[BOJ] 20310 타노스 - JAVA

1. 문제

20310번: 타노스

어느 날, 타노스는 0과 1로 이루어진 문자열 S를 보았다. 신기하게도, S가 포함하는 0의 개수와 S가 포함하는 1의 개수는 모두 짝수라고 한다.
갑자기 심술이 난 타노스는 S를 구성하는 문자 중 절반의 0과 절반의 1을 제거하여 새로운 문자열 S'를 만들고자 한다. 
S'로 가능한 문자열 중 사전순으로 가장 빠른 것을 구하시오.

---

2. 풀이

1.  S문자열을 char배열로 만든다.

2.  0,1개수를 각각 세고 마지막에 나누기 2를 해둔다.

3.  사전순으로 가장 빠른 것을 만드려면 작은 수를 만들어야 한다. 따라서 앞에서부터 1을 뺀다. 이 때, 배열에서 문자 '1'이 있는 자리를 제거하지 않고 '*'같은 아무 의미없는 문자를 넣었다.

4.  뒤에서부터 0을 빼야하는데, 이때도 의미없는 문자를 대신 넣었다.

5.  StringBuilder로 의미없는 문자를 제외하고 하나씩 붙여서 출력한다.

import java.io.*;

public class BOJ_20310_타노스 {
   public static void main(String[] args) throws IOException {
      //입력
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      char[] S = in.readLine().toCharArray();

      //0,1개수 세기
      int zero = 0;
      int one = 0;
      for(int i=0;i<S.length;i++){
         if(S[i]=='0') zero++;
         else one++;
      }
      zero/=2;
      one/=2;

      //1은 앞에서부터 빼기
      int idx = 0;
      while(one>0){
         if(S[idx]=='1') {
            S[idx]='*';
            one--;
         }
         idx++;
      }

      //0은 뒤에서부터 빼기
      idx = S.length-1;
      while(zero>0){
         if(S[idx]=='0') {
            S[idx]='*';
            zero--;
         }
         idx--;
      }

      //출력
      StringBuilder sb = new StringBuilder();
      for(char s:S){
         if(s!='*') sb.append(s);
      }
      System.out.println(sb);
   }
}

---

3. 결과