내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
백준 온라인 저지 (BOJ)
»
데크 소트
ps:problems:boj:1624
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 데크 소트 ====== ===== 풀이 ===== * [[ps:problems:boj:10975]]의 하드 버전. n의 범위가 커진것은 별 문제가 아닌데, 중복 숫자가 들어올수 있다는 것 때문에 전혀 다른 방법으로 풀어야 한다. * 중복 숫자가 없을 경우에는, 현재 만들어진 덱의 끝에 있는 숫자와 인접한 순위의 숫자가 나오면 무조건 덱에 추가해도 소팅이 가능했다. 하지만 중복 숫자가 있는 경우에는 이야기가 달라지는데, 입력 시퀀스가 5,4,5,6,5 이라고 할 경우, 처음 5를 갖고 새 덱을 만든 다음에 4가 들어왔을 경우, 뒤에 5가 아직 2개 더 나올 예정이지만 4를 앞에다가 붙일 수 있다. 뒤에 나오는 5는 덱의 뒤쪽에 붙이면 되기 때문이다. 하지만 그 뒤에 6이 들어왔을 경우에는 붙일수 없다. 양쪽이 다 막히면 그 뒤에 나오는 5를 넣을수가 없기 때문이다. 결국, 순위가 인접한 숫자라도 상황에 따라서 덱에 붙일수 있는 경우가 있고 새 덱을 만들어야 하는 경우가 생긴다. * 그렇다면.. 역시 그리디하게, "뒤에 들어올 똑같은 숫자가 있으면 양쪽이 뚫린 경우에만 덱에 추가한다, 한쪽만 뚫려있으면 새 덱을 만든다" 라는 전략을 세워보자. 그 경우에는 이런 반례가 생긴다. 5,4,6,5,3,4 라는 시퀀스가 들어올 경우.. 4는 5의 양쪽이 뚫려있으므로 5앞에 붙이고, 6은 한쪽이 막혀있으므로 세 덱을 만든다. [4,5] / [6] 의 상황인데. 이때 3을 4의 앞에 붙일수가 없으므로 3을 또 새로운 덱으로 만들어야 하고, 최종적으로 [3]/[4,4,5]/[6] 의 세개의 덱이 만들어진다. 하지만 4가 처음 나왔을때 새로운 덱으로 만들었다면 [3,4,4]/[5,5,6] 의 두개의 덱으로 처리할 수 있다. 즉, 시퀀스를 앞에서부터 읽으면서 기존덱에 붙일지 새 덱을 만들지 '그리디하게' 결정하는 것은 불가능하다.. * 다른 방식의 그리디 전략을 세울 수 있다. 시퀀스 안의 숫자를 기존 덱에 붙일지 새 덱을 만들지 하는 결정을, 현재까지 만들어진 덱의 상황을 보고 결정하는 것이 아니라, 아예 맨 처음부터 1번 덱에는 [a,b] 범위의 숫자들을 담고, 2번 덱에는 [c,d]범위의 숫자들들을 담고.. 하겠다는 결정을 내려두고 거기에 맞춰서 처리하는 방법이다. * 우선.. 중복된 같은 숫자가 여러개에 덱에 나눠져야만 최적이 되는 경우가 있는지를 생각해보면, 그런 경우는 없다는 것을 쉽게 알수 있다. [1,1,2,2]/[2,2,3,4] 와 같은식으로 덱을 만들수 있는 경우는 항상 [1,1,2,2,2,2]/[3,4] 로도 덱을 만들수 있다. 그러므로 각 덱에 포함될 숫자범위가 겹치지 않는 것만을 갖고 생각해도 최적값을 찾을수 있다. * 이제 각 덱에 들어가야할 숫자 범위를 그리디하게 정하자. 첫번째 덱이 최솟값부터 x까지의 숫자 범위를 갖고 나머지 덱들이 x+1부터 시작하는 숫자들을 커버한다고 할때, x를 가능한 크게 잡는것이 덱의 총 갯수를 줄이는 최적 방법이 된다. 엄밀한 증명을 안해도 직관적으로 쉽게 파악가능하다. 그러면 이제 덱에 넣어질수 있는 x의 최대값이 얼마인지만 찾으면 된다. * 세 수 a<b<c 가 있고, 그 숫자들의 인덱스가 i[a],i[b],i[c]라고 하면, i[a]<i[b] 이고 i[c]<i[b] 인 경우, 즉 c와 a가 b 보다 먼저 나오는 경우에는 이 세 수를 같은 덱에 넣을 수 없다. 이런 숫자쌍이 하나도 존재하지 않아야만 a,b,c를 모두 같은 덱에 넣을 수 있다. 이것을 잘 정리하면, [a,b-1] 범위를 덱에 넣을 수 있을때, b도 그 덱에 넣을수 있는지를 보기 위해서는 [a,b-1]범위에서 x<y 이고 i[y]>i[x]인 것중 가장 큰 i[y]를 유지하면서 i[b]<i[y]가 있는지를 체크하면 된다. 그런 경우에는 b부터 시작하는 새 덱을 만들어야 하고, 그렇지 않으면 i[y]값을 갱신하면서 b+1에 대해서 테스트하는 식으로 하면 된다. * 각 숫자에 대해서 가장 왼쪽에 등장하는 숫자의 인덱스와, 가장 우측의 등장하는 인덱스만 계산해서 저장해 놓으면, 각 숫자들에 대해서 새 덱을 만들어야 할지 여부를 O(1) 에 처리 가능하다. 따라서 이부분의 시간 복잡도는 O(m)이고 (m는 unique한 숫자의 갯수), 그 이전에 정렬 과정이 필요하므로 O(mlogm)이 필요하다. 그냥 m대신 n으로 쓰면 O(nlogn) ===== 코드 ===== <dkpr py> """Solution code for "BOJ 1624. 데크 소트". - Problem link: https://www.acmicpc.net/problem/1624 - Solution link: http://www.teferi.net/ps/problems/boj/1624 Tags: [Greedy] """ import collections import sys INF = float('inf') def main(): N = int(sys.stdin.readline()) nums = [int(sys.stdin.readline()) for _ in range(N)] left_and_right_pos = collections.defaultdict(lambda: (INF, 0)) for pos, num in enumerate(nums): l, r = left_and_right_pos[num] left_and_right_pos[num] = (min(l, pos), max(r, pos)) answer = 0 left_of_decreasing, right_of_increasing = None, INF for _, (l, r) in sorted(left_and_right_pos.items()): if right_of_increasing is None: if r < left_of_decreasing: left_of_decreasing = l else: right_of_increasing = r else: if l > right_of_increasing: right_of_increasing = r else: answer += 1 left_of_decreasing, right_of_increasing = l, None print(answer) if __name__ == '__main__': main() </dkpr> {{tag>BOJ ps:problems:boj:플래티넘_1}}
ps/problems/boj/1624.txt
· 마지막으로 수정됨: 2022/01/26 05:01 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로