본문 바로가기

알고리즘/Baekjoon

kmp. [10266]

[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