[백준] 1439번 : 뒤집기 – JAVA [자바]

https://www.acmicpc.net/problem/1439

 

 

---

문제

 

 

---

해결 방법

 

이 문제는 그리디 알고리즘(Greedy Algorithm)을 사용하여 해결할 수 있다.

1. 0과 1이 각각 몇 번 그룹으로 나뉘는지 계산한다.

예를 들어 0001100의 경우, 000 / 11 / 00으로 0 그룹 2개, 1 그룹 1개가 된다.

11001100110011000001의 경우, 11 / 00 / 11 / 00 / 11 / 00 / 11 / 00000 / 1로 0 그룹 4개, 1 그룹 4개가 된다.

2. 0과 1의 그룹 수 중 작은 값을 선택하면 최소 뒤집기 횟수가 된다.

예를 들어 0001100의 경우 0 그룹 2개, 1 그룹 1개이므로 최소 1번 뒤집으면 해결 가능하다.

11001100110011000001의 경우 0 그룹 4개, 1 그룹 4개이므로 최소 4번 뒤집어야 한다.

 

 

---

코드 

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int zeroCount = 0; // '0' 그룹의 개수
        int oneCount = 0;  // '1' 그룹의 개수
        
        // 첫 번째 문자에 따라 첫 그룹을 추가
        if (s.charAt(0) == '0') {
            zeroCount++;
        } else {
            oneCount++;
        }
        
        // 연속된 숫자가 변경될 때마다 그룹 개수 증가
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                if (s.charAt(i) == '0') {
                    zeroCount++;
                } else {
                    oneCount++;
                }
            }
        }
        
        // 최소 횟수를 출력
        System.out.println(Math.min(zeroCount, oneCount));
    }
}

 

 

---

코드 설명

1. 첫 번째 문자가 '0'인지 '1'인지 확인하고 해당 그룹을 추가한다.

2. 문자열을 순회하면서 이전 문자와 다를 때마다 그룹 수를 증가시킨다.

  - 예를 들어 110011이라면, 11 → 00 → 11로 변하면서 0 그룹 1개, 1 그룹 2개가 된다.

3. 0과 1의 그룹 수 중 작은 값을 출력하면 최소 뒤집기 횟수가 된다.

 

이 문제가 그리디 알고리즘인 이유

이 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 항상 최적의 선택이 명확하게 정해져 있기 때문이다.

한 번에 뒤집을 때, 가장 큰 그룹을 뒤집는 것이 유리하다.

그룹의 개수를 세고 최소 그룹을 뒤집으면 항상 최적의 해를 보장할 수 있다.

따라서, 0 그룹 개수와 1 그룹 개수를 세고 더 작은 값을 선택하는 것이 최적의 방법이다.

---

시간 복잡도 분석

• 문자열을 한 번 순회하며 그룹을 계산하므로 O(N)의 시간 복잡도를 가진다.