[Python] 백준 1439 - 뒤집기

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

1439번: 뒤집기

 

클릭시 해당 문제 페이지로 이동합니다.

---

해결방법

제가 풀이한 해결 방법은 두 가지가 있습니다.

하나는 문자열을 전부 읽어 들이는 방법, 다른 하나는 split 함수를 이용하는 방법이 있습니다.

방법 1. 

import math
string = input()
L = len(string)
cnt = 0
for i in range(L-1):
  if string[i] != string[i+1]:
    cnt += 1
cnt /= 2
print(math.ceil(cnt))

코드 설명

for 문을 통해서 주어진 문자열을 전부 읽어냅니다. 이때 수가 달라지는 횟수를 카운트합니다. 0->1 혹은 1->0 인 경우입니다. 다솜이는 0을 1로, 혹은 1을 0으로 바꾸는 작업 중 하나만 골라서 모두 같은 수로 만들 생각입니다.

예를 들어 '11101101'을 입력했을 때 수가 달라지는 횟수는 4번입니다. 0을 1로 바꾸는 작업을 두 번만 하면 모두 같은 수로 변환할 수 있습니다. 그럼 입력이 '111011010'인 경우는 어떨까요? 달라지는 횟수는 5번입니다. 이렇게 홀수번일 경우에는 0과 1 중 아무 수나 변환해주면 됩니다. 횟수가 홀수번인 경우는 1의 뭉텅이(?)와 0의 뭉텅이 수가 동일하기 때문입니다. 따라서 수가 변하는 횟수를 2로 나눈 값의 올림이 그 해가 될 것입니다.

('100110100', 달라진 횟수 5번, '1'뭉텅이 3개, '0'뭉텅이 3개. // '101101', 달라진 횟수 4번, '1'뭉텅이 3개, '0' 뭉텅이 2개)

+ 다른 글들을 참고해보니 천정 함수를 이용하는 게 아니라 (횟수+1)//2를 하시네요.

---

방법 2.

def count(split_by):
  cnt = 0
  for ele in split_by:
    if ele != '':
      cnt += 1
  return cnt

string = input()
tmp1 = count(string.split('1'))
tmp2 = count(string.split('0'))
print(tmp1 if tmp1 < tmp2 else tmp2)

코드 설명

입력한 문자열을 1과 0으로 split 하면 각각의 뭉텅이가 리스트로 저장됩니다.

반복문을 통해서 뭉텅이의 개수를 구합니다. 뭉텅이의 수가 더 적은 것을 변환하는 것이 더 작은 수로 변환하는 것입니다. 그러므로 더 작은 값을 출력토록 합니다.

입력 : 100110100
>>> split('1') : ['', '00', '', '0', '00']
>>> split('0') : ['1', '', '11', '1', '', '']
>>> answer : 3

입력 : 101101
>>> split('1') : ['', '0', '', '0', '']
>>> split('0') : ['1', '11', '1']
>>> answer : 2

두 리스트에서 뭉텅이의 개수를 구하고, 더 작은 값을 출력하도록 하는 것이 이 해결방법의 핵심입니다.

---

코드길이 148이 방법1, 다른 하나가 방법2 입니다.