문제
구르미는 얼마전 새로 구매한 자동차를 타고 여행을 떠나려고 한다. 구르미는 운전 실력이 서툴러 운전을 할 때 여유가 없어지지만, 이번에 새로 구매한 자동차에는 현대모비스의 자율 주행 기술이 탑재되어 있어 운전의 부담이 훨씬 덜해졌다.
그래서 구르미는 운전할 때 노래를 들을 수 있을 만큼의 여유가 생겼고, 오랜만에 가는 여행이니 최고의 플레이리스트를 만들어 여행길을 가는 동안 노래를 만끽하고 싶다.
구르미는 총 개의 곡을 가지고 있으며, 이 중 일부 노래를 뽑아 여행 중 들을 플레이리스트를 만들려고 한다. 구르미의 여행길은 정확히
분이 걸리고, 구르미는 여행을 시작할 때 노래를 듣기 시작해서 목적지에 도착했을 때 딱 모든 노래의 재생이 끝나면 한다. 따라서, 구르미의 플레이리스트에 속한 노래의 재생 시간 합은 정확히
분이 되어야 한다.
또, 구르미는 비슷한 제목으로 시작하는 노래들을 연달아 듣는 걸 좋아하기 때문에, 플레이리스트에 속한 노래의 제목들의 공통 접두사 길이가 최대한 길었으면 한다. 이 때 어떤 문자열 의 맨 앞에서 시작해서 연속한 임의의
개 글자를 골라 새로운 문자열을 만든 것을
의 접두사라고 하며, 문자열들이 주어졌을 때 모든 문자열이 공통으로 포함하는 접두사를 공통 접두사, 그리고 그 중 가장 길이가 긴 것을 최장 공통 접두사라고 한다. 예를 들어, 문자열 "happy", "has", "hack" 이 주어졌을 때 "h", "ha"는 세 문자열의 공통 접두사지만 "hac", "hap"등은 공통 접두사가 아니다. 또, 세 문자열의 최장 공통 접두사는 "ha"가 된다.
정리하자면, 구르미가 만들 플레이리스트는 아래의 조건을 만족해야 한다.
- 같은 노래는 플레이리스트에 최대 한 번만 들어갈 수 있다.
- 플레이리스트에 속한 노래들의 재생 시간 합이 정확히
여야 한다.
- 플레이리스트에 속한 노래 제목들의 최장 공통 접두사 길이를 가능한 한 길게 만들어야 한다.
조건을 만족하는 경우가 여러가지라면, 플레이리스트에 속한 노래들의 최장 공통 접두사가 사전순으로 최소가 되게 만들고 싶다.
예를 들어, 구르미의 여행 시간은 총 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 한 곡으로 구성된 플레이리스트를 만들게 될 것이다.
구르미를 도와 이렇게 플레이리스트를 구성하는게 가능한지 판별하고, 가능하다면 조건을 만족하는 플레이리스트에 속한 노래들의 최장 공통 접두사를 출력하는 프로그램을 만들어보자.
입력
첫째 줄에 구르미가 가지고 있는 노래의 개수 과 여행 시간을 나타내는 정수
가 주어진다(
).
둘째 줄부터 줄에 걸쳐 구르미가 가진
번째 노래의 이름을 나타내는 문자열
와 해당 노래의 재생 시간을 나타내는 정수
가 주어진다(
). 노래의 이름은 영문 소문자로만 구성되어 있으며, 구르미가 가진 모든 노래의 이름 길이의 합은
을 넘지 않는다.
출력
첫째 줄에 조건을 만족하는 최대 공통 접두사의 길이와, 해당 접두사를 공백으로 구분하여 출력한다.
만약 조건을 만족하는 플레이리스트 구성 방법이 없다면, 을 출력하고 종료한다.
* 문제에 대한 힌트는 블로그에서 확인할 수 있습니다.
* 문제에 대한 질문은 Q&A에 남겨주세요!