[파이썬, 스위프트][백준 12904][💛골드 5] (그리디, 구현)

🧞‍♂️ 난이도

💛 골드 5

🧞‍♂️ 문제

https://www.acmicpc.net/problem/12904

🧞‍♂️ 내 풀이 ⭕

처음에는 백트래킹으로 푸는건줄 알았는데 알고보니까 S 로 T를 만드는것이 아니라, T로 S 를 만드는 방법이 있었다.

그러면 그리디의 특징을 이용할 수 있다. 왜냐하면 T 로 S를 만들때는 마지막 글자가 A 인지 B 인지에 따라 pop() 만 할지 아니면 reverse 도 할지 결정을 할 수 있다.

🧞‍♂️ 배운점

가끔 반대로 발상을 바꿔줘야한다. 작은것에서 큰것을 만드는게 아니라 큰것에서 작은걸로

---

🧞‍♂️ 파이썬 풀이

import sys
input = sys.stdin.readline

S = list(input().rstrip())
T = list(input().rstrip())

while len(S) != len(T):
    if T[-1] == 'A':
        T.pop()
    else:
        T.pop()
        T = T[::-1]

if S == T:
    print(1)
    exit(0)
else:
    print(0)

🧞‍♂️ 스위프트 풀이

var S = readLine()!.compactMap { String($0) }
var T = readLine()!.compactMap { String($0) }

while S.count != T.count {
    if T.last == "A" {
        T.removeLast()
    } else {
        T.removeLast()
        T = T.reversed()
    }
}
var answer = 0
if T == S {
    answer = 1
}
print(answer)

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기