백준 20310번: 타노스[JAVA]

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

20310번: 타노스

 

 

[25점 정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        char[] words = br.readLine().toCharArray();
        int countZero = 0;
        int countOne = 0;

        for (char word : words) {
            if (word == '0') {
                countZero++; // 0의 개수를 카운팅
            } else {
                countOne++; // 1의 개수를 카운팅
            }
        }
        for (int i = 0; i < countZero / 2; i++) { // 0의 개수의 절반을 날린것을 먼저 출력
            bw.write("0");
        }
        for (int i = 0; i < countOne / 2; i++) { // 1의 개수의 절반을 날린것을 뒤에 출력
            bw.write("1");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

[100점 정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String words = br.readLine();
        int countZero = 0;
        int countOne = 0;

        for (int i = 0; i < words.length(); i++) {
            if (words.charAt(i) == '0') { // 0의 개수 카운팅
                countZero++;
            } else { // 1의 개수 카운팅
                countOne++;
            }
        }
        countZero/=2; // 0의 개수 카운팅 한것의 절반을 날림
        countOne/=2; // 1의 개수 카운팅 한것의 절반을 날림
        
        // 1 제거 로직
        int i = 0;
        while (countOne != 0) {
            if (words.charAt(i) == '1') { // 해당 인덱스의 가 1일 경우
                words = words.substring(0, i) + words.substring(i + 1); // i번 인덱스를 제거한다
                countOne--;
                i = -1; // i번 인덱스를 제거할 경우 i를 다시 초기화 해주어야 인덱스가 꼬이지 않는다
            }
            i++;
        }

        // 0 제거 로직
        int j = words.length() - 1;
        while (countZero != 0) {
            if (words.charAt(j) == '0') { // 해당 인덱스의 가 0일 경우
                words = words.substring(0, j) + words.substring(j + 1); // j번 인덱스를 제거한다
                countZero--;
                j = words.length(); // j번 인덱스를 제거할 경우 j를 다시 초기화 해주어야 인덱스가 꼬이지 않는다
            }
            j--;
        }
        System.out.println(words);

        bw.flush();
        bw.close();
        br.close();
    }
}

 

[설명]

이 문제는 그리디 알고리즘과 문자열을 잘 다뤄야한다. 먼저 처음에 25점 짜리 정답은 문제를 잘못이해해 0과 1의 개수를 카운팅 한후 0과1을 단순 재배열해 0의 개수의 절반만큼 0출력 후 나머지 1의 개수의 절반만큼 1출력했다. 그 결과 25점짜리 정답을 맞았다.

다시 문제를 보니 입력받은 문자열을 다 뜯어서 재배치하는것이 아니라 입력받은 문자열에서 0과 1을 제거해 사전순으로 출력하는것이다.

1을 제거하는 로직을 보면 for문이 아닌 while문으로 작성한 이유는 for문으로 작성할 경우 String.substring() 으로 해당 인덱스의 문자를 제거할 경우 제거한 인덱스만큼 문자열이 줄어들어 i가 바라보는 인덱스와 검사해야할 문자열의 인덱스가 꼬이는 경우가 발생하기 때문에 while문으로 작성했다. String.substring()으로 문자열을 수정했을 경우 i를 초기화시켜 다시 처음부터 문자열을 체크했다. 지금보니 문자열을 i = -1 이런식으로 처음으로 초기화시킬 필요없이 수정한 인덱스 바로 뒤로 초기화시켜도 되는것같다.