[백준/1294] 문자열 장식 (Python)

https://www.acmicpc.net/problem/1294

Problem : https://www.acmicpc.net/problem/1294

1294번: 문자열 장식

Status : Solved

Time : ??????

 

---

 

문제 설명

 

오민식은 단어 N개를 이용해서 문자열 W를 만들려고 한다.

일단 오민식은 각각의 문자열을 적절히 쪼갠다. 그 다음에 쪼갠 문자열을 모두 이어붙여서 W를 만든다. 단, 한 문자열을 쪼개서 나온 조각의 순서는 유지해야 한다.

예를 들어, 오민식이 {YOUNGSIK, DONGHO, BAEKJOON} 총 3개를 가지고 있었다면, 오민식은 자기 마음대로 {YOUNG, SIK, DO, NG, HO, BA, E, K, JOO, N}과 같이 쪼갠 다음, 아래와 같이 YOUNGDOBAESIKNGKJOOHON을 만들 수 있다.

YOUNG     SIK
     DO      NG    HO
       BAE     KJOO  N
----------------------
YOUNGDOBAESIKNGKJOOHON

오민식이 만들 수 있는 문자열 중에 사전순으로 가장 앞서는 것을 출력하시오.

 

입력 및 출력

 

입력 

첫째 줄에 단어의 개수 N이 주어진다. N은 최대 20이다. 둘째 줄부터 N개의 줄에 단어가 주어진다. 단어는 최대 1,000글자이고, 공백은 없이 알파벳 대문자로만 구성되어 있다.

 

출력

문제의 오민식이 만들 수 있는 문자열 중에 사전순으로 가장 앞서는 것을 출력한다.

 

---

 

풀이

꽤 오래 걸린 문제였고, 간단해 보이지만 고려해야 할 상황이 많았다.

모든 문자열은 문자 단위로 순서만 지키면 되므로, 문자 단위로 그리디하게 정렬하면 된다. 나는 여기에 머지 소트(merge sort)방식을 조금 가미했다. 완성된 부분 문자열들로 다시 조건을 만족하는 문자열을 만들고, 이를 재귀적으로 시행해나가는 방식이다.

여기서 처음으로 고려해야 할 것은 문자열이 사전순으로 가장 앞서야한다는 점이다. 따라서 2개의 문자열에서 문자 하나를 뽑아쓸 때, 사전순으로 앞서는 문자열을 기준으로 뽑아 써야 한다. 이를테면

CB

AB

문자열은 사전순으로 정렬 후 뽑게 되면 'ABCB'라는 결과를 가져온다. (CB,B) -> (CB, ) -> (B, ) -> ( , )

 

여기서, 추가적으로 다음과 같은 예외 상황을 고려해야 한다.

BA

BAA

이 경우는 BA가 BBA보다 사전순으로 앞서므로 BA의 문자열을 처음 사용하게 되고, 'BABAA'라는 결과를 도출한다. 하지만 정답은 'BAABA'가 되므로 틀린 답이 된다. 이 경우-한 문자열이 다른 문자열보다 짧고, 짧은 문자열과 긴 문자열의 앞부분이 동일할 경우-에 한해서는 문자열 길이가 더 긴 쪽이 앞서도록 해야 한다.

나는 우선 두 문자열을 길이 순으로 정렬하여, 만약 두 문자열을 비교하여 위의 예외 상황에 해당되는 케이스를 반영하는 코드를 구성하였다. 이를 최종적으로 구현한 코드는 다음과 같다 :

 

풀이 코드

N = int(input())

str_list = [input().strip() for _ in range(N)]

def merge(n, lst) :
  if n == 0 :
    return ''
  if n == 1 :
    return lst[0]

  mid = n // 2
  str1 = merge(mid, lst[:mid])
  str2 = merge(n - mid, lst[mid:])
  result = ''

  while str1 or str2 :
    if len(str1) < len(str2) :
      str1, str2 = str2, str1
    if str2 == '' :
      result += str1
      break
    if str1 == '' :
      result += str2
      break
    if str2 < str1[:len(str2)] :
      result += str2[0]
      str2 = str2[1:]
    else :
      result += str1[0]
      str1 = str1[1:]

  return result

print(merge(N, str_list))

풀이 완료!