99클럽 코테 스터디 15일차 TIL: 그리디 정석

오늘의 문제: 13417. 카드 문자열

카드를 순서대로 순회하여 가장 사전 순으로 빠르도록 만드는게 미션이다. 문제는 딱 봐도 그리디인 것으로 보이고, 이제 아이디어를 떠올려야 한다.

아이디어: 순회하며 만나는 대로 판단하여 배치한다

그냥 단순하게 하나하나 돌면서, 맨앞에 있는 것과 비교하여 빠르면 앞으로, 아니면 뒤로 보내는 작업을 한다. 이유는 단순히 느릴 경우 앞으로 보내는게 손해가 되기 때문이다. 정말 그리디에 충실한 해결 방법인듯.

from collections import deque
t=int(input())
for i in range(t):
    n=int(input())
    l=input().split()
    r=deque()
    r.append(l[0])
    del l[0]
    for i in l:
        if r[0]<i: r.append(i)
        else: r.appendleft(i)
    print(*r,sep="")

진짜로 이 방법이 맞았다. 이게 왜 실버3인지는 나도 모르겠지만 그래도 그리디로 이를 증명하는게 쉽지 않나보다. 결국 모든 상황에서 이득이 되는 선택을 하여 전체가 이득이 된다는 사실 하나만 붙잡고 가서 풀었다.

오늘의 회고

어렵고 한번쯤은 틀릴 줄 알았는데 한번에 맞춰서 오히려 당황했다. 확실히 그리디는 판단의 근거를 빨리 떠올리는 게 중요해보인다.