[백준] 12904번 A와 B (Python)

고승우·2023년 3월 20일
0

알고리즘

목록 보기
36/86
post-thumbnail

백준 12904번 A와 B

그리디알고리즘을 활용한 문제였다. 솔루션은 금방 찾아냈지만 아쉬웠던 점이 있다.

  1. 시간 복잡도를 고려하여 너무 복잡하게 해결했다.
  2. 문자열의 변환은 새로운 객체를 만들고 복사하는 과정이 있어 이를 지양하는 것이 좋지만 알고리즘 문제를 해결하는 것에 있어서는 큰 영향이 없다.
  3. 예외 케이스를 고려하지 않아 시간을 낭비했다.

내 코드는

import sys

s1 = sys.stdin.readline().strip()
s2 = sys.stdin.readline().strip()
l = len(s2) - len(s1)
lp = 0
rp = len(s2) - 1
ptr = rp
for _ in range(l):
    if ptr == rp:
        if s2[ptr] == "B":
            rp -= 1
            ptr = lp
        elif s2[ptr] == "A":
            rp -= 1
            ptr = rp
        else:
            print(0)
            sys.exit()
    else:
        if s2[ptr] == "B":
            lp += 1
            ptr = rp
        elif s2[ptr] == "A":
            lp += 1
            ptr = lp
        else:
            print(0)
            sys.exit()
if ptr == rp and s2[lp : rp + 1] == s1:
    print(1)
elif ptr == lp and s2[lp : rp + 1][::-1] == s1:
    print(1)
else:
    print(0)

가장 깔끔한 솔루션은

import sys

T = sys.stdin.readline().strip()
S = sys.stdin.readline().strip()
while len(S) > len(T):
        if S[-1] == "A":
            S = S[:-1]
        elif S[-1] == "B":
            S = S[:-1][::-1]
        else:
             print(0)
             exit()
if S == T:
     print(1)
else:
     print(0)
profile
٩( ᐛ )و 

0개의 댓글