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

코드설명

그리디(탐욕법, Greedy) 문제입니다.

 

문자열 중 사전순으로 가장 빠른 것을 구하기 위해서는, 0이 앞에 가장 많아야하고, 1이 가장 뒤에 있어야 합니다.

1. 맨 앞에서부터 1 의 개수의 절반만큼 1을 발견하면 삭제합니다.

2. 맨 뒤에서부터 0 의 개수의 절반만큼 0 을 발견하면 삭제합니다.

코드

package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private static int N, M, Q, K;
private static char[] arr;
private static int answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// N = Integer.parseInt(st.nextToken());
// st = new StringTokenizer(br.readLine());
arr = st.nextToken().toCharArray();
int oneCnt = 0, zeroCnt = 0;
N = arr.length;
for(int i=0;i<N;i++) {
if(arr[i] == '1') {
oneCnt += 1;
}else if(arr[i] == '0'){
zeroCnt += 1;
}
}
//이제 앞에서부터 먼저 삭제처리를 하자.
//1을 삭제하자.
oneCnt /= 2; zeroCnt /= 2;
for(int i=0;i<N && oneCnt > 0;i++) {
if(arr[i] == '1') {
oneCnt -= 1;
arr[i] = 'X';
}
}
for(int i=N-1;i>=0 && zeroCnt > 0;i--) {
if(arr[i] == '0') {
zeroCnt -= 1;
arr[i] = 'X';
}
}
for(int i=0;i<N;i++) {
if(arr[i] != 'X') {
System.out.print(arr[i]);
}
}
}
}

+ Recent posts