[백준] 2138번 전구와 스위치 (python)

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

2138번: 전구와 스위치

 

일단 이 문제는 1080번 행렬 문제와 비슷하다.

문제에서 최소 횟수를 요구하고 있기 때문에 한 번 바꿔준 애는 다시 바꿔주면 안 되겠다는 생각이 들었다. 현재 전구 상태가 원하는 전구 상태와 같으면 그냥 넘어가고, 아니면 눌러주는 방식으로 구현하고자 했다. 하지만 이렇게 풀면 예제를 틀린다.

 

예제에서는 000을 010으로 바꾸고 싶어 하는데, 내가 말한 대로 풀게 되면 0번 인덱스는 똑같기 때문에 그냥 넘어가고 1번 인덱스에서 눌러버려 111 -> 100 이 돼버린다. 때문에 0번 인덱스를 눌러주는 경우와, 눌러주지 않는 경우로 나누어서 생각해야 된다. 앞서 말한 예외 상황이 있기 때문에 0번 인덱스가 이미 같아도 눌러주는 경우를 생각해야 된다.

 

문제 풀이

• 먼저 0번 인덱스를 누르지 않는 경우를 계산한다. 이때 중요한 게 현재 전구 상태 리스트를 copy 해준다. 입력받은 전구 상태를 그대로 사용할 경우 0번 인덱스를 누르고 시작하는 경우를 계산해 줄 수 없기 때문이다.
• 0번 인덱스부터 탐색하면서 원하는 전구 상태와 같지 않을 경우 스위치를 누른다. 스위치를 한 번 누를 때마다 카운트 해준다.
• 마지막 인덱스까지 다 확인한 후, 최종 상태가 원하는 상태와 같지 않은 경우 answer에 1e9를 대입한다. (-1을 넣을 경우 최소 횟수보다 더 작기 때문에 잘못된 답을 출력한다.)
• 다음으로 0번 인덱스를 누르고 시작하는 경우를 계산한다. 여기서는 입력받은 전구 상태를 그대로 사용했다. 또 사용할 일이 없기 때문이다.
• 앞과 똑같이 전구 상태가 다르면 스위치를 눌러주고, 탐색이 끝나면 현재 전구 상태와 원하는 전구 상태를 비교한다.
• 최종 결과는 0번 인덱스를 누르지 않고 계산한 경우의 결과와 0번 인덱스를 누르고 계산한 경우의 결과 중 더 작은 값이다. 만약 더 작은 값이 1e9인 경우에는 -1을 출력하면 된다.

 

정답 코드

지저분해서 리팩토링 하고 싶다.

import sys
input = sys.stdin.readline

n = int(input())
switchs = list(map(int, input().strip()))
want = list(map(int, input().strip()))

def change(switchs, index):
    if index == 0:
        switchs[index] = 1 - switchs[index]
        switchs[index+1] = 1 - switchs[index+1]
    
    elif index == len(switchs) - 1:
        switchs[index] = 1 - switchs[index]
        switchs[index-1] = 1 - switchs[index-1]
    
    else:
        switchs[index] = 1 - switchs[index]
        switchs[index-1] = 1 - switchs[index-1]
        switchs[index+1] = 1 - switchs[index+1]

# 0번 인덱스를 누르지 않는 경우
answer_1 = 0
answer_1_switch = switchs.copy()
for index in range(1, len(switchs)):
    if answer_1_switch[index-1] != want[index-1]:
        change(answer_1_switch, index)
        answer_1 += 1

if answer_1_switch != want:
    answer_1 = 1e9

# 0번 인덱스를 누르는 경우
answer_2 = 1 # 0번 인덱스를 누르고 시작하기 때문에 answer_2는 1로 선언한다.
change(switchs, 0) # 0번 인덱스 눌러주기
for index in range(1, len(switchs)):
    if switchs[index-1] != want[index-1]:
        change(switchs, index)
        answer_2 += 1

if switchs != want:
    answer_2 = 1e9

result = min(answer_1, answer_2)
print(result if result != 1e9 else -1)