문제 설명
0과 1로만 이루어진 문자열 s가 주어질 때, s의 모든 숫자를 같게 만드려고 한다. 그렇게 하기 위해 할 수 있는 것은 a번 부터 b번까지 뒤집는 것.
s = 00011000 일 때, 4번부터 5번까지의 1을 한 번만 뒤집으면 문자열을 모두 0으로 같게 만들 수 있다. 이렇듯 원하는 답을 위한 뒤집기의 최소 횟수를 구하여라.
<제한 사항>
시간 제한 : 1 sec
메모리 제한 : 128 MB
<입력>
0과 1로만 이루어진 문자열 s이 주어진다. (1 <= len(s) < 1000000)
<출력>
뒤집기의 최소 횟수
<예시>
0001100
1
1100011000011110
3
나의 풀이
len(s) = 1000000 -> 성공
단순히 0이 연속된 그룹이나 1이 연속된 그룹 중 적은 그룹(해봤자 1 차이지만)을 전부 다른 그룹으로 뒤집으면 되는 거 아닌가?
따라서 숫자가 바뀔 때를 count 해서 (count / 2) 를 올림 하면 되지 않나?
0001111000001101111은 사실 010101과 같고,
010101 이라면 (5/2)를 올림 해서 3,
1010101 이라면 (6/2)를 올림해서 그대로 3
import math
s = input()
cnt = 0
for i in range(1, len(s)):
if s[i] != s[i-1]:
cnt += 1
print(math.ceil(cnt/2))책의 풀이
문자열을 0으로 만드는 경우와 1로 만드는 경우의 비용을 계산해서 둘을 비교하여 최솟값을 가지는 경우를 출력
data = input()
count0 = 0
count1 = 0
if data[0] == '1':
count0 += 1
else:
count1 += 1
for i in range(len(data) - 1):
if data[i] != data[i + 1]:
if data[i + 1] == '1':
count0 += 1
else:
count1 += 1
print(min(count0, count1))느낀 점
이번 만큼은 나의 풀이가 더 간단한 것 같다. 시간을 찍어본 결과도 내 풀이가 더 빨랐다. 문제 자체가 좀 허술하다.
출처 : 이것이 취업을 위한 코딩테스트다 with 파이썬 - 나동빈
No Excuses