[2138] 전구의 스위치 in python

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

2138번: 전구와 스위치

 

시간 복잡도를 생각하지 못하고

bfs로 탐색을 진행했다가

메모리초과 뜸..

 

아래 코드의 시간복잡도는

O(N^2)

1초에 N의 범위가 2000 이하여야 쓸 수 있는 코드!

 

 

하지만

주어진 데이터 개수는 10만

시간 복잡도를 계산하면 10만 *. 10만 =. 100만

 

결국 O(N)으로 작성을 해야 함! 

 

시간 제한은 2초

# import sys
# from collections import deque
#
# n = int(input())
# state = list(input())
# want = list(input())
# for i in range(n):
#     if state[i] == '0':
#         state[i] = False
#     else:
#         state[i] = True
#     if want[i] == '0':
#         want[i] = False
#     else:
#         want[i] = True
#
# result = 0
# sys.setrecursionlimit(100000)
# def bfs(node, result):
#     queue=deque()
#     queue.append((node,result))
#     while queue:
#         now_node,cnt=queue.popleft()
#         if now_node==want:
#             print(cnt+2)
#             break
#         for i in range(n):
#             if i==0:
#                 temp=now_node
#                 temp[0],temp[1]=not(temp[0]),not(temp[1])
#                 queue.append((temp,cnt+1))
#             elif i==n-1:
#                 temp = now_node
#                 temp[n-2], temp[n-1] = not (temp[n-2]), not (temp[n-1])
#                 queue.append((temp, cnt + 1))
#             else:
#                 temp = now_node
#                 temp[i-1],temp[i], temp[i+1] = not (temp[i-1]), not (temp[i]),not(temp[i+1])
#                 queue.append((temp, cnt + 1))
#
# bfs(state,0)

 

 

---

그래서 아래 코드는 

O(N) 범위 내에서 돌아가는 방식이다.

 

문제에 나와있는 예시에서는

초기 전구 스위치 상태가 000이고,

원하는 스위치 상태를 010이라고 한다.

 

0번째 스위치가 켜져있느냐 

켜져있지 않느냐에 따라서

조건을 나눠준다.

 

 

0번째 스위치와 맨 마지막 스위치를 다른 스위치들과는 다른 조건을 걸어줘야한다.

 

조건1)

 0번째 스위치를 누르지 않는다고 가정한다.

000에서 0번째 스위치는 누르지 않고

바로 1번째 스위치로 넘어간다.

1번쨰 스위치는 1이 되어야 하니 

1번째 스위치를 눌러준다.

 

000 => 111

 

111에서 2번쨰 스위치를 누르면 100이 되는데

이렇게 되면 애초에 원하는 010이 나올 수 없으므로 -1이 된다.

이런식으로 왼쪽을 비교해가며

탐색을 진행하면 된다.

약간 다이나믹 프로그래밍과 비슷한 방식인 것 같다.

 

---

조건2)

0번째 스위치를 누른다고 가정한다.

000에서 110이다.

 

1번째 스위치를 눌러야 맨 앞의 스위치가 0이 되므로

눌러준다.

 

110 -> 001

 

001에서 2번째 스위치를 눌러야 010이 되므로

눌러준다.

 

 

스위치를 눌러준 횟수는 총 3회이고,

두 조건 중에 -1이 아닌 숫자 중, 가장 작은 수이므로

3을 출력한다. 

 

n = int(input())
state = list(map(int, input().rstrip('\n')))  # 000을 숫자 0,0,0으로 받으려면 rstrip('\n')을 해줘야함.
want = list(map(int, input().rstrip('\n')))
def change(num):
    if num == 0:
        return 1
    else:
        return 0


def switch(array, cnt):
    if cnt == 1:
        array[0] = change(array[0])
        array[1] = change(array[1])
    for i in range(1, n):
        if array[i - 1] != want[i - 1]:
            cnt += 1
            array[i - 1] = change(array[i - 1])
            array[i] = change(array[i])
            if i != n - 1:
                array[i + 1] = change(array[i + 1])
    if array == want:
        return cnt
    else:
        return -1


test1 = switch(state[:], 0)  # 0번쨰 스위치 안 누름
test2 = switch(state[:], 1)  # 0번째 스위치 누름
if test1 >= 0 and test2 >= 0:
    print(min(test1, test2))
elif test1 >= 0 and test2 < 0:
    print(test1)
elif test1 < 0 and test2 >= 0:
    print(test2)
else:
    print(-1)