문제 정의
n×n 크기의 행렬이 주어졌다고 가정해 보겠습니다. 이때 확인해야 할 것은 행렬의 모든 행이 바로 앞 행의 원형 회전(circular rotation)인지 여부입니다. 단, 첫 번째 행은 마지막(n번째) 행의 원형 회전이어야 한다는 조건이 붙습니다.
예를 들어 다음과 같은 행렬이 입력으로 주어진 경우를 살펴보겠습니다.
| B | A | D | C |
| C | B | A | D |
| D | C | B | A |
| A | D | C | B |
두 번째 행은 첫 번째 행을, 세 번째 행은 두 번째 행을, 네 번째 행은 세 번째 행을 각각 오른쪽으로 한 칸씩 민 형태이며, 첫 번째 행 역시 네 번째 행의 원형 회전입니다. 따라서 출력 결과는 True가 됩니다.
해결 접근 방법
이 문제는 문자열 결합(concatenation) 기법을 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
"어떤 문자열을 자기 자신과 한 번 이어 붙이면, 그 결과 안에는 원래 문자열의 모든 원형 회전이 부분 문자열로 포함된다."
예를 들어 "-B-A-D-C"를 두 번 이어 붙인 "-B-A-D-C-B-A-D-C"라는 문자열에는 "-C-B-A-D", "-D-C-B-A", "-A-D-C-B"처럼 가능한 모든 회전 형태가 부분 문자열로 존재합니다. 이 성질을 이용하면 각 행이 원형 회전인지를 단순한 부분 문자열 검색만으로 판별할 수 있습니다.
구체적인 알고리즘은 다음과 같습니다.
- 빈 문자열
concat을 준비합니다. - 첫 번째 행의 각 요소를 "-" 구분자와 함께 이어 붙여
concat에 저장합니다. concat을 자기 자신과 한 번 더 연결하여 두 배 길이의 문자열로 만듭니다.- 두 번째 행부터 마지막 행까지 차례대로 순회하면서, 각 행을 같은 방식으로 문자열로 변환합니다.
- 변환된 문자열이
concat에 존재하지 않으면 즉시False를 반환합니다. - 모든 행이 조건을 통과하면
True를 반환합니다.
요소 사이에 "-" 구분자를 넣는 이유는 값의 경계가 모호해지는 오류를 막기 위해서입니다. 구분자 없이 이어 붙이면 [12, 3]과 [1, 23]이 모두 "123"으로 변환되어, 서로 다른 배열임에도 같은 문자열로 판별되는 문제가 생길 수 있습니다.
구현 예제
다음 파이썬 코드를 통해 실제 구현을 확인해 보겠습니다.
def solve(matrix):
# 첫 번째 행을 문자열로 변환
concat = ""
for i in range(len(matrix)):
concat = concat + "-" + str(matrix[0][i])
# 문자열을 두 배로 늘려 모든 원형 회전을 포함
concat = concat + concat
# 나머지 행들이 원형 회전인지 확인
for i in range(1, len(matrix)):
curr_row = ""
for j in range(len(matrix[0])):
curr_row = curr_row + "-" + str(matrix[i][j])
if curr_row not in concat:
return False
return True
matrix = [['B', 'A', 'D', 'C'],
['C', 'B', 'A', 'D'],
['D', 'C', 'B', 'A'],
['A', 'D', 'C', 'B']]
print(solve(matrix))입력
[['B', 'A', 'D', 'C'],
['C', 'B', 'A', 'D'],
['D', 'C', 'B', 'A'],
['A', 'D', 'C', 'B']]출력
True동작 원리 상세 설명
위 코드가 실행되면 먼저 첫 번째 행으로부터 "-B-A-D-C"라는 문자열이 만들어지고, 이것이 두 번 이어져 "-B-A-D-C-B-A-D-C"가 됩니다. 이후 두 번째 행 "-C-B-A-D", 세 번째 행 "-D-C-B-A", 네 번째 행 "-A-D-C-B"가 차례로 이 긴 문자열 안에서 검색되며, 세 행 모두 발견되므로 최종적으로 True가 출력됩니다.
행렬의 크기를 n×n이라고 할 때, 모든 행의 문자열을 만드는 데 O(n²)의 시간이 소요되며, 파이썬의 in 연산자는 내부적으로 매우 효율적인 문자열 검색 알고리즘을 사용하기 때문에 전체적으로도 실용적인 성능을 보여줍니다. 또한 이 방식은 요소가 숫자든 문자든 str()로 변환만 하면 되므로 다양한 자료형에 그대로 적용할 수 있다는 장점이 있습니다.