목차
※ 쉽고 명확하게 풀이하실 수 있도록 문제 지문을 일부 수정했습니다. 실제 경진대회 문제 지문과 차이가 있는 점 참고 부탁드립니다.
언어별 메모리 제한/수행시간 제한(공통 적용)
- C/C++
메모리제한 512MB, 수행시간 2초
- Java
메모리제한 512MB, 수행시간 4초
- Python3
메모리제한 512MB, 수행시간 10초
Q2. 플레이리스트 만들기
알고리즘
- Trie
문제
구르미는 얼마 전 새로 구매한 자동차를 타고 여행을 떠나려고 한다. 구르미는 운전 실력이 서툴러 운전을 할 때 여유가 없어지지만, 이번에 새로 구매한 자동차에는 현대모비스의 자율 주행 기술이 탑재되어 있어 운전의 부담이 훨씬 덜해졌다.
그래서 구르미는 운전할 때 노래를 들을 수 있을 만큼의 여유가 생겼고, 오랜만에 가는 여행이니 최고의 플레이리스트를 만들어 여행길을 가는 동안 노래를 만끽하고 싶다.
구르미는 총 N( 1 ≤ N ≤ 10^4)개의 곡을 가지고 있으며, 이 중 일부 노래를 뽑아 여행 중 들을 플레이리스트를 만들려고 한다. 구르미의 여행길은 정확히 K( 1 ≤ K ≤ 2 * 10^3)분이 걸리고, 구르미는 여행을 시작할 때 노래를 듣기 시작해서 목적지에 도착했을 때 딱 모든 노래의 재생이 끝났으면 한다. 따라서, 구르미의 플레이리스트에 속한 노래의 재생 시간 합은 정확히 K분이 되어야 한다.
또, 구르미는 비슷한 제목으로 시작하는 노래들을 연달아 듣는 걸 좋아하기 때문에, 플레이리스트에 속한 노래 제목들의 공통 접두사 길이가 최대한 길었으면 한다. 이때 어떤 문자열 s의 맨 앞에서 시작해서 연속한 임의의 x개 글자를 골라 새로운 문자열을 만든 것을 s의 접두사라고 하며, 문자열들이 주어졌을 때 모든 문자열이 공통으로 포함하는 접두사를 공통 접두사, 그리고 그중 가장 길이가 긴 것을 최장 공통 접두사라고 한다. 예를 들어, 문자열 “happy”, “has”, “hack”이 주어졌을 때 “h”, “ha”는 세 문자열의 공통 접두사지만 “hac”, “hap”등은 공통 접두사가 아니다. 또, 세 문자열의 최장 공통 접두사는 “ha”가 된다.
정리하자면, 구르미가 만들 플레이리스트는 아래의 조건을 만족해야 한다.
- 같은 노래는 플레이리스트에 최대 한 번만 들어갈 수 있다.
- 플레이리스트에 속한 노래들의 재생 시간 합이 정확히 K여야 한다.
- 플레이리스트에 속한 노래 제목들의 최장 공통 접두사 길이를 가능한 한 길게 만들어야 한다.
조건을 만족하는 경우가 여러 가지라면, 플레이리스트에 속한 노래들의 최장 공통 접두사가 사전 순으로 최소가 되게 만들고 싶다.
예를 들어, 구르미의 여행 시간은 총 40분이고, 구르미는 아래의 7개 곡을 가지고 있다고 하자.
- liveforever : 16분
- happyending : 22분
- liveyoung : 24분
- happening : 18분
- liveforsomeone : 19분
- liveforyou : 5분
- goormio : 40분
이중 liveforever, liveyoung을 뽑아서 플레이리스트를 만드는 경우 총길이가 40분이므로 조건을 만족하고, 이때 최장 공통 접두사는 live가 된다.
그 외에도 liveforever, liveforsomeone, liveforyou를 뽑아서 플레이리스트를 만드는 것도 가능한데, 이때 최장 공통 접두사는 livefor가 된다. 그리고 이 경우가 조건을 만족하는 플레이리스트 중 최장 공통 접두사의 길이가 가장 긴 경우이다.
하지만 goormio 한 곡만으로도 조건을 만족하게 플레이리스트를 구성할 수 있고, 이때 최장 공통 접두사는 goormio가 된다. 이 경우가 위의 플레이리스트와 최장 공통 접두사의 길이는 동일하나 사전 순으로 goormio가 livefor보다 앞서기 때문에, 구르미는 goormio 한 곡으로 구성된 플레이리스트를 만들게 될 것이다.
구르미를 도와 이렇게 플레이리스트를 구성하는 게 가능한지 판별하고, 가능하다면 조건을 만족하는 플레이리스트에 속한 노래들의 최장 공통 접두사를 출력하는 프로그램을 만들어보자.
