[백준/JAVA] 20310번: 타노스

📖 문제

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

 

 

 

💡  풀이 방식

• 그리디

1. 입력받은 문자열 s에서 0과 1의 갯수를 세며 StringBuilder 객체로 문자열을 민든다.

2. 0과 1의 갯수를 각각 절반값으로 교체한다.

3. 앞에서부터 1을 없애며, 1의 갯수가 0일 때 종료한다.  0은 뒤에서부터 없애며, 0의 갯수가 0일 때 종료한다. ⇒ 그리디.  가능한 문자열 중 사전순으로 가장 빠른 것을 구한다.

5. 문자열에서 남은 0과 1만을 출력한다.

 

 

💥 유의사항

사전순으로 가장 빠른 것 출력하기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        String s = br.readLine();
        
        int zeroCnt = 0;
        int oneCnt = 0;
        
        for(char c : s.toCharArray()) {
            sb.append(c);
            
            if(c == '0')    zeroCnt++;
            else            oneCnt++;
        }
        
        // 0의 갯수와 1의 갯수 각각 절반값으로 교체
        zeroCnt /= 2;
        oneCnt  /= 2;
        
        // 1은 앞에서부터 없애기
        for(int i = 0 ; i < sb.length() ; i++) {
            if(sb.charAt(i) == '1') {
                sb.setCharAt(i, '2');
                oneCnt--;
            }
            
            if(oneCnt == 0)
                break;
        }
        
        // 0은 뒤에서부터 없애기
        for(int i = sb.length() - 1 ; i > -1 ; i--) {
            if(sb.charAt(i) == '0') {
                sb.setCharAt(i, '2');
                zeroCnt--;
            }
            
            if(zeroCnt == 0)
                break;
        }
        
        // 문자열에서 2가 아닌 0과 1만 출력
        for(int i = 0 ; i < sb.length() ; i++) {
            if(sb.charAt(i) == '1' | sb.charAt(i) == '0')
                System.out.print(sb.charAt(i));
        }
    }
}

 

---

💦 어려웠던 점

- 어떤 방식을 활용해야 할지 감이 잡히지 않았다.

 

 

🧐 새로 알게 된 내용

- 문제 해결 아이디어!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

 

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

 

백준 20310 자바 - 타노스 (BOJ 20310 JAVA)