백준 20310번 풀이 : 타노스 (JAVA)

문제 링크 : https://www.acmicpc.net/problem/20310

20310번: 타노스

 

❓  문 제

어느 날, 타노스는 0과 1로 이루어진 문자열 S를 보았다. 신기하게도, S가 포함하는 0의 개수와 S가 포함하는 1의 개수는 모두 짝수라고 한다.

갑자기 심술이 난 타노스는 S를 구성하는 문자 중 절반의 0과 절반의 1을 제거하여 새로운 문자열 S′를 만들고자 한다. S′로 가능한 문자열 중 사전순으로 가장 빠른 것을 구하시오.

 

✏️  입 력

문자열 S가 주어진다.

 

💻  출 력

S′로 가능한 문자열 중 사전순으로 가장 빠른 것을 출력한다.

 

❗️ 예 제

 

 

---

💡 문제 풀이

1. 0의 갯수와 1의 갯수를 파악하여 앞쪽에 0의 갯수 / 2를 출력, 뒷쪽에 1의 갯수 / 2를 출력하게 되면 예제는 맞게 되지만 문제의 요점과는 다르게 된다.

 

2. 탐욕법(그리디)를 추가하여 문제를 해결해야한다.

 

3. 가장 작은 수가 되기 위해선 0을 뒤에서 부터 지우고 1을 앞에서 부터 지우면 된다.

 

 

✏️ 풀이 과정

1. 0의 갯수와 1의 갯수를 구한다.

 

2. 문자열을 앞에서 부터 탐색하여 1의 갯수 / 2만큼 1을 지워준다.

 

3. 문자열을 뒤에서 부터 탐색하여 0의 갯수 / 2 만큼 0을 지워준다.

 

4. 지워지지 않은 수만 문자열로 더하여 출력한다.

 

⌨️ 풀이 코드

package develope;

import java.util.*;

public class Main_20310 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String str = sc.next();
        char[] arr = str.toCharArray();
        String answer = "";

        int count_0 = 0;
        int count_1 = 0;

        for(int i = 0; i < arr.length; i++){
            if(arr[i] == '0') count_0++;
            else count_1++;
        }
        
        count_0 /= 2;
        count_1 /= 2;

        for(int i = 0; i < str.length(); i++){
            if(count_1 == 0) break;

            if(arr[i] == '1') {
                arr[i] = '-';
                count_1--;
            }
        }

        for(int i = arr.length - 1; i >= 0; i--){
            if(count_0 == 0) break;

            if(arr[i] == '0'){
                arr[i] = '-';
                count_0--;
            }
        }

        for(int i = 0; i < arr.length; i++){
            if(arr[i] != '-') answer += arr[i];
        }
        System.out.println(answer);
    }
}

 

✅ 비고

• 문자열 문제이지만 그리도 알고리즘도 포함하여 풀어야 하는 문제이다.
• 숫자를 최소로 하기 위해선 0을 앞에서 뒤에서 지워야하고 1을 앞에서 지워야 한다.