[백준 1294번] 문자열 장식

mokomoko·2022년 11월 17일

1. 문제

오민식은 단어 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

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

제한사항

시간 : 1초
메모리 : 128MB

키워드

우선 순위 큐를 커스터마이징해보자!

2. 풀이

이 문제를 처음 풀었을 때는 갖가지 예외사항때문에 골머리를 썩었다.

어찌저찌 로직은 구현했지만 시간초과가 났다.

이유는 최악의 상황일 경우 계속해서 정렬을 돌리기 때문에 시간초과가 날 수밖에 없었다.

어떻게 할까 고민하다가 다른사람들의 풀이를 보던 중 우선순위 큐를 커스터마이징하는 방법을 찾았다.

로직 자체는 두 문자열을 합치는 순서에 따라 우선순위 큐에 넣는 것이다.

그리고 사전적으로 가장 앞에있는 문자열의 첫번째 문자를 꺼내고

다시 우선순위 큐 안에 넣는다

ex) s1 = ABC, s2 = BCD가 있다면

ABCBCD (s1+s2) 와 BCDABC (s2+s1) 가 있다.

이 중 사전적으로 앞에있는것은 ABCBCD이므로 ABC가 BCD보다 앞에 있다.

3. 소스코드

# python
import sys
import heapq

input = sys.stdin.readline

class string:
	def __init__(self,s):
		self.s = s

	def __lt__(self,other): // 이 부분이 커스텀 하는 부분
		if self.s + other.s < other.s + self.s: // s1+s2 < s2+s1 오름차순 정렬
			return True
		else:
			return False

	def getString(self):
		return self.s

def solution():
	answer = ""
	words = []
	for _ in range(int(input())):
		# heapq.heappush(words,string('A'*1000)) // 이걸로 테스트해보는 것을 추천!
		heapq.heappush(words,string(input().strip()))
	while words:
		s = heapq.heappop(words).getString()
		answer += s[0]
		if len(s) > 1:
			heapq.heappush(words,string(s[1:]))
		
	return answer

if __name__ == "__main__":
	print(solution())