[파이썬] [그리디] 백준 2138 전구와 스위치

문제

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

2138번: 전구와 스위치

코드

import sys
import copy

input = sys.stdin.readline

n = int(input())
array = list(map(int, list(input().rstrip())))
target = list(map(int, list(input().rstrip())))


def change(i):
    if i == 0:
        if temp[i] == 1:
            temp[i] = 0
        else:
            temp[i] = 1
        if temp[i + 1] == 1:
            temp[i + 1] = 0
        else:
            temp[i + 1] = 1
    elif i == n - 1:
        if temp[n - 1] == 1:
            temp[n - 1] = 0
        else:
            temp[n - 1] = 1
        if temp[n - 2] == 1:
            temp[n - 2] = 0
        else:
            temp[n - 2] = 1
    else:
        if temp[i] == 1:
            temp[i] = 0
        else:
            temp[i] = 1
        if temp[i - 1] == 1:
            temp[i - 1] = 0
        else:
            temp[i - 1] = 1
        if temp[i + 1] == 1:
            temp[i + 1] = 0
        else:
            temp[i + 1] = 1


result = 0
# temp를 2번 사용해야 돼서 깊은 복사를 사용하였다.
temp = copy.deepcopy(array)
# 첫번째 전구를 안누르는 경우(1)가 누르는 경우(2)보다 최소횟수가 작기 때문에 (1)에서 답이 나올경우 (2)를 안하기 위한 flag
flag = False

if temp == target:
    print(0)
else:
    # 첫번째 전구를 안누르는 경우
    for i in range(1, n):
        if temp == target:
            print(result)
            flag = True
            break
        elif i == n - 1:
            change(i)
            result += 1
            if temp == target:
                print(result)
                flag = True
                break
        #앞에 숫자가 다를 경우 change
        elif temp[i - 1] != target[i - 1]:
            change(i)
            result += 1
    # 첫번째 전구를 누르는 경우
    if flag == False:
        temp = copy.deepcopy(array)
        change(0)
        result = 1
        if temp == result:
            print(1)
        else:
            for i in range(1, n):
                if temp == target:
                    print(result)
                    flag = True
                    break
                elif i == n - 1:
                    change(i)
                    result += 1
                    if temp == target:
                        print(result)
                        flag = True
                        break
                    else:
                        print(-1)
                        break
                elif temp[i - 1] != target[i - 1]:
                    change(i)
                    result += 1

시간 복잡도

for문을 n번 만큼만 반복하기 때문에 O(n)이다.

 

어려웠던 부분

첫번째꺼를 누르는 경우와 안누르는 경우로 나누는 것을 생각하는데 시간이 오래 걸렸고

깊은 복사 문법이 헷갈렸다.