목록정렬 (2)
Joonas' Note
파일 내용이 10GB가 되는 것은 어떻게 정렬할까? 메모리에 올릴 수 있는 크기가 한정되어 있기 때문에, 10GB 짜리의 큰 파일을 한번에 읽어서 quick sort 같은 인메모리(in-memory) 정렬을 할 수 없다. Linux/Mac에는 sort 라는 명령어가 있고, Windows에서는 git bash를 깔면 사용할 수 있다. 이미 있는 커맨드인지 모르고 python으로 직접 구현했다. 더보기 과정 메모리에 올릴 수 있는 만큼만 쪼개어서 올린 후, 각각을 정렬하고 다시 합친다. 여기서 "메모리에 올릴 수 있는 만큼"은 적당히 128MB로 설정했다. 이를 자세히 각 단계별로 쪼개면 이렇다. 준비 - 나눠 담을 크기를 계산 분리 - 큰 세그먼트 단위로 나누어 쪼개어 담는다. 정렬 - 쪼개진 각 파일을 ..
링크: https://www.acmicpc.net/problem/5052문제한 문자열이 다른 문자열의 접두어(prefix)이면 NO, 그런 경우가 없으면 YES를 출력하는 문제이다.풀이 1 (정렬)모든 문자열을 사전순으로 정렬하면, 접두어가 겹치는 문자열끼리 붙어있다.어떤 문자열이 직전 문자열의 부분 문자열인지 확인하면 된다.시간 복잡도는 정렬 + 부분 문자열 확인 시간만큼이므로, \(O(nlogn + n|s_{max}|)\)코드 1 (정렬) 풀이 2 (트라이; Trie)분류에 트라이가 있기도 하고, 트라이를 한번도 구현해본 적 없어서 트라이로 풀어봤다.문자열을 하나씩 확인하며 트라이를 만들어간다.어떤 문자열이 끊긴 지점에 "이 곳이 하나의 단어였다"로 리프 표시를 해두고 넘어간다.다음에 트라이를 만드는..