[백준_20310번] 타노스

[문제]

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

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

 

[코드]

import java.util.*;

public class BaekJoon_20310 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String str=sc.next();
		char[] ch=str.toCharArray();
		
		int one=0;
		int zero=0;
		for(int i=0;i<str.length();i++) {
			if(str.charAt(i)=='1')
				one++;
			else
				zero++;
		}
		
		// 문자열의 0과 1의 개수 중 반을 없애야 함
		one/=2;
		zero/=2;
		
		// 앞자리에 1이 오면 최솟값이 될 수 없으므로 앞에있는 1부터 지우기
		for(int i=0;i<ch.length;i++) {
			if(one>0&&ch[i]=='1') {
				ch[i]='X';
				one--;
			}
		}
		
		// 0은 최대한 앞에 있어야 하므로 뒤에있는 0부터 지우기
		for(int i=ch.length-1;i>=0;i--) {
			if(zero>0&&ch[i]=='0') {
				ch[i]='X';
				zero--;
			}
		}
		
		// 결과 출력
		String result="";
		for(int i=0;i<ch.length;i++)
			if(ch[i]=='0'||ch[i]=='1')
				result+=ch[i];
		
		System.out.println(result);
		
	}
}

 

[고찰]

 이번 문제는 어떻게 최솟값을 만들 수 있을지만 체크하면 쉽게 풀리는 문제였다. 0은 최대한 앞에만 위치하여 단위가 늘어나지 않게 해야하고, 1은 최대한 뒤에 위치해 값이 커지지 않게 해야한다. 즉, 0은 뒤에서부터 지우고 1은 앞에서부터 지우면 되는 문제였다.