[Python] BOJ(백준) 1294번 - 문자열 장식

링크

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

난이도

플래티넘2

풀이

cmp_to_key를 좀 더 딥하게 사용해보는 문제를 찾아보다가 발견한 문제다.

핵심 아이디어는, 처음에 cmp_to_key로 제일 먼저 위치한 문자열 내의 문자를 하나씩 빼주면서 그때마다 다시 한 번 cmp_to_key를 진행하는 것이다. 매번 이렇게 진행하는 것이 답인 이유는, 단어를 어떻게 잘라야 하는지에 대한 설명이 없으므로(문제에서는 적절히 쪼갠다고 했으므로, 완전히 임의라고 봐야한다) 결국 모든 케이스마다 제일 앞에 나오는 값을 넣음으로써 해결할 수밖에 없기 때문이다.

 

아이디어가 문제였을 뿐.. 구현은 어렵지 않았다. temp라는 빈 문자열을 두고 cmp_to_key로 sort한 arr에 대해 첫번째 값을 빼주고 제일 앞 글자를 제외한 값을 다시 넣어주고 다시 cmp_to_key로 sort하는 과정을 '이 빈 문자열 temp의 길이가 기존의 arr의 길이와 같아질 때'까지 반복하는 것이다.

 

그런데, 이 글을 쓰다가 어차피 하나씩 빼주면서 다시 한 번 sort를 할 것이라면 굳이 cmp_to_key를 쓸 필요가 있을까? 싶었는데

2
BAC
BACA

이 케이스를 보면 그냥 sort를 하면 ['BAC', 'BACA']를 하는 반면 cmp_to_key를 사용하면 사전순으로 하나하나 값이 바뀔 때마다 다시 한 번 진행하기 때문에 A가 C보다 사전순으로 앞에 위치하게 되어 ['BACA, BAC']의 형태로 sorting이 된다. 실제로 답도 전자는 BABACCA(CA가 C보다 뒤에 있게 되지만, A가 C보다 앞에 위치해야 하므로 틀림), 후자(정답)는 BABACAC가 된다.