[백준 1439번-뒤집기]-파이썬

 

solved.ac 난이도 :  Silver5

백준  1439번- 파이썬 풀이

 

<문제>

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

1439번: 뒤집기

<풀이>-그리디 알고리즘

이 문제는 '0'을 뒤집는 부분과 '1'을 뒤집는 부분을 각각 구현해 두 개의 결과중 작은값을 출력하는 식으로 풀이를 구서해 봤다. 이때 뒤집는 부분을 필자는 큐 자료구조를 이용해 봤다.

 

-'1'을 뒤집는 부분-

 

우선 핵심은 다음과 같다. 큐에 문자열의 처음 원소를 삽입한다. 이때 연속된 숫자는 한번에 뒤집는다. 

 

즉, 큐에서 추출한 원소가 1인 경우 다음 원소가 0일경우 뒤집는 횟수가 추가된다는 것이다. 이럴경우 뒤집는 횟수를 +1해주고 다음원소를 큐에 삽입한다.

 

만약 큐에서 추출한 원소가 '0'이거나 추출한 원소가 '1'이고 다음원소도 '1'인경우 뒤집는 횟수에 추가할 필요 없이 큐에 삽입한다.

 

그리고 마지막 원소가 '1'인경우도 뒤집어야하는데 마지막 원소는 다음 원소가 없으므로 마지막 부분이 '1'인경우 뒤집는 횟수에 +1을 해준다.  

 

정리하자면 현재 추출한 원소가 '1'이면서 다음 원소가 '0' 또는 마지막 원소이면서 '1'인 경우 뒤집는 횟수에 +1을 해줘야 한다.

 

-'0'을 뒤집는 부분-

 

위 '1'을 뒤집는 부분에서 '1'을 '0'으로만 바꿔주면 된다.

728x90

반응형

<코드>-파이썬

from collections import deque
s = input()
s = list(s)
queue1 = deque()
queue1.append((s[0],0))

queue2 = deque()
queue2.append((s[0],0))
answer1 = 0
answer2 = 0
while queue1:
    num,x = queue1.popleft()
    #1을 뒤집는다.
    nx = x+1
    if 0<=nx<len(s):
            if (num == '1' and s[nx] != '1') or (s[nx]=='1' and nx == len(s)-1):
                answer1+=1
                queue1.append((s[nx],nx))
            else:
                queue1.append((s[nx],nx))

while queue2:
    num,x = queue2.popleft()
    #0을 뒤집는다.
    nx = x+1
    if 0<=nx<len(s):
            if (num == '0' and s[nx] != '0') or (s[nx]=='0' and nx == len(s)-1):
                answer2+=1
                queue2.append((s[nx],nx))
            else:
                queue2.append((s[nx],nx))


print(min(answer1,answer2))

-마치며-

 

그리디 알고리즘 문제는 풀이법이 정말 다양한거 같다. 그리디 알고리즘을 풀때는 반드시 스스로 한번 풀어보고 다른 사람들의 풀이도 확인해 자신과 다른점이 뭔지, 다른 접근 방식은 무엇이 있는지를 꼼꼼히 확인해봐야 할거 같다.