배열을 시계 또는 반시계 방향으로 순회하기

내가 접했던 문제는 원형 회전판문제였다.

 

배열 pan[]이 있다고 치면

이 배열을 회전판이라고 생각하자

0

1

2

3

 

위 배열을 회전판 그림으로 나타낸 것

빨간색 화살표가 가리키는 숫자를 보면

1. 회전판을 반시계방향으로 돌리면 0 -> 1 -> 2 -> 3 -> 0 -> 1 -> 2 -> 3 -> ... 이지만
2. 회전판을 시계방향으로 돌리면 0 -> 3 -> 2 -> 1 -> 0 -> 3 -> 2 -> 1 -> ... 이다.

1에서 보다시피, 반시계로 돌려야 배열을 오른쪽으로 순회하고 시계로 돌리면 왼쪽으로 순회하는 것을 알 수 있다.

 

그렇다면 문제,

Q. 반시계 방향으로 7만큼 돌렸을 때, 화살표가 가르키는 숫자는?

이거... 어떻게 구현할까?

1의 반시계의 경우는 쉽다. 회전판이 처음 가르키는 위치의 인덱스가 i라고 하면,

pan[( i + 7 ) % 4]를 하면 답을 구할 수 있다.

확인해보면, 1 2 3 0 1 2 "3"

3이 답이고, 위 식의 답도 3임을 알 수 있다.

 

그런데!!

시계방향인 경우는 어떻게 구현할까....!! 이거 시간 너무 많이 잡아먹었다 ㅠ ㅠ

결론부터 말하자면

moveIdx = i - (7 % 4);

만약 answer < 0 이면, moveIdx += 4;

pan[ moveIdx ] 이다.

확인해보면, 3 2 1 0 3 2 "1"

1이 답이고, 위 식의 답도 1임을 알 수 있다.

 

배열의 인덱스를 구하는 공식을 좀 더 점화식(?)처럼 써보자면

이동거리만큼 이동한 후의 인덱스 = 현재 화살표가 가르키는 숫자의 인덱스 - ( 이동거리 % 회전판 배열의 길이 )

이때, 값이 음수라면 배열의 길이를 더해준다.