[JAVA] 백준 #20310 타노스 문제 풀이 / Greedy Algorithm / StringBuilder / 25점 반례

---

백준 #20310 타노스 

20310번: 타노스

🔒 문제 설명

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

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

 

⌨️ 입력

문자열 S가 주어진다.

 

🖥️ 출력

S'로 가능한 문자열 중 사전순으로 가장 빠른 것을 출력한다

 

---

🗝️Solution

1차 시도: 25점

import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();

        // 0의 개수 = num0
        int num0 = 0;

        //1의 개수 = num1
        int num1 = 0;

        for(int i = 0; i < s.length(); i++){
            if( s.charAt(i)== '0') num0 ++;
            else num1 ++;
        }

        // num0, num2 각각 절반값으로 교체
        num0/=2;
        num1/=2;

        StringBuilder stringBuilder = new StringBuilder();

        for(int i =0; i<num0 ; i++){
            stringBuilder.append('0');
        }
        for(int i =0; i<num1 ; i++){
            stringBuilder.append('1');
        }

        System.out.println(stringBuilder);

    }
}

처음 문제를 봤을 때 '어? 이거 너무 쉬운데?' 하고 0의 개수와 1의 개수를 각각 구해서 절반으로 나누고 0, 1을 각각 절반값만큼 StringBuilder에 append 해서 출력하는 방식으로 금방 풀어냈다. 하지만 결과는 25점. 그렇다 내가 놓친 문제의 조건이 있었다.

 가능한 문자열 중 사전순으로 가장 빠른 것을 구하시오.

문제를 대충 훑었을 때는 그냥 사전순으로 출력하라는 것이라고 생각하고 단순히 0 먼저 1 다음 이렇게 코드를 구성했는데, 알고 보니 위 조건은 한 개가 아닌 두 개를 합한 것이다. 바로 '사전순'과 '가장 빠른 것'.

그런데 내 생각에는 문제의 조건이 명확하지 않은 듯하다. 조건을 '가능한 문자열 중 사전순으로 나열했을 때 가장 빠르게 구할 수 있는 문자열을 출력하시오'라고 하는 것이 더 명확한 것 같다. 

 

반례를 함께 보면 조건을 이해하기 쉽다. 위와 같이 원래 문자열에서 0과 1의 절반값만 구하고 0 먼저 1 다음 재배열한 문자열을 출력하는 코드를 작성했을 경우 아래 입력에 대해 잘못된 출력이 나온다.

 

⌨️input:

//반례 
00110000

 

🖥️output:

//틀린 출력
0001

//올바른 출력
0010

 

0과 1을 재배열할 경우 S'로 가능한 문자열 중 '사전순'으로 가장 앞에 있는 문자열임에는 틀림없지만 '가장 빠른 문자열'인 것은 아니다. 그러므로 위 반례에 대해 틀린 답을 출력한다.

암튼 조건에 해당하는 문자열을 구하려면 문자열을 따로 재배열하지 말고 1은 앞에서부터, 0은 뒤에서부터 제거하는 Greedy Algorithm으로 코드를 구성하면 된다.

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();

        // 0의 개수 = num0
        int num0 = 0;

        //1의 개수 = num1
        int num1 = 0;

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            sb.append(c);
            if( c == '0') num0 ++;
            else num1 ++;
        }


        // num0, num2 각각 절반값으로 교체
        num0/=2;
        num1/=2;


        // 1은 앞에서 없애기
        for(int i = 0; i < sb.length(); i++){
            if(sb.charAt(i)=='1') {
                sb.setCharAt(i,'2');
                num1 --;
            }
            if(num1 == 0) break;
        }

        // 0은 뒤에서부터 없애기
        for(int i = sb.length()-1; i > -1; i--){
            if(sb.charAt(i)=='0') {
                sb.setCharAt(i,'2');
                num0 --;
            }
            if(num0 == 0) break;
        }

        for(int i = 0; i<sb.length(); i++){
            if(sb.charAt(i) == '1' | sb.charAt(i) == '0') System.out.print(sb.charAt(i));
        }
    }
}

 

처음에는 sb.deleteCharAt(i);을 사용해서 1과 0을 없애는 방식으로 코드를 구성했다.

그래서 객체를 변경할 수 없는 String 대신 새로운 String Builder라는 객체를 생성하고 S값을 복사하여 String Builder의 요소를 삭제해 나갔다. 하지만 이렇게 하면 for문에서 sb의 길이가 계속 달라지므로 누락되는 것이 생겨서 복잡했다.

 

그래서 sb.setCharAt(1, '2')를 사용해서 1과 0을 '2'로 바꿔주고 마지막에 출력할 때는 문자열에서 2가 아닌 0과 1만을 출력하도록 했다. 이렇게 하면 StringBuilder를 안 쓰고 기존 S를 변경해도 됐을 것 같다. 

 

sb.setCharAt(i,'2');

 

 

결과는 100점💯