[baekjoon] 백준 2138번(파이썬): 스위치

문제

2138번: 전구와 스위치

- N개의 스위치와 N개의 전구가 있다.

- 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다.

- i(1 <i <N) 번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다.

- 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다.

- 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

- N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 문제이다.

- 자연수 N(2≤N≤100,000)이 주어진다.

- 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다.

- 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다.

- 불가능한 경우에는 -1을 출력한다.

알고리즘

- 전구 스위치에 상태를 확인할 함수와 전구의 상태를 바꿔줄 함수를 만든다.

- 첫 번째 전구의 스위치는 첫 번째 전구와 이후에 전구의 상태만을 바꾸므로 다음 2가지 경우로 나눈다.

- 첫 번째 전구를 켰는지와 안 켰는지를 나누어 문제를 수행한다.

- 이후부터는 이전 전구를 확인하면서 전구의 상태를 바꿔준다.

- 이후 전구는 마지막 전구가 아니라면 바꿔준다.

- 현재 전구와 바꿔야 하는 전구가 똑같으면 멈춰주고 카운트를 리턴한다.

- 그렇지 않다면 현재 전구를 바꿔야 하는 전구로 바꾸지 못하는 것을 의미하며 -1을 출력한다.

코드

import sys


# 전구의 상태 바꿈
def switch_button(num):
    if num == 0:
        num = 1
    else: num = 0

    return num


# 전구 스위치
def switch(state, cnt):
    # 첫번째 전구 스위치를 눌렀을 때 첫번째 전구와 두번째 전구의 상태를 바꿔준다.
    if cnt == 1:
        state[0] = switch_button(state[0])
        state[1] = switch_button(state[1])
    # 반복문을 통해 전구의 상태를 확인한다.
    for i in range(1, n):
        # 스위치 이전에 전구의 상태와 바꿔야하는 전구의 상태를 비교
        if state[i-1] != after[i-1]:
            cnt += 1
            # 이전 전구와 스위치 전구의 상태를 바꾼다.
            state[i-1] = switch_button(state[i-1])
            state[i] = switch_button(state[i])

            # 스위치 이후에 전구가 있다면 이후 전구의 상태를 바꾼다.
            if i != n-1:
                state[i+1] = switch_button(state[i+1])

    # 현재 전구의 상태와 바꿔야하는 전구의 상태가 같으면 멈춘다.
    if state == after:
        return cnt

    # 바꿔야하는 전구의 상태로 바꾸지 못하므로 -1 출력
    else:
        return -1

n = int(sys.stdin.readline())
now = list(map(int,sys.stdin.readline().rstrip("\n")))
after = list(map(int,sys.stdin.readline().rstrip("\n")))

res1 = switch(now[:], 0) # 첫번째 전구 스위치를 안누르고 시작한 경우
res2 = switch(now[:], 1) # 첫번째 전구 스위치를 누르고 시작한 경우

# 2가지 조건으로 했을 때 더 작은 횟수를 출력
if res1 >= 0 and res2 >= 0:
    print(min(res1, res2))
    
# 0보다 큰 횟수를 출력
elif res1 >= 0 and res2 < 0:
    print(res1)
elif res1 < 0 and res2 >= 0:
    print(res2)
    
# 둘다 0보다 작기때문에 -1 출력
else:
    print(-1)

github

junjange/CodingTest