[1. 문제 설명]
https://www.acmicpc.net/problem/10266
[2. 풀이 접근]
최초에 생각해 본 방식
- 첫번째 시계의 배치를 1도 단위로 회전시켜서 이어 붙인다.
- 여기서, 두번째 시계의 배치를 찾는다.
- 그런데, 각도가 0 ~ 360,000 이므로, 1도 단위로 회전 시키면 메모리 및 시간 초과가 발생할 것이다.
- 현실적인 시간/공간 복잡도가 되도록 해야 한다.
올바른 풀이
- 역시 첫번째 시계의 배치를 확장한다.
- 그러나, [0, 360,000) 에 대해서 각도가 있으면 1, 없으면 0 으로 설정한다.
- 회전 한 경우는 [360,000, 720,000) 범위에 대해서 1 또는 0으로 설정하도록 한다.
- 이제 이 배치에서 두번째 시계의 배치를 찾는다.
- 즉, 첫번째 시계의 배치는 길이가 720,000 인 배열에 설정하고
- 두번째 시계의 배치는 길이가 360,000 인 배열에 설정하고
- kmpSearch 를 응용하여, 선형 시간내 두번째 시계의 배치의 존재 유무를 확인 할 수 있다.
문제에서 입력의 최대 길이 만큼의 배열을 할당하고, 이를 활용하여 푸는 문제의 패턴이 있다.
이 부분을 놓쳤다.
[3. 코드]
'알고리즘 > Baekjoon' 카테고리의 다른 글
kmp. [7575] (0) | 2023.04.27 |
---|---|
kmp. [11585] (0) | 2023.04.25 |
kmp. [4354] (0) | 2023.04.21 |
kmp. [1701] (0) | 2023.04.21 |
위상정렬. [2056] (0) | 2023.04.13 |