[BOJ] 1913 - 달팽이 (Python, JavaScript)

 

 

아이디어

 

2차원 리스트를 이용해 바깥쪽부터 안쪽으로 빈 공간에 숫자를 채워 나간다.

 

 

풀이 #1 (Python)

 

방향에 따라 행열 인덱스 변화 값 튜플을 반시계 방향인 하우상좌 순으로 리스트 delta에 저장한다.

 

함수 fill에서는 0으로 채워진 N*N 2차원 리스트 table를 만들고, N*N부터 1까지의 숫자를 (0, 0)부터 채워 나간다.

현재 숫자를 문자열로 인덱스에 맞게 리스트 table에 저장하고, 현재 숫자가 M이면 pos에 현재 좌표를 문자열로 저장한다.

다음 인덱스가 범위를 벗어나거나 해당 위치에 이미 값이 채워져 있으면 d를 증가시켜 방향을 전환한다.

 

값이 모두 채워진 리스트 table을 한 줄씩 공백으로 join하여 출력하고, 마지막 줄에 pos를 출력한다.

 

delta = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def fill():
    table = [[0] * N for _ in range(N)]
    pos = ()
    i = j = d = 0
    di, dj = delta[0]
    for n in range(N*N, 0, -1):
        if n == M:
            pos = (i+1, j+1)
        table[i][j] = f'{n}'
        if i+di >= N or i+di < 0 or j+dj >= N or j+dj < 0 or table[i+di][j+dj]:
            d = (d+1)%4
            di, dj = delta[d]
        i, j = i+di, j+dj
    for t in table:
        print(' '.join(t))
    print(*pos)

N = int(input())
M = int(input())
fill()

 

 

리스트를 언패킹하여 출력하는 코드보다 문자열로 join하여 출력하는 코드가 메모리 사용량은 같으면서 더 빨랐다.

리스트에 숫자를 문자열로 저장하고 join하는 코드는 더 빠르기는 하나, 메모리가 더 많이 사용되었다.

# 1.
for n in range(N*N, 0, -1):
    table[i][j] = n
...
for t in table:
    print(*t)

# 2. 1번 코드보다 더 빠른 코드
for n in range(N*N, 0, -1):
    table[i][j] = n
...
for t in table:
    print(' '.join(map(str, t)))

# 3. 2번 코드보다 메모리를 더 많이 사용하나 더 빠른 코드
for n in range(N*N, 0, -1):
    table[i][j] = f'{n}'
...
for t in table:
    print(' '.join(t))

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1 코드와 마찬가지로 0으로 채워진 2차원 배열 table을 만들고 값을 채운 후 문자열로 table과 pos를 출력한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const delta = [[1, 0], [0, 1], [-1, 0], [0, -1]];

const N = Number(input[0]);
const M = Number(input[1]);
let table = [];
for (let i=0; i<N; i++) {
    let t = [];
    for (let j=0; j<N; j++) {
        t.push(0);
    }
    table.push(t);
}
let pos;
let i = 0;
let j = 0;
let d = 0;
let [di, dj] = delta[0];
for (let n=N*N; n>0; n--) {
    if (n === M) pos = [i+1, j+1];
    table[i][j] = n;
    if (i+di >= N || i+di < 0 || j+dj >= N || j+dj < 0 || table[i+di][j+dj]) {
        d = (d+1)%4;
        [di, dj] = delta[d];
    }
    [i, j] = [i+di, j+dj];
}
for (let t of table) {
    console.log(t.join(' '));
}
console.log(pos.join(' '));