• 목록
• 답변
• 글쓰기
• 게시판 리스트 옵션
  • 수정
  • 삭제

​이번 원판돌리기 문제는 구현 문제입니다.저는 이번 문제를 총 4가지의 함수를 사용해서 풀었습니다.원판을 돌리는 함수인접한 수를 찾는 함수인접한 수 중 같은 수를 지우는 함수인접한 수가 없다면 평균을 내서 평균보다 크면 -1, 작으면 +1을 시키는 함수​알고리즘의 동작방식을 먼저 보겠습니다.먼저 원판을 원판돌리기 돌립니다. 그 다음 인접한 수를 찾고, 인접한 수 중 같은 수가 있다면 없애고, 같은 수가 없다면 평균보다 큰 수는 -1, 작은 수는 +1을 합니다. 중요한 점은 만약 더 이상 수가 남아있지 않다면 즉시 끝내버려야합니다. 또한, 평균이 원판돌리기 0이 나올 수는 없기 때문에 빈칸은 0으로 해두었습니다.먼저 돌리는 함수를 보겠습니다. 원판을 T번 돌리는데, 어떻게 돌릴지는 이미 정해져 있습니다. x[i]의 배수 번째 원판을 d[i]( ϐ | 1, 0이면 시계방향 1이면 반시계방향) 방향으로 돌리는데 총 k[i]번 돌립니다.예를 원판돌리기 들면 2 0 1 로 주어지면 2의 배수 번째 즉, 2, 4, 6, ... 번째 원판을 0 =시계방향으로 1번 돌립니다.그림에는 원판으로 주어지지만 사실 2차원 배열을 사용하여 원판 상태를 저장할 수 있겠죠. 그러면 시계 방향과 반시계 방향은 원판돌리기 다음과 그림과 같습니다.아래 코드가 위의 작동방식을 구현한 함수입니다. xt 배수 번째 원판을 dt방향으로 kt번 이동시킵니다.그 다음은 인접한 곳을 찾는 함수입니다. 이 함수는 문제에 나온대로 구현합니다. 여기서 주요한 점은 우선 빈칸, 문제에서는 x표시가 된 곳은 모두 숫자가 원판돌리기 같으므로, 빈칸이 아님을 검사해야합니다.또한 만약 인접한 곳을 찾았다고 바로 지우게 되면 같은 곳에서 다른 인접한 곳을 찾지 못합니다. 예를 들어 (1, 1)과 (1, 2)의 숫자가 같다고 바로 지워버리면 만약 (2, 1)도 (1, 1)과 같은 숫자라면 (2, 원판돌리기 1)은 지워버리지 못하겠죠. 이미 (1, 1)이 지워진 상태이기 때문이죠.따라서 저는 map자료구조를 사용해서 지워버릴 곳을 저장해놓고 인접하면서 같은 수인 곳을 모두 찾은 다음 지워버리기로 했습니다. set을 사용한 이유는 중복을 없애서 시간복잡도를 조금이라도 줄일 의도였습니다.그러면 마지막으로 인접하면서 같은 원판돌리기 수를 지우는 함수와 수를 변화시키는 함수를 보겠습니다.평균을 구할 때 중요한 점은 빈칸이 아닌 곳에만 평균을 구해야하며(예제에 나와있습니다), 또, 수를 변경할 때도 빈칸이 아닌 칸에 작업을 해야겠죠.전체 코드는 깃허브를 참고해주세요.Contribute to RaonPark/baekjoon-solution development by creating an account 원판돌리기 on GitHub.​