99클럽 코테 스터디 4기 15일차 TIL - 백준: 카드 문자열(13417) Swift & Python

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	13417	카드 문자열	그리디	실버3	Swift, Python

🚀 나의 접근 방법

이 문제는 그리디 알고리즘과 덱 자료구조를 사용하면 쉽게 해결할 수 있다.

주의할 점은 주어진 알파벳을 단순히 사전 순으로 정렬하는 것이 아닌 제시된 행동에 의해서만 알파벳을 정렬할 수 있다.

행동 1. 가장 처음에 가져온 카드는 자신의 앞에 놓는다.
행동 2. 그다음부터는 가져온 카드를 자신의 앞에 놓인 카드들의 가장 왼쪽, 또는 가장 오른쪽에 놓는다.

그렇기 때문에 주어진 알파벳을 순서대로 방문하면서 지금 놓인 카드들(result 리스트)의 맨 앞에 값과 비교해서 작거나 같으면 맨 앞쪽에 놓는다. 아니라면 맨 뒤에 놓으면 된다.

이것이 가능한 이유는 프로그래밍 언어에서 대부분 알파벳은 아스키코드로 정의되기 때문이다. A는 아스키코드(10진수)로 65, B는 66으로 사전 순으로 했을 때 앞쪽 알파벳들이 더 작다.

✍️ 나의 코드

Swift

let T = Int(readLine()!)!

for _ in 0..<T {
    let N = Int(readLine()!)!
    let alphabet = readLine()!.split(separator: " ")
    var result: [String] = []
    for al in alphabet {
        let a = String(al)
        if result.isEmpty {
            result.append(a)
            continue
        }
        if result.first! >= a {
            result.insert(a, at: 0)
        } else {
            result.append(a)
        }
    }
    print(result.joined())
}

Python

T = int(input())

for _ in range(T):
    N = int(input())
    alphabet = input().split(" ")
    result = []
    for a in alphabet:
        if len(result) == 0:
            result.append(a)
            continue
        if result[0] >= a:
            result.insert(0, a)
        else:
            result.append(a)
    print("".join(result))

🤔