99클럽 코테 스터디 15일차 TIL / 자료구조(덱)&문자열

✏️ 문제

[백준/BOJ] 13417번: 카드 문자열(https://www.acmicpc.net/problem/13417)

 

N장의 카드가 일렬로 놓여있다. 각 카드에는 알파벳이 하나씩 적혀있다. 태욱이는 가장 왼쪽에 있는 카드부터 차례대로 한 장씩 가져올 수 있다. 가장 처음에 가져온 카드는 자신의 앞에 놓는다. 그다음부터는 가져온 카드를 자신의 앞에 놓인 카드들의 가장 왼쪽, 또는 가장 오른쪽에 놓는다. 태욱이는 모든 카드를 다 가져온 후에 자신의 앞에 놓인 카드를 순서대로 이어 붙여 카드 문자열을 만들려고 한다.

예를 들어 3장의 카드가 [M, K, U] 순으로 놓여있다고 하자. 태욱이는 먼저 가장 왼쪽에 있는 “M”이 적힌 카드를 가져와서 자신의 앞에 놓는다. 다음으로 남은 카드 중 가장 왼쪽에 있는 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 다시 가장 왼쪽에 두면 “UKM”이라는 문자열을 만들 수 있다. 만약 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 가장 오른쪽에 두면 “KMU”라는 문자열을 만들 수 있다. 이때, 태욱이가 만들 수 있는 문자열 중 사전 순으로 가장 빠른 문자열은 “KMU”이다.

N장의 카드에 적혀있는 알파벳의 처음 순서가 주어질 때, 태욱이가 만들 수 있는 카드 문자열 중 사전 순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 S3

✅ 소요 시간: 38분

✅ 권장 시간: 1시간 15분

 

💡 풀이

1) 문제 유형 파악

문제, 입출력 예시를 봤을 때 문자열 처리 유형이겠구나 싶었고 '가장 왼쪽에 있는 카드부터 차례대로 한 장씩 가져올 수 있다'는 부분에서 덱을 써먹을 수 있겠다는 생각이 들었다.

 

2) 아이디어 흐름

① 정렬?

사실 바로 덱을 떠올렸던 건 아니다. 처음에는 문제 슥 보고 '사전 순으로 가장 빠른 문자열'에 꽂혀서 입력 받은 알파벳 리스트를 정렬한 후 다 붙여서 출력하면 되지 않나? 라고 생각했다.

 

근데 ASDFG가 나와야 하는 예시랑 답이 달라서 문제를 다시 보게 됐고 '가장 왼쪽에 있는 카드부터 차례대로 한 장씩 가져올 수 있다'는 조건을 간과한 걸 깨달았다.

 

알파벳 리스트를 cards라고 할 때, 처음 고르는 카드는 무조건 cards[0]이다.

 

② ⭐ 덱 활용하기 ⭐

이 문제에서 덱을 활용하는 방법의 핵심은 '쓴 알파벳은 덱에서 빼주는 것'이고 popleft()를 이용해 이 부분을 구현할 수 있다.

 

먼저 처음 고르는 카드는 무조건 cards[0]이라고 했기 때문에 카드 리스트에서 cards.popleft()로 첫 카드를 빼주고 시작한다.

 

남아 있는 카드 리스트가 완전히 빌 때까지 while문을 도는데 이 때 덱의 첫 알파벳과 word의 첫 알파벳을 비교하여 덱에 있는 알파벳을 적절한 위치에 붙여준다. 덱의 첫 알파벳이 word의 첫 알파벳보다 앞서면 word의 왼쪽에 덱의 첫 알파벳을 추가하고 반대의 경우 word의 오른쪽에 덱의 첫 알파벳을 추가한다.

 

사용한 알파벳은 popleft()를 이용해 카드 리스트에서 바로 빼준다.

 

B A C A B A C

 

이 예제를 이용해 위의 과정을 확인해보자면 아래와 같다.

 

시작 카드: cards.popleft() = B

현재 단어: B

나머지 카드: A C A B A C

─

덱의 첫 알파벳: cards[0] = A

word의 첫 알파벳: B

현재 단어: AB (A가 B보다 앞서기 때문에 현재 단어의 왼쪽에 추가)

나머지 카드: C A B A C

─

덱의 첫 알파벳: cards[0] = C

word의 첫 알파벳: A

현재 단어: ABC(C가 A보다 뒷 순서기 때문에 현재 단어의 오른쪽에 추가)

 

덱이 빌 때까지 위 과정 반복!

 

3) 구현

from collections import deque

T = int(input())

for _ in range(T):
    N = int(input())
    
    cards = deque(list((input().split())))
    
    current_char = cards.popleft()
    
    word = current_char
    
    while cards:
        if cards[0] <= word[0]:
            word = cards[0]+word
        else:
            word += cards[0]

        cards.popleft()
        
    print(word)

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 어려웠던 점은 없지만 문제 좀 천천히/꼼꼼히 읽는 습관을 장착하자 제발 ⭐

❗ 배운 점

• 문자열도 부등호로 비교 가능함 → a < b이면 a가 b보다 사전순으로 앞선다는 뜻