백준 20310 자바 - 타노스 (BOJ 20310 JAVA)

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

 

  사전순으로 가장 빠른 것이 되려면 결국 최대한 0이 앞쪽으로 와야하고, 최대한 1이 뒤쪽으로 가야한다. 그래서 생각보다 간단하게 풀 수 있는데, 단순히 1은 앞에서부터 지우고, 0은 뒤에서부터 지우면 된다.

 

  다음과 같은 경우를 보자.

1은 4개이므로 2개를 지워야 한다. 0은 2개이므로 1개를 지워야 한다.

 

로직은 다음과 같다.

1. 편히 풀기위해 문자열을 character 배열 형태로 변경한다.

 

2. '1'이 들어있는 부분만 보면서, 지워야 하는 개수만큼 앞에서부터 순서대로 지운다. (따라서 이 풀이는 그리디!)

 

3. '0'이 들어있는 부분만 보면서, 지워야 하는 개수만큼 뒤에서부터 순서대로지운다.

 

---

 

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/20300/BOJ_20310.java

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        char[] arr = new char[s.length()];
        int cnt0 = 0;
        int cnt1 = 0;
        for (int i = 0; i < arr.length; i++) {
            arr[i] = s.charAt(i);
            if (arr[i] == '0') cnt0++;
            else cnt1++;
        }
        cnt0/=2;
        cnt1/=2;

        for (int i = 0; i < s.length() && cnt1!=0; i++) {
            if (arr[i] == '1') {
                cnt1--;
                arr[i] = 0;
            }
        }

        for (int i = s.length()-1; i >= 0 && cnt0!=0; i--) {
            if (arr[i] == '0') {
                cnt0--;
                arr[i] = 0;
            }
        }

        StringBuilder answer = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (arr[i] != 0)
                answer.append(arr[i]);
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}