[백준] 타노스 20310번 (🥈실버3)

사이트

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

20310번: 타노스

 

문제

 

분석

실버3 문제여서 굉장히 얕본 문제였지만 의외로 어렵게 푼 문제였다... 

필자는 문자열 알고리즘이 너무 약한거 같다. 

자 이제 분석을 들어가보자!

 

처음 생각

필자의 처음생각은 간단했다! 그냥 1하고 0 갯수 샌 다음에 바로 절반으로 나누고 

문제가 요구한게 사전순이므로 그냥 0부터 쭉 갯수 대로 나열하면 될거라고 생각했다.

너무 간단하고 이게 실버문제인가... 의심을 했다. 결국 돌렸더니 25점.... 

 

중간 생각

생각을 정말 많이 했다... 

만약 입력이 000011 일때 0이 2개, 1이 3개 남아야 되므로 

001이 최종정답이 된다.

즉 최종 자릿수는 3이므로 1차: 000 2차: 000 3차: 001 4차: 011 이렇게 비교하면서 타노스한 숫자 자릿수 맞을때 그게 답이 최종인거를 꾸리면 될거 같았는데.. 

 

역시나 문제가 생겼다.  00110000 으로 보면 0010이 최종정답이 될 수 가 없다... 그래서 이 방법도 아웃! 

 

최종 생각

곰곰히 생각을 했다. 기존 문자열을 유지하면서 사전순으로 빠르게 나열할 수 있는  방법 

그건 바로!! 사전순이어야 되므로 타노스한 자릿수 맞게 0을 뒤에서 빼고 동시에 1을 앞에서 빼면 된다!

 

그럼 사전순 및 자릿수가 유지가 된다! 

for(int i=0; i<all; i++){
    if(original.charAt(i)=='1' && f_one_cnt!=0){
        sb.setCharAt(i,'2');
        f_one_cnt--;
    }
}

for(int i=all-1; i>=0; i--){
    if(original.charAt(i)=='0' && f_zero_cnt !=0){
        sb.setCharAt(i,'2');
        f_zero_cnt--;
    }
}

 

필자는 위 코드와 같이 타노스한 자릿수 위치를 2로 바꾸었다. 문자열로 되어 있어 리스트로 바꿀려면 귀찮고 불필요하게 여겨 그냥 setCharAt를 통해 그 수를 바꾸었다. 

String message=sb.toString();
sb=new StringBuilder();
for(int i=0; i<all; i++){
    if(message.charAt(i)!='2'){
        sb.append(message.charAt(i));
    }
}

 

그리고 2가 아닌것만 출력하면 정답이 나오게 된다! 

 

전체 코드

package greedy;

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

public class Greedy20310 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        String original = br.readLine();
        int all = original.length();

        int zero_cnt = 0;
        int one_cnt = 0;
        for (int i = 0; i < all; i++) {
            if (original.charAt(i) == '1') {
                one_cnt++;
            } else {
                zero_cnt++;
            }
            sb.append(original.charAt(i));
        }
        int f_one_cnt = one_cnt / 2;
        int f_zero_cnt = zero_cnt / 2;

        for(int i=0; i<all; i++){
            if(original.charAt(i)=='1' && f_one_cnt!=0){
                sb.setCharAt(i,'2');
                f_one_cnt--;
            }
        }

        for(int i=all-1; i>=0; i--){
            if(original.charAt(i)=='0' && f_zero_cnt !=0){
                sb.setCharAt(i,'2');
                f_zero_cnt--;
            }
        }

        String message=sb.toString();
        sb=new StringBuilder();
        for(int i=0; i<all; i++){
            if(message.charAt(i)!='2'){
                sb.append(message.charAt(i));
            }
        }

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


    }
}

 

 

결과

 

느낀점

정말 고민이 많았고 실버3을 저정도로 못풀었다는게 내 자신에게 실망을 많이 끼친 문제였다... 

너무 피곤해서 머리가 안돌아간건지... 열심히 노력하자!