[백준] (Python) A와 B

머리말

문제 링크

12904번: A와 B

이 문제를 선택한 이유

• 문제를 읽고 해석할 수 있는 능력(문해력)
• 반복문과 조건문을 적재적소에 활용하기
• 구현 문제 유형 연습

 

풀이

1) 잘못된 접근 방식 - 브루트 포스

• 처음에는 2가지의 연산이 존재하고 각각 결과론적으로 A를 추가하거나 B를 추가하거나 2가지이다.
• $n$ = (결괏값의 길이) - (초깃값의 길이)만큼의 경우의 수가 있으니 브루트 포스로 접근하면 되겠구나 싶었다.
• 결국 길이에 대한 2가지의 연산이므로 $2^{n}$을 생각하여 문제를 풀었다.

# =================== 브루트 포스 -> 시간 초과 =====================

# S와 T 입력
input_string = input().strip()
objective_string = input().strip()

# S와 T 사이의 길이 차이와, 그 차이에 따른 경우의 수 할당
len_difference = len(objective_string) - len(input_string)
cases = 2 ** len_difference

# 결괏값 초기화
result = 0

'''
000 <- 0
001 <- 1
010 <- 10
...
111
'''
for num in range(cases):
    # 경우의 수를 구하기 위해 이진법으로 전환하기 "0", "1", "10", ... , "111"
    binary_string = bin(num)[2:] # 0x0

    # 길이가 다르면 다른 만큼 앞에 "0" 채워 넣기 "0" --> "000"
    if len(binary_string) != len_difference:
        binary_string = "0" * (len_difference - len(binary_string)) + binary_string

    # 변환한 문자열 초기화
    translated_string = input_string

    # 이진수의 자리 반복
    for digit in binary_string:
        # 이진법을 조회하면서 0일 경우 연산 1을, 아닐 경우 연산 2를 실행
        if digit == "0":
            translated_string += "A"
        else:
            translated_string = translated_string[::-1] + "B"

    # 변환한 문자열이 목표한 문자열과 같으면 결괏값에 1을 할당
    if translated_string == objective_string:
        result = 1

print(result)

채점 결과(시간 초과)와 회고

표 맨 아래에 기록된 시간 초과... 기껏 힘겹게 풀었는데 시간 초과라니 김이 다 빠졌다.

하지만 이렇게 할 경우에는 결국 시간 초과가 뜬다. 그래서 다시 문제로 돌아가 보니, S의 길이와 T의 길이가 아래와 같았다.

(1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

내 풀이 방식이라면 $n$의 최댓값은 (1000 - 9) = 999이므로, 경우의 수가 $2^{999}$가 나올 것이다. 따라서 어떻게 하면 이를 해결할 수 있을까에 대해서 고민을 해 보았다.

2) 수정한 접근 방식 - 반대로 생각하기(Think Backwards)

• 앞서 말한 브루트 방식은 문제의 흐름을 초깃값에서 결괏값의 방향으로, 즉, 앞으로 생각하는(think forward) 방식이다.
• 반면에 결괏값에서 초깃값으로 거슬러 올라가는 "반대로 생각하기(think backwards)"는 어떨까.
• 끝에 A와 B가 추가되었다는 뜻은 반대로 결괏값 또한 각각의 조건을 반대로 하여 제거할 수 있다.
• 이러면 단순히 반복문 하나로 초깃값과 같은지 여부를 구할 수 있다.

default = list(map(str, input().strip()))
target = list(map(str, input().strip()))

while len(target) != len(default):
    if target[-1] == 'A':
        target.pop()
    elif target[-1] == 'B':
        target.pop()
        target = target[::-1]

if target == default:
    print(1)
else:
    print(0)

 

꼬리말

브루트 포스 선택 시 시간 초과의 여부 고민하자

• 만약에 일일이 경우의 수를 모두 대입하는 브루트 포스를 생각한다면, 주어진 변수의 길이와 반복문을 생각하자.

문제의 조건을 좀 더 유심히 읽자

• 곧바로 문제를 바로 푸는 습관은 당장에 도움이 될 것 같지만 장기적으로 보면 방향을 잘못 잡아 장기적으로 푸는 시간이 더 걸릴 수 있다.
• 주어진 입력 값의 범위 등 문제에 적힌 내용을 빠뜨리지 말고 보다 신중히 읽자.