[백준] 20310번: 타노스 (25점 반례)

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

20310번: 타노스

 

 

 

1차 시도: 25점

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = br.readLine();

        int zero = 0;
        int one = 0;
        for (int i = 0; i < inputStr.length(); i++) {
            if (inputStr.charAt(i) == '0') zero++;
            else if (inputStr.charAt(i) == '1') one++;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < zero/2; i++) {
            sb.append(0);
        }

        for (int j = 0; j < one/2; j++) {
            sb.append(1);
        }

        System.out.println(sb.toString());
    }
}

여기서 내가 놓친 조건은

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

 

그냥 사전순으로 가장 빠른 거라고 단순히 생각했는데 구체적으로 들여다보면 가능한 문자열 중 사전순으로 나열했을 때 가장 빠르게 구할 수 있는 문자열을 출력하라는 말이 더 적합한 것 같다.

 

반례를 살펴보면

input

00110000

 

output

// 오답
0001
// 정답
0010

 

이러한 조건에 해당하는 문자열을 구하려면 따로 재배열하지 말고 1은 앞에서부터, 0은 뒤에서부터 제거하는 그리디 알고리즘으로 코드를 구현하면 된다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = br.readLine();

        int zero = 0;
        int one = 0;
        for (int i = 0; i < inputStr.length(); i++) {
            if (inputStr.charAt(i) == '0') zero++;
            else if (inputStr.charAt(i) == '1') one++;
        }

        zero /= 2;
        one /= 2;

        char[] charArray = inputStr.toCharArray();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < inputStr.length() && one != 0; i++) {
            if (charArray[i] == '1') {
                one--;
                charArray[i] = 0;
            }
        }

        for (int j = inputStr.length()-1; j >= 0 && zero != 0; j--) {
            if (charArray[j] == '0') {
                zero--;
                charArray[j] = 0;
            }
        }

        for (int k = 0; k < inputStr.length(); k++) {
            if (charArray[k] != 0) {
                sb.append(charArray[k]);
            }
        }

        System.out.println(sb.toString());
    }
}

 

앞에서부터 '1'을 검사한다. 만약 문자가 '1'이면 0(숫자 0과 문자 '0'은 다름!) 숫자 0으로 바꿔주고 one을 하나 감소시킨다. 

다음은 뒤에서부터 '0'을 검사한다. 만약 문자가 '0'일 경우 숫자 0으로 바꿔주고 zero를 하나 감소시킨다. 

마지막으로 결과 문자열을 추출하기 위해 숫자0이 아닌 문자만 StringBuilder로 합친다.

결과를 출력해주면 끝이다!

 

 

 

참조

• https://nahwasa.com/entry/%EB%B0%B1%EC%A4%80-20310-%EC%9E%90%EB%B0%94-%ED%83%80%EB%85%B8%EC%8A%A4-BOJ-20310-JAVA
• https://yuejeong.tistory.com/45