[이코테] 문자열 뒤집기

이것이 취업을 위한 코딩테스트다 with 파이썬 책을 읽고 정리한 내용입니다.

 

 

 

 

📋 문제

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다.

다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다.

다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다.

뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

 

예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

 

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

 

 

 

👉 입력

첫째 줄에 문자열 S가 주어진다.

S의 길이는 100만보다 작다.

 

 

👈 출력

첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

 

 

📝 풀이

S = input()

count_0 = 0
count_1 = 0

if S[0] == '1':
  count_0 += 1
else:
  count_1 += 1
  
for i in range(len(S) - 1):
  if S[i] != S[i+1]:
    if S[i+1] == '1':
      count_0 += 1
    else:
      count_1 += 1

print(min(count_0, count_1))

 

그리디를 이용한 풀이 방법이다.

count_0은 S를 전부 0으로 바꾸는 경우, count_1은 S를 전부 1로 바꾸는 경우에 대해 횟수를 센다.

 

먼저 S의 첫 번째 요소를 살펴본다.

S가 1로 시작하면 count_0을, 0으로 시작하면 count_1을 1씩 늘려준다.

 

그리고 for문을 통해 S의 각 요소를 살펴보며 현재 요소와 그 다음 인덱스의 요소가 동일한 값을 가지고 있는지 살핀다.

동일한 값을 가지고 있으면 한 번만 바꾸면 되지만 동일하지 않으면 여러 번에 걸쳐 바꾸어야 하기 때문이다.

또 이 경우 다음 인덱스의 값을 살피고 알맞은 경우를 1씩 늘려준다.

 

그리고 모두 0으로 바꾸는 경우와 모두 1로 바꾸는 경우에 대해 최솟값을 출력한다.

 

이전에 다른 풀이 방법으로 같은 문제를 푼 적이 있다.

 

2022.03.09 - [Algorithm/Python] - [백준 1439번] 뒤집기

[백준 1439번] 뒤집기

 

위 포스팅의 풀이 방법과 이 방법을 비교해 보면 별 차이가 없다.

같은 메모리에 4ms 정도만 차이나니 편한 방법을 사용하면 될 것 같다.

 

🔍 참조

이것이 취업을 위한 코딩 테스트다 with 파이썬 (한빛미디어, 나동빈)