[25.03.13] algo 백준 17822 리뷰

25.03.13(Thu) 알고리즘 스터디 리뷰

문제 요약

• N개의 원판에 각각 M개의 정수가 적혀 있으며, 인접한 위치 관계가 정의되어 있음.
• 총 T번의 회전을 수행하며, 각 회전은 특정 배수(xi)의 원판을 특정 방향(di)으로 특정 칸 수(ki)만큼 회전시킴.
• 회전 후 인접하면서 같은 수가 있으면 모두 지우고, 없으면 평균보다 큰 수는 1 감소, 작은 수는 1 증가시킴.
• 모든 회전이 끝난 후 남아 있는 수들의 합을 구하는 문제.
• 원판은 독립적으로 회전하며, 각 원판의 숫자는 원형으로 연결되어 있음.

풀이방식

Rotate & Remove 구현에서 잘못했던 점
Rotate를 구현할때 가장 어려웠던 점은 시계방향과 반시계방향이 나누어져있다는 점이었다. 배열을 활용했기 때문에 해당 움직임을 구현할때 인덱스 값을 정확하게 계산하는 것이 필요했는데 처음 생각했던 방식은 아래와 같았다. 그런데 이런 방식은 음수가 되는 값을 나눗셈 연산하게 되는 점을 처리하지 못한다는 문제가 있었다.

• 시계: (i - k) % M
• 반시계: (i + k) % M

그래서 결과적으로 나오게 된 방식이 음수가 될 수 있는 값에는 M을 한번 더해주는 방식으로 풀이하면, 음수가 되는 것도 처리 할 수 있고, 음수가 되지 않더라도 인덱스 계산에는 문제가 발생하지 않는다.

• 시계: (i - k + M) % M
• 반시계: (i + k) % M

이러한 문제가 인접하는 수중에 중복제거하는 함수에도 나타났는데 x 인덱스를 계산하는 과정에서 음수가 나올 수 있다는 점을 생각하지 못했다. 그래서 이부분도 적용을 하고 나서야 문제 해결이 가능했다.

구현 문제가 어려웠던 이유
원판 돌리기의 문제가 어려웟던 이유는 다른 구현문제가 어려운 문제와 동일했다 요구사항이 상세히 작성되어 있고 그 부분을 완벽하게 이해하지 못하면 풀기 어려운 문제였다. 이러한 문제를 빠르고 정확하게 풀기 위해서는 문제를 접할 때 요구사항을 이해하기 쉽게 작성하고 함수를 나눌때 함수의 요구사항을 나누어서 작성을 한번 해보는 것을 습관으로 들여야 할 것 같다.
그리고 구현시에 오래걸렸던 부분이 함수를 3개 정도 구현하다 보니 요구사항을 바로 떠올리는 것에 어려움을 겪었다. 그래서 구현코드를 작성하기 전에는 주석을 통해 함수의 동작 방식을 상세히 작성하고 풀이해보는 것이 좋을 것 같다.

결과 코드