[알고리즘/그리디] 2138번 : 전구와 스위치 - python

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

2138번: 전구와 스위치

 

---

• 문제
• 소요시간: 30분(실패)

---

• 설계하기(접근방법) 

1. 입력받기

 

list(map(int, str(input()))) 을 통해

int를 공백없이 리스트로 슬라이싱 가능하다

 

2. 구현하기

처음과 끝 리스트를 어떻게 나누어 구현하는가에 생각을 많이했다.

 

이 문제의 핵심은

가운데를 기준으로 이전의 인덱스가

목표 리스트의 인덱스와 같지 않다면 뒤집어주는 것이다

그리디로 생각했을 때 이전의 인덱스는 다시는 뒤집어질 일이 없기 때문이다

 

마지막 부분의 인덱스가 list out of range하지 않게 for문에 조건을 달아줘야 한다

 

그렇다면 끝 부분은 고려하지 않아도 된다

첫번쨰 부분은 case를 2개로 나누어 진행해야 한다

 

0번째를 뒤집어서 index[0]과 index[1]을 뒤집고 가는 경우

pass 하고 가는 경우 2개를 생각해야 한다

 

 

3. 출력하기

둘중에 작은 값을 출력한다.

만약 두 경우 모두 목표 int를 만들 수 없다면 -1을 출력한다

 

---

• 코드(출력)

def change_state(light_state,now, n):
        if now != n - 1:
            for i in range(3):
                light_state[now + i - 1] = 1 - light_state[now + i - 1] 
        else:    
            for i in range(2):
                light_state[now + i - 1] = 1 - light_state[now + i - 1] 

n = int(input())

original_light = list(map(int, str(input())))
target_light = list(map(int, str(input())))

# case 1
case_1 = list(original_light)
cnt_case_1 = 0


for i in range(1, n):
    if case_1[i - 1] != target_light[i - 1]:
        change_state(case_1, i, n)
        cnt_case_1 += 1
    else:
        pass


for i in range(n):
    if case_1[i] != target_light[i]:
        cnt_case_1 = 1e9
        break

# case 2
case_2 = list(original_light)
cnt_case_2 = 1

case_2[0] = 1 - case_2[0]
case_2[1] = 1 - case_2[1]

for i in range(1, n):
    if case_2[i - 1] != target_light[i - 1]:
        change_state(case_2, i, n)
        cnt_case_2 += 1
    else:
        pass

for i in range(n):
    if case_2[i] != target_light[i]:
        cnt_case_2 = 1e9
        break


if cnt_case_1 == 1e9 and cnt_case_2 == 1e9:
    print(-1)
else:
    print(min(cnt_case_1, cnt_case_2))

- 함수로 선언하면 좀더 깔끔한 코드를 짤 수 있다.

---

• 얻어갈 부분

1. 그리디로 푸는 경우, 끝쪽의 경우의 수는 고려할 필요가 없을 수도 있다. 

2. list(map(int, str(input()))) 을 통해 정수를 슬라이싱 할 수 있다.