백준 1439 : 뒤집기

문제 링크

풀이

카카오 공채 문제 중 하나였던 문자열 압축의 쉬운 버전입니다.

만약 00111000인 경우의 뒤집기 수는, 이어져있는 동일한 수(00, 111, 000)은 하나의 수(0,1,0)과 같습니다. 가령 00111000을 뒤집기 위해서는 중간에 같은 수와 이어지지 않은 111을 뒤집으면 되듯이, 010에서도 마찬가지입니다.

이를 이용하여 우선 이어진 수를 하나의 수로 치환하는 문자열 압축을 해주고, 0과 1의 갯수를 세어 둘 중 더 작은 값을 출력하면 됩니다.
단, 유의해야할 점은 입력으로 들어오는 S는 최대 1,000,000의 값을 지닙니다. 즉 10^6으로, 한 번의 순회(O(N))로만 처리해야 시간초과를 받지 않을 수 있습니다. (10^8이 대략 1초 걸립니다.)

코드

S = input()
ans = ""
N0 = 0
N1 = 0

for i in range(1, len(S)) :
  if(S[i-1] != S[i]) :
    ans += S[i-1]
    if(S[i-1] == "0") : N0+=1
    else : N1+=1
if(ans and (S[len(S)-1] != ans[len(ans)-1])) :
  ans+=S[len(S)-1]
  if(S[len(S)-1] == "0") : N0+=1
  else : N1+=1

print(min(N0,N1))

해당 코드의 시간 복잡도는 한 번 순회하는 것으로 끝나므로, O(N)입니다.