백준 16719 ZOAC (숏코딩 1등풀이)

일단 문제를 접근할때 정방향으로 접근하는게 조금 막막하다는 생각이 들었다.
그래서 입 출력 예시를 조금 살펴봤는데

밑에서 부터 거꾸로 보면 한글자씩 빼보면서 그 녀석들중 가장 사전순으로 먼저 오는 문자열을 골라서 출력하면 되겠다는 생각이 들었다.
예를들어서
STARTLINK이면
[TARTLINK,SARTLINK,STRTLINK,...,STARTLIN] 중에서 사전순으로 가장 먼저오는 문자열을 골라낸다는 것이다.

이렇게 푼다면 대략 O(n logn) 나오기 때문에 시도할만한 풀이라고 생각했다.

맨처음 풀어낸 코드

a=[]
def rec(s):
    if not a : a.append(s)
    if len(s)==1 : return
    ns = min([s[:i]+s[i+1:] for i in range(len(s))])
    a.append(ns)
    rec(ns)
rec(input())
print(*a[::-1],sep='\n')

나쁘지 않은 코드라고 생각하는데 몇차례의 과정을 거쳐서 숏코딩 버전으로 변환해보았다.

숏코딩

a=[]
def rec(s):
    if not s : return
    a.insert(0,s)
    rec(min(s[:i]+s[i+1:] for i in range(len(s))))
rec(input())
print(*a)

무려 69B나 겉어냈다.
[사용된 기법]

• 빈문자열인지 확인하기 위해서 not s 라는 구문을 사용했다.
• 맨처음에는 a 리스트에 정방향으로 넣고 거꾸로 돌려서 출력했는데 insert를 이용해 삽입하고 정방향으로 출력함으로서 바이트 수를 많이 줄였다.
  만약에 a에 삽입연산이 많이 필요한 문제라면 insert를 사용할때 성능저하가 일어날 수 있는데 이 문제에서는 많아봤자 100번이므로 그냥 사용했다.
• 파이썬에서 최소값을 동적으로 구할때 min 함수안에 리스트를 넣어서 많이 사용하는데 사실 리스트 형태로 전달할 필요가 없다. 그냥 for문만 넣어주면 알아서 계산해준다.
• 리스트를 출력할때 join 함수를 사용할 필요없이 앞에 *를 달아주면 스페이스바를 기준으로 출력해준다.
  문제에서 출력예시는 문자열 사이에 줄바꿈이 있어야 할것처럼 보이는데 백준에서는 줄바꿈이랑 스페이스바랑 차이가 없다. 그렇기 때문에 굳이 sep='\n'를 넣어줄 필요가 없다.