[코딩테스트] 코딩테스트 빈출 유형 정리

1. 회전

1-1. zip()

정사각형, 직사각형 모두 동일하게 적용

arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]

# 시계 90 (= 반시계 270)
arr_90 = list(map(list, zip(*arr[::-1])))
print(arr_90)

# 시계 180
arr_180 = [a[::-1] for a in arr[::-1]]

# 시계 270 (= 반시계 90)
arr_270 = [x[::-1] for x in list(map(list, zip(*arr[::-1])))[::-1]]

1-2. 인덱스 규칙 찾아서 회전

정사각형

arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
n = 3

# 시계 방향 90 (= 반시계 방향 270)
rotate_90 = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        rotate_90[j][n - i - 1] = arr[i][j]


# 시계 180 & 반시계 180
rotate_180 = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        rotate_180[n - i - 1][n - j - 1] = arr[i][j]

# 시계 270 & 반시계 90
rotate_270 = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        rotate_270[n - 1 - j][i] = arr[i][j]

직사각형

a = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]


def rotate_90(a):
  m = len(a)
  n = len(a[0])
  result = [[0]* m for _ in range(n)] 
  for i in range(m): 
    for j in range(n): 
      result[j][m-i-1] = a[i][j]
  return result

def rotate_180(a):
  n = len(a)
  m = len(a[0])
  result = [[0]* m for _ in range(n)] 
  for i in range(n): 
    for j in range(m): 
      result[n-i-1][m-j-1] = a[i][j]
  return result

def rotate_270(a):
  n = len(a)
  m = len(a[0])
  result = [[0]* n for _ in range(m)] 
  for i in range(n): 
    for j in range(m): 
      result[m-1-j][i] = a[i][j]
  return result

2. 부분 회전

# 7X7 배열

arr = [[7 * j + i for i in range(1, 8)] for j in range(7)]
new_arr = [[0] * 7 for _ in range(7)]
sy, sx = 2, 2
length = 3


# 배열의 특정 부분(정사각형)을 회전
def rotate_90(sy, sx, length):
    global arr, new_arr

    # 정사각형을 시계방향으로 90도 회전
    for y in range(sy, sy + length):
        for x in range(sx, sx + length):
            # 1단계 : (0,0)으로 옮겨주는 변환
            oy, ox = y - sy, x - sx
            # 2단계 : 90도 회전했을때의 좌표
            ry, rx = ox, length - oy - 1
            # 3단계 : 다시 (sy,sx)를 더하기
            new_arr[sy + ry][sx + rx] = arr[y][x]

    # new_arr 값을 현재 board에 옮김
    for y in range(sy, sy + length):
        for x in range(sx, sx + length):
            arr[y][x] = new_arr[y][x]
            print(arr[y][x])

rotate_90(sy, sx, length)

for i in range(len(arr)):
    print(arr[i])

3. 순열, 중복 순열, 조합, 중복 조합

3.1 순열(Permutations)

arr = [1, 2, 3, 4]
visited = [0] * len(arr)  

# 뽑을 개수, 뽑힌 값을 담는 배열
def permutations(n, new_arr):
    global arr
    # 순서 상관 O, 중복 X
    if len(new_arr) == n:
        print(new_arr)
        return

    for i in range(len(arr)):
        if not visited[i]:
            visited[i] = 1
            permutations(n, new_arr + [arr[i]])
            visited[i] = 0


permutations(2, [])

3.2 중복 순열(Product)

arr = [1, 2, 3, 4]
def product(n, new_arr):
    global arr

    # 순서 상관 O, 중복 O
    if len(new_arr) == n:
        print(new_arr)
        return

    for i in range(len(arr)):
        product(n, new_arr + [arr[i]])

product(2, [])

3.3 조합(Combinations)

arr = [1, 2, 3, 4]

def combinations(n, new_arr, c):

    # 순서 상관 X, 중복 X
    if len(new_arr) == n:
        print(new_arr)
        return

    for i in range(c, len(arr)):
        combinations(n, new_arr + [arr[i]], i + 1)


combinations(2, [], 0)

3.4 중복 조합(Combinations with replacement)

arr = [1, 2, 3, 4]

def combinations_with_replacement(n, new_arr, c):

    # 순서 상관 X, 중복 O
    if len(new_arr) == n:
        print(new_arr)
        return

    for i in range(c, len(arr)):
        combinations(n, new_arr + [arr[i]], i)


combinations_with_replacement(2, [], 0)

4. 중력

4.1 바닥까지 하강

arr = [[0, 1, 0], [1, 0, 1], [0, 1, 0], [0, 0, 1], [0, 1, 0]]

print("Before")
for i in range(len(arr)):
    print(arr[i])


def gravity():
    n = len(arr)
    m = len(arr[0])
    for i in range(n - 1):
        for j in range(m):
            p = i
            # 현재칸이 아래로 내려갈 수 있다면 그 윗줄도 한 칸 씩 연쇄적으로 내려와야함
            while 0 <= p and arr[p][j] == 1 and arr[p + 1][j] == 0:
                arr[p][j], arr[p + 1][j] = arr[p + 1][j], arr[p][j]
                p -= 1


gravity()

print("After")
for i in range(len(arr)):
    print(arr[i])

5. 나선형(달팽이) 배열

5.1 안에서 밖으로

• 좌 $\rightarrow$ 하 $\rightarrow$ 우 $\rightarrow$ 상

arr = [[0] * 5 for _ in range(5)]


def tornado():
    global arr
    d = [(0, -1), (1, 0), (0, 1), (-1, 0)]
    y = len(arr) // 2
    x = len(arr) // 2
    num = 0  # 칸에 채워넣을 값
    dist = 1
    d_idx = 0  # 서 남 동 북 순서
    move_count = 0  # 2가 되면 dist 길이가 1 늘어나고 move_count는 다시 0으로 초기화
    while True:
        for _ in range(dist):
            dy, dx = d[d_idx]
            Y = dy + y
            X = dx + x
            if (Y, X) == (0, -1):  # 0행 -1열이 토네이도가 모두 끝나고 나서의 위치임
                return
            num += 1
            arr[Y][X] = num
            y = Y
            x = X
        move_count += 1
        d_idx = (d_idx + 1) % 4
        if move_count == 2:
            dist += 1
            move_count = 0


tornado()
for i in range(5):
    print(arr[i])

5.2 밖에서 안으로

def solution(n):
    if n == 1:
        return [[1]]

    answer = [[0 for j in range(n)] for i in range(n)]  

    x = 0
    y = 0
    d_idx=0

    for i in range(n * n):
        answer[x][y] = i + 1
        if d_idx == 0:
            y += 1
            if y == n - 1 or answer[x][y + 1] != 0:  
                d_idx = 1
        elif d_idx == 1:
            x += 1
            if x == n - 1 or answer[x + 1][y] != 0:
                d_idx = 2
        elif d_idx == 2:
            y -= 1
            if y == 0 or answer[x][y - 1] != 0:
                d_idx = 3
        elif d_idx == 3:
            x -= 1
            if x == n - 1 or answer[x - 1][y] != 0:
                d_idx = 0

    return answer


arr = solution(5)
for i in range(len(arr)):
    print(arr[i])

6. 이동 중 벽에 부딪혀서 방향 전환

def get_next_loc(i, j, speed, dir):

    if dir == UP or dir == DOWN:  # i
        cycle = R * 2 - 2
        if dir == UP:
            speed += 2 * (R - 1) - i
        else:
            speed += i

        speed %= cycle
        if speed >= R:
            return (2 * R - 2 - speed, j, UP)
        return (speed, j, DOWN)

    else:  # j
        cycle = C * 2 - 2
        if dir == LEFT:
            speed += 2 * (C - 1) - j
        else:
            speed += j

        speed %= cycle
        if speed >= C:
            return (i, 2 * C - 2 - speed, LEFT)
        return (i, speed, RIGHT)

7. 배열 한 칸씩 돌리기

from collections import deque

N, M, R = map(int, input.split())

arr = []
new_arr = [[0]*M for _ in range(N)]
q = deque()

for i in range(N):
    arr.append(list(input().split()))

loops = min(N, M) // 2
for i in range(loops):
    q.clear()
    q.extend(arr[i][i:M-i])
    q.extend([row[M-i-1] for row in arr[i+1:N-i-1]])
    q.extend(arr[N-i-1][i:M-i][::-1])
    q.extend([row[i] for row in arr[i+1:N-i-1]][::-1])
    
    q.rotate(-R)
    
    for j in range(i, M-i):                 # 상
        new_arr[i][j] = q.popleft()
    for j in range(i+1, N-i-1):             # 우
        new_arr[j][M-i-1] = q.popleft()
    for j in range(M-i-1, i-1, -1):           # 하
        new_arr[N-i-1][j] = q.popleft()  
    for j in range(N-i-2, i, -1):           # 좌
        new_arr[j][i] = q.popleft()    

return new_arr

Reference

• https://velog.io/@rhdmstj17/%EC%82%BC%EC%84%B1-%EC%9D%B8%EC%9E%AC%EC%9B%90-%EB%93%A4%EC%96%B4%EA%B0%80%EA%B8%B0-%EC%A0%84-%EC%88%99%EC%A7%80%ED%95%98%EA%B3%A0-%EB%93%A4%EC%96%B4%EA%B0%80%EB%A9%B4-%EC%A2%8B%EC%9D%80-%EB%B9%88%EC%B6%9C-%EC%BD%94%EB%93%9C-%EC%9C%A0%ED%98%95-6%EA%B0%80%EC%A7%80