백준 #12919 - [G5] A와 B 2 : 거꾸로 해결하기/예외처리

(python3)

12919번: A와 B 2

 

이 문제는 처음 떠올린 아이디어에 예외처리를 더해가면서 해결해서 재밌는 흐름이었습니다.

물론 모범답안은 매우 짧았지만요...ㅋㅋㅋ

 

시간 초과

첫 문자열 s, 두번째 문자열 t로 지칭합니다.

 

첫번째 접근으로는 s에서 파생될 수 있는 모든 경우의 수를 재귀로 탐색했습니다.

- 1, 2 선택지로 분기를 갈라서 재귀

- 모든 경우의 수에 대해 탐색

 

최악의 경우 O(2^50)이라 시간초과가 발생합니다.

 

이걸 조금 빨리 멈춰줄 수 있도록 A와 B 문자의 개수를 비교해주는 코드를 추가했지만 최악의 경우를 상쇄시킬 수 있는 방법이 아니라 특정 케이스에서 역시 시간초과가 발생했습니다.

def solution(input) :
    # 1, 2 선택지로 분기를 갈라서 재귀
    # 모든 경우의 수에 대해 해결
    # A,B의 개수를 세면서 s에 문자를 붙이는 방식으로 연산량을 조금 줄임

    s = input().rstrip()
    t = input().rstrip()
    cnta = t.count('A')
    cntb = t.count('B')


    def recur(s,t,cnta,cntb) :
        if len(s) >= len(t) :
            if s == t : return 1
            else : return 0
        else :
            if s.count('A') < cnta :
                ans1 = recur(s+'A',t,cnta,cntb)
                if ans1 :
                    return 1
            if s.count('B') < cntb :
                ans2 = recur(''.join(reversed(s+'B')),t,cnta,cntb)
                if ans2 :
                    return 1
            return 0
    
    print(recur(s,t,cnta,cntb))

input = sys.stdin.readline
solution(input)

 

재귀 없이 예외 처리로

방향을 완전히 바꿔서 패턴을 찾아보기로 했습니다.

성공 가능한 경우 t안에 s가 포함되어있어야하고, s 앞뒤로 붙는 B의 개수에 제한이 생깁니다. A는 일부 케이스를 제외하면 아무때나 붙일 수있다고 생각하고 진행했습니다. 이 일부 케이스를 예외 처리해줄 필요가 있었습니다.

 

1.

t의 부분으로 s가 포함되어있어야 합니다.

정순 s가 t의 부분으로 포함되어있다면 t에 포함된 s의 앞뒤로 B가 똑같은 갯수만큼 들어가있어야합니다. 짝수번 뒤집혔기 때문이죠.

역순 s가 t의 부분으로 포함되어있다면 s의 앞으로는 n+1개의 B가, 뒤로는 n개의 B가 존재해야합니다. 마지막으로 붙은 B에 의해 뒤집히면 앞쪽으로 B가 한개 더 많을 수 밖에 없습니다.

이 알고리즘에서는 다음과 같은 예외 케이스가 벌어질 수 있습니다.

AAA, ABAAA

알고리즘 상에서 t의 AAA 앞으로 B가 1개, 뒤로 0개라서 가능하다고 판별하겠지만 A는 앞으로 붙을 수 없기 때문에 문제가 생깁니다.

 

2.

B가 앞뒤로 한번이라도 등장하는 경우, (즉 한번이라도 뒤집힌 경우) t의 맨 앞에는 무조건 B가 올 수 밖에 없습니다.

여기까지 예외처리를 하고 나면 이런 예외 케이스가 생깁니다.

AAB, AAAB

앞뒤로 B가 한번도 오지 않았기 때문에 앞에 A가 올 수 있다고 판단하지만, 앞에 A가 추가로 붙을 수는 없어서 실패입니다.

 

3.

A가 맨 앞에 올 수 있는 경우는 B가 한번도 등장하지 않고 s가 t의 맨 앞에 위치할때 뿐입니다.

s = A...

s, sAAA...

위 조건까지 추가해주면 테케를 모두 통과할 수 있습니다.

import sys
def solution(input) :
    # 문자열 1의 번치를 2에서 다 찾는다.
    # 앞뒤로 붙는 b 갯수가 똑같아야한다.
    # 뒤집힌 문자열 1을 2에서 찾는다.
    # 앞에 붙는 b가 한개 더 많아야한다.
    # 예외 : AAA , ABAAA
    # B가 한개 이상 붙은 경우 t의 맨 앞에 A가 올 수 없다.
    # 예외 : AAB, AAAB
    # 맨 앞에 A가 올 수 있는 경우는 B가 추가되지 않고, t의 부분수열로 배치되는 s가 맨 앞이어야한다.

    s = input().rstrip()
    t = input().rstrip()

    # 1. 정순 s가 t의 부분인 경우를 탐색
    for i in range(len(t)-len(s)+1) :
        flag = 1
        for d in range(len(s)) :
            if s[d] != t[i+d] :
                flag = 0
                break
        if flag : # 정순 s가 t의 부분인 경우
            cnt1 = 0
            cnt2 = 0
            for f in range(i) : # 앞에 붙는 B의 개수 카운팅
                if t[f] == 'B' : cnt1+=1
            for f in range(i+len(s),len(t)) : # 뒤에 붙는 B의 개수 카운팅
                if t[f] == 'B' : cnt2+=1
            if cnt1 == cnt2 == 0 and i == 0: # B가 한번도 나오지 않고 t의 맨 앞에 s가 등장하는 경우 성공
                print(1)
                return
            elif cnt1 == cnt2 and t[0] != 'A' : # B가 한번 이상 등장, 앞뒤로 B등장 횟수가 같고, t의 맨 처음이 B가 아니면 성공
                print(1)
                return
                
    # 2. s의 역순이 t의 부분인 경우를 탐색
    s = ''.join(reversed(s))
    for i in range(len(t)-len(s)+1) :
        flag = 1
        for d in range(len(s)) :
            if s[d] != t[i+d] :
                flag = 0
                break
        if flag : # 역순 s가 t의 부분인 경우
            cnt1 = 0
            cnt2 = 0
            for f in range(i) : # 앞에 B 개수 카운트
                if t[f] == 'B' : cnt1+=1
            for f in range(i+len(s),len(t)) : # 뒤에 B 개수 카운트
                if t[f] == 'B' : cnt2+=1

            if cnt1 == cnt2+1 and t[0] != 'A' :  # B가 앞쪽에 1개 더 많고, 맨 앞이 A가 아니면 성공
                print(1)
                return
            
    print(0)

input = sys.stdin.readline
solution(input)

 

 

최단 시간 풀이 (정석 풀이)

짜잔~ A에 붙일게 아니라 B에서 역순으로 제거하면서 A와 같은지 확인하면 되는거였습니다~

import sys
def solution(input) :

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

    def rec(t) :
        if S == t :
            return 1
        if len(S) > len(t) :
            return 0
        if t[-1] == 'A' :
            ans = rec(t[:-1])
            if ans :
                return 1
        if t[0] == 'B' :
            ans = rec(t[1:][::-1])
            if ans :
                return 1
        return 0
    
    print(rec(T))
input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac