21162번 - 뒤집기 K
어렵게 풀긴 풀었는데, 코드 안정성도 없는 것 같고, 너무 어렵게 푼 것 같아요. 다른 정석풀이가 어떤 것이 있는지 알고싶습니다. 우선, 제 풀이부터 설명드리겠습니다.
이 문제를 관찰하다가, 결국 수열은 한 번 뒤집은 상태에서, 원형으로 돌리면서 수열들을 정렬하면 되는 문제로 치환하였습니다.
해싱값은 그냥 다항함수에 (mod 1000000007)로 하였습니다.
그래서
1) 1부터 i번째까지의 해싱값을 미리 저장해둠.
2) i~j번째까지의 해싱값을 O(1)만에 계산하도록 함수를 짬.
3) 슬라이딩 윈도우(?) 느낌으로다가 싸이클을 돌리면서 수열을 우선순위 큐에 넣음(수열을 다 넣진 않고, 시작 인덱스를 넣었습니다)
4) 그렇게 해서 k번째보다 커질때만 우선순위큐의 top과 비교하여 넣을지 말지 결정하며 k번째 수열을 유지함.
이 때, 수열끼리의 크기를 비교할 때는, binary search와 해싱값을 이용하여 두 개의 수열의 가장 긴 공통 길이를 찾고, 그 직후의 값을 비교하여 비교하여서 O(log N).
결국 우선순위큐와 합치면 아마 O(N*logN*logN)..?
근데 다른 사람들 보니까 binary search는 드문 것 같고, 다른 방식의 풀이인 것 같더라구요. 다른 사람 풀이들이 이해가 잘 안되는데 보통 이 문제는 어떤 방식으로 푸나요?
뒤집은 문자열을 2개 이어붙인 문자열에 대해 suffix array를 만드는 방식으로도 풀 수 있습니다.
해싱과 이분 탐색을 이용해 O(log N) 시간에 두 부분 문자열의 사전순 비교를 수행해서, O(N log^2 N) 시간에 N-1개의 부분 문자열을 정렬(또는 selection)하는 풀이를 의도하고 출제했습니다. zenith82114님께서 말씀하신 것처럼 suffix array를 이용하면 O(N log N)에 해결할 수도 있습니다.
감사합니다..! 공부할게 정말 많군요 ㅠ
댓글을 작성하려면 로그인해야 합니다.
ksjb2897 1년 전
어렵게 풀긴 풀었는데, 코드 안정성도 없는 것 같고, 너무 어렵게 푼 것 같아요. 다른 정석풀이가 어떤 것이 있는지 알고싶습니다. 우선, 제 풀이부터 설명드리겠습니다.
이 문제를 관찰하다가, 결국 수열은 한 번 뒤집은 상태에서, 원형으로 돌리면서 수열들을 정렬하면 되는 문제로 치환하였습니다.
해싱값은 그냥 다항함수에 (mod 1000000007)로 하였습니다.
그래서
1) 1부터 i번째까지의 해싱값을 미리 저장해둠.
2) i~j번째까지의 해싱값을 O(1)만에 계산하도록 함수를 짬.
3) 슬라이딩 윈도우(?) 느낌으로다가 싸이클을 돌리면서 수열을 우선순위 큐에 넣음(수열을 다 넣진 않고, 시작 인덱스를 넣었습니다)
4) 그렇게 해서 k번째보다 커질때만 우선순위큐의 top과 비교하여 넣을지 말지 결정하며 k번째 수열을 유지함.
이 때, 수열끼리의 크기를 비교할 때는, binary search와 해싱값을 이용하여 두 개의 수열의 가장 긴 공통 길이를 찾고, 그 직후의 값을 비교하여 비교하여서 O(log N).
결국 우선순위큐와 합치면 아마 O(N*logN*logN)..?
근데 다른 사람들 보니까 binary search는 드문 것 같고, 다른 방식의 풀이인 것 같더라구요. 다른 사람 풀이들이 이해가 잘 안되는데 보통 이 문제는 어떤 방식으로 푸나요?