[백준] 20310 타노스 - 그리디(탐욕법, Greedy) JAVA

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

코드설명

그리디(탐욕법, Greedy) 문제입니다.

 

문자열 중 사전순으로 가장 빠른 것을 구하기 위해서는, 0이 앞에 가장 많아야하고, 1이 가장 뒤에 있어야 합니다.

1. 맨 앞에서부터 1 의 개수의 절반만큼 1을 발견하면 삭제합니다.

2. 맨 뒤에서부터 0 의 개수의 절반만큼 0 을 발견하면 삭제합니다.

코드

package Main;

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

public class Main {
	private static int N, M, Q, K;
    private static char[] arr;
    private static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
//        N = Integer.parseInt(st.nextToken());
        
//        st = new StringTokenizer(br.readLine());
        arr = st.nextToken().toCharArray();
        
        int oneCnt = 0, zeroCnt = 0;
        N = arr.length;
        for(int i=0;i<N;i++) {
        	if(arr[i] == '1') {
        		oneCnt += 1;
        	}else if(arr[i] == '0'){
        		zeroCnt += 1;
        	}
        }
        
        
        //이제 앞에서부터 먼저 삭제처리를 하자.
        //1을 삭제하자.
        oneCnt /= 2; zeroCnt /= 2;
        for(int i=0;i<N && oneCnt > 0;i++) {
        	if(arr[i] == '1') {
        		oneCnt -= 1;
        		arr[i] = 'X';
        	}
        }
        
        for(int i=N-1;i>=0 && zeroCnt > 0;i--) {
        	if(arr[i] == '0') {
        		zeroCnt -= 1;
        		arr[i] = 'X';
        	}
        }
        
        for(int i=0;i<N;i++) {
        	if(arr[i] != 'X') {
        		System.out.print(arr[i]);
        	}
        }
    }
    
}