[BOJ] 백준 20310. 타노스

문제

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

 

 

 

---

풀이

0과 1로 이루어진 문자열 S가 있으면, 0과 1을 절반씩 제거하는데 사전 순으로 가장 빠른 것을 구하는 문제입니다. 

 

아이디어를 생각해보면, 사전 순이라는 것은 0이 1보다 우선이라는 얘기입니다. 다르게 말하면, 제거할 때 0은 뒤에서부터 제거하여 최대한 앞의 0을 남겨야하고, 1은 앞에서부터 제거하여 사전 순을 미루어야합니다.

 

전체 문자열 중 0과 1의 숫자를 구하고, 0은 뒤에서 1은 앞에서 인덱스를 찾아가며 각각의 절반에 다다르면 while문을 종료합니다.

 

아래는 소스 코드입니다.

---

소스 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] ch = sc.next().toCharArray();
        int zeroCnt = 0;
        int oneCnt = 0;

        for(int i = 0; i<ch.length;i++){
            if(ch[i]=='0') zeroCnt++;
            if(ch[i]=='1') oneCnt++;
        }

        int idx = 0;
        int cnt = 0;
        while(cnt<oneCnt/2){
            if(ch[idx]=='1'){
                cnt++;
                ch[idx] = '2';
            }
            idx++;
        }

        idx = ch.length-1;
        cnt = 0;
        while(cnt<zeroCnt/2){
            if(ch[idx]=='0'){
                cnt++;
                ch[idx] = '2';
            }
            idx--;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<ch.length;i++){
            if(ch[i]=='0'||ch[i]=='1') sb.append(ch[i]);
        }
        System.out.println(sb.toString());
    }
}