https://www.acmicpc.net/problem/1294
문제요약
- 단어 N개로 문자열 W를 만듬 (N 20, W 1000)
- 단어를 순서를 유지하며 쪼갤 수 있음.
- 사전 순으로 가장 앞서는 것 구하기
접근법
- 단어를 한 글자로 다 쪼개놓고 시작
- 단어 각각을 리스트로 생각하고, 리스트의 앞의 글자중 가장 작은 글자를 뽑아서 단어를 구성하는 방식으로 접근
- 직관적이고, 될 것 같지만 예외가 발생함
- 동일한 우선순위를 갖는 경우 어디에서 가지고 올 것인가?
- ex) C CA ==> 우선순위 처리가 안되면 CCA도 가능하고 CAC도 가능해짐
- 고민하다보면 단어의 길이가 다를때 처리를 고민하게 됨
- 교환해서 앞서는 것을 먼저 가지고 오는 전략을 택함
- 그런데 다른 접근법으로는 단어의 가장 끝에 임의의 문자("~"와 같은)를 넣고 처리해도 됨