[BOJ #13417] 카드 문자열

BOJ #13417, 카드 문자열 문제입니다.

처음에 C로 짜다가 입력 버퍼 관련 문제가 발생해서 한참 헤맸습니다만 Python으로 짜니까 바로 해결했습니다. 입력 버퍼 비우는 테크닉을 알고 있었는데 왜인지 잘 기억이 안 났었네요. 그리고 아직도 왜 안 되는지 모르겠습니다. 구글링도 열심히 하면서 해결하려고 해 보았으나 나중에 다시 시도해보기로 했습니다.

 

이 문제의 예제에서는 너무나 쉬운 testcase만을 제시하기 때문에, 혼자서 여러 가지 testcase를 만들어서 시험해봐야 합니다. 그리고 bit mask를 이용한 brute force도 문제의 입력 조건 상 시간이 부족하기 때문에 불가능하며 따라서 연역적인 과정을 통해 답을 도출할 수 있어야 합니다. (brute force의 범위를 좁히는 것이 권장되는 풀이일 수도 있겠습니다만 저는 연역적으로 풀었습니다.)

 

대부분의 프로그래밍 언어들에서는 ascii code 기준으로 문자(또는 문자열)의 순서를 판단하므로 이 문제는 숫자 정렬 문제와 동일하게 생각할 수 있습니다.

 

저는 제가 만든 여러 가지 testcase들을 탐구해 보았고, greedy algorithm을 적용해서 풀 수 있겠다는 결론에 도달했습니다. 저는 greedy algorithm을 적용하기 위해 '최소 문자'를 저장했습니다. 이 '최소 문자'를 통해 문자를 왼쪽에 붙였을 때와 오른쪽에 붙였을 때 중 어느 쪽이 사전 순으로 더 빠른지 판단할 수 있게 됩니다.

 

예를 들어 4 2 3 1 5의 입력이 들어왔다고 합시다. 4로 시작해서 2 4의 상태가 될 것입니다. 여기서 3의 위치를 선택해야 하는데, 만약 왼쪽에 붙인다면 3 2 4가 되어 기존보다 사전에서 느린 순서가 됩니다. 물론 이 다음의 1을 왼쪽에 붙이면 1 3 2 4가 되어 사전에서 빠른 순서가 되긴 합니다만, 그럴 바에야 3을 뒤에 붙이고 1을 왼쪽에 붙여 1 2 4 3으로 만드는 것이 사전에서 더 빠른 순서를 차지할 수 있습니다. 따라서, 우리는 '최소 문자'보다 더 빠른 문자만을(정확히는 더 빠르거나 같은 문자만을 - 왜냐하면 '최소 문자'를 중첩하는 것이 사전에서 빠른 순서가 되는 데에 유리하기 때문입니다.) 왼쪽에 붙이고 그 이외는 뒤에 붙여야 한다는 것입니다.

 

코드 첨부합니다. 다른 분들의 메모리나 시간 경과를 봤을 때 추후에 더 수정해 볼 예정입니다.

T = int(input(''))

for i in range(T):
    N = int(input(''))
    card_list = input('').split()

    min_card = card_list[0]
    res_list = [card_list[0]]

    for j in range(1, N):
        if min_card >= card_list[j]:
            min_card = card_list[j]
            res_list.insert(0, card_list[j])
        else:
            res_list.append(card_list[j])

    for j in range(N):
        print(res_list[j], end='')
    print()