문제 출처
1. 문제설명
n
개의 원판에는 m
개의 숫자가 적혀있다.
- 게임판의 원판을 회전시키고자 한다.
- 회전은 독립적으로 이루어진다.
- 회전 요청은
{x, d, k}
이며 x
번째 원판을 d
방향으로 k
번 움직인다는 의미이다.
- 회전 이후 인접한 위치의 같은 숫자가 지워진다.
- 원판에 지워지는 수가 없는 경우에는 원판 전체에 적힌 수의 평균을 구해서 정규화해준다.
- 원판의 모든 값을 더해서 평균을 내고, 편의상 소수점을 버린 값을 취한다.
2. 입/출력
- 원판의 개수
n
, 원판 내의 숫자의 개수 m
, 회전 횟수 q
q
개의 줄에는 앞서 언급한 회전 요청이 주어진다.
- 게임판을 총 q번 회전 시킨 후에 게임판에 남아있는 수의 총합을 구하라
3. 문제 분류
4. 알고리즘 설계
- 원판이 최대 50개가 존재할 수 있다.
- 이런 회전 문제의 경우,
deque
를 사용하면 매우 유용하다.
- 만약
x
번 원판을 시계방향 회전한다면 아래와 같은 방법으로 회전한 효과를 낼 수 있다.
deque
의 앞단에 가장 뒤의 원소를 집어넣고
deque
의 가장 뒤의 원소를 제거
- 인접한 숫자를 탐색하는 방법
- 4방향으로 탐색
x
좌표의 경우 값의 범위를 벗어나면 버리고
y
좌표의 경우 값의 범위를 벗어나면 가장 마지막 부분으로 보내면 된다.
x
좌표는 값의 1번 원판의 위치와 마지막 원판의 위치가 인접하지 않기 때문이다.
5. 전체 코드
4. 소감
- 회전을
deque
로 구현하면 굉장히 쉬운 문제였다.