[BAEKJOON] 1439 뒤집기

문제 요약

• 알고리즘 분류: 그리디
• 난이도: Silver5
• 문제내용:
  • 0과 1로 이루어진 문자열 S가 있다.
  • 뒤집다는 의미는 0과 1을 바꾸는것이다. 
  • 뒤집을 수 경우는 모두다 뒤집거나 a ~ b 길이 만큼 변경이 가능하다.
  • 모든 숫자가 같을라면 몇번 뒤집어야 하는가

• 사이트: 거스름돈

5585번: 거스름돈

문제풀이

 이번 문제는 최대길이가 100만이고 제한시간 1초라서 O(n)으로 풀어야 한다. 브루드포스 알고리즘으로 풀기에는 무리가 있어서 그리디알고리즘으로 적용해야한다.

https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

 문제 접근 방법

 그리디는 간단한데 중요한것은 접근 방법이다. 첫번째 문제를 예시로 하겠다.

 위 그림으로 보면 000/ 11/ 00으로 구분을 해두었다. 구분을 해두면 0만 변경하면 첫번째 구간 3번째 구간 총 2번만 변경하면된고. 1만 변경한다면 2번만 변경하면된다. 0인 구간과 1인 구간 갯수중 적은 구간만 출력하면 된다. 2번째 예제는 1111을 보면 모두가 같기 때문에 변경할필요는 없지만 알고리즘으로 본다면  0의 구간의 개수는 0개 1의 구간의 개수는 1개이라서 답은 0개이다. 결론은 0 → 1 또는 1 → 0을 바뀌는 경우중 더 적게 바뀌는 곳만 알면 된다.

Code

Python

S = input()
count = [0, 0]
count[int(S[0])] = 1
for i in range(1, len(S)):
    count[int(S[i])] += 1 if S[i] != S[i - 1] else 0
print(min(count))

 Java

Java개발자로 간다면,  Stream  사용하는 방법도 익혀두도록 하자. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		String S = br.readLine();
		int[] count = {0, 0};
		count[Integer.parseInt(S.substring(0, 1))]++;
		for(int i = 1; i < S.length(); i++) {
			if(S.charAt(i - 1) != S.charAt(i)) {
				count[Integer.parseInt(S.substring(i, i+1))]++;
			}
		}
		System.out.println(Arrays.stream(count).min().getAsInt());
		
	}
	
}