[리뷰] 그리디 - 뒤집기

github.com/ndb796/python-for-coding-test

ndb796/python-for-coding-test

이번 문제는 백준에도 올라와 있다.

www.acmicpc.net/problem/1439

1439번: 뒤집기

n의 범위에 따라 문제 풀이 방식의 팁

O(n^3) : 500

O(n^2) : 2,000

O(nlogn) : 100,000

O(n) : 10,000,000

O(logn) : 10,000,000,000 이상

리스트 크기가 1000만 이상으로 주어지는 경우는 설계를 잘못한거다.

 

이번 문제는 연속된 0의 개수 1의 개수를 센다음, 더 적은 수를 뒤집는것이 최소 행동이다. 하지만 연속된 0의 개수와 1의 개수를 세는것은 생각보다 귀찮다. 물론 어렵진 않다. 변화되는 개수를 센다음 0의 연속 숫자와 1의 연속 숫자는 언제나 1 또는 0이다. 그래서 2로 나눠서 더 작은 수를 찾는다.

수	변화 갯수	뒤집는 최소 횟수
01	1	1
10	1	1
010	2	1
101	2	1
0101	3	2
01010	4	2

이렇게 패턴을 찾으면 바로 코드로 옮겨준다.

 

파이썬 

s = input()
change = 0
for i in range(len(s)-1):
  if s[i] != s[i+1]:
    change+=1
if change%2 ==0:
  result = change//2
else:
  result = change//2+1
print(result)

정석적으로 푼경우

s = input()
change0 = 0
change1 = 0
if s[0] == '0':
  change0 +=1
else:
  change1 +=1
for i in range(len(s)-1):
  if s[i] != s[i+1]:
    if s[i+1] == '0':
      change0 +=1
    else:
      change1 +=1

print(min(change0,change1))

c++ 정석적으로 푼 방법은 생략한다.

#include <bits/stdc++.h>

using namespace std;

int main() {
  string s;
  cin >>s;
  int change = 0;
  int result;
  for(int i =0; i< s.size()-1;i++){
    if(s[i]!=s[i+1]) change++;
  }
  if(change%2 ==0) result = change / 2;
  else result = change / 2 +1;
  cout<<result<<'\n';
}