Snake Traverse 문제
2006년도에 Microsoft 본사 면접을 봤을 때 두번째로 면접볼때 풀었던 문제다. 화이트보드에 직접 코드를 작성하기란 여간 까다로운게 아니어서 15분만에 풀었어야 하는 문제를 30분정도 걸렸던것 같다. 다행히도 면접을 봤던 Diago(현재는 구글 Japan에 근무)가 친절하게 기다려줘서 clear했던 문제. 그런데 이 문제가 구글이나 MS와 같은 IT 기업의 문제 은행으로 등록되어 있다니. 그땐 사전에 미리 공부도 하지 못해서 "뭐 이런 문제를 내지?"라고 생각했었는데, 오늘 우연히 발견하게 되어서 간단하게 풀어보았다. 머리도 식힐겸~
문제의 요구 사항은 NxN 배열이 있을 때 해당 배열의 각 항목을 뱀 꼬리를 잡듯이 하나씩 출력하는 문제다.
영어로 설명하자면, 이렇다.
Given a 2-d array, write code to print it out in a snake pattern. For example, if the array is this:
1, 2, 3
4, 5, 6
7, 8, 9
the routine prints this:
1,2,3,6,9,8,7,4,5The array is an NxN array.
편의상 Python으로 작성했다. 주석이나 이런저런 코드를 빼면 20줄 내외로 작성 가능하다. 생각한 방안은 진행 방향을 고려해서 x와 y의 증가(또는 증감)을 자동으로 계산되도록 한다. 그리고 이 순환이 끝날 수 있도록 min과 max 값을 잘 조절하는게 핵심. 더 좋은 방법이 있을 수 있고, 이게 최선은 아닐 수도 있습니다.
# -*- coding: utf-8 -*- class SnakeTraverse: def __init__(self, dim, tables): self.dim = dim self.tables = tables def traverse(self): # 스네이크 traverse를 하기 위해서는 x와 y 좌표를 통해 방향을 지정한다. # 0 --> 오른쪽으로, 1 --> 아래로, 2 --> 왼쪽으로, 3 --> 위쪽으로 switch = [[1, 0], [0, 1], [-1, 0], [0, -1]] switch_type = 0 # 한번의 traverse가 끝나면 다음 시작 좌표를 조절한다. adjust_to_next_point = [[-1, 1], [-1, -1], [1, -1], [1, 1]] x = 0 y = 0 min_x = 0 max_x = self.dim - 1 min_y = 0 max_y = self.dim - 1 while True: # x와 y의 최소값과 최대값을 변경하여 해당 좌표안에서만 탐색하도록 한다. while ((min_x <= x <= max_x) and (min_y <= y <= max_y)): # 현재 좌표의 값을 찍고 print str(x) + ", " + str(y) + " ==> " + str(self.tables[y][x]) # 다음 좌표로 이동 x = x + switch[switch_type][0] y = y + switch[switch_type][1] # 모든 위치가 탐색될 때 끝난다. if min_x > max_x or min_y > max_y: break; # 다음 순환을 위해 좌표를 보정한다. x = x + adjust_to_next_point[switch_type][0] y = y + adjust_to_next_point[switch_type][1] # 방향에 따라서 x와 y 값의 최대값과 최소값을 변경한다. if switch_type is 0: min_y = min_y + 1 elif switch_type is 1: max_x = max_x - 1 elif switch_type is 2: max_y = max_y - 1 else: min_x = min_x + 1 # 방향을 바꾼다. switch_type = (switch_type + 1) % 4 if __name__ == "__main__": tables_3 = [[0,1,2], [3,4,5], [6,7,8]] tables_4 = [[0,1,2,3],[4,5,6,7],[8,9,10,11],[12,13,14,15]] traverse = SnakeTraverse(3, tables_3) traverse.traverse() traverse = SnakeTraverse(4, tables_4) traverse.traverse()