[백준] 알고리즘 분류(그리디 알고리즘,JAVA)2812번, 크게 만들기

문제 링크

2812번: 크게 만들기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. N자리의 숫자에서 K개의 숫자를 지웠을 때 가장 큰 값을 결과로 출력합니다.

2. 수는 0으로 시작하지 않습니다.

3. K는 N보다 항상 작습니다.

 

★ 이 문제를 처음 접근할 때 스택을 이용해서 접근하여 해결하였습니다.

다른 분들의 채점결과를 살펴보던 중 제가 작성한 것보다 시간효율이 압도적으로 좋은 것을 발견하게 되어서 코드를 분석하여 해당 코드로도 해결하였습니다.

이 문제에 설명하는 내용은 Stack을 사용하지 않고 문제를 해결한 분에 방법을 설명할 것이며, Stack을 사용한 방법은 코드에 주석을 통해서 간단하게 설명만 진행하도록 하겠습니다.

 

Stack을 사용하여 해결한 코드(1936ms Code)

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

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        String str = br.readLine();
        Stack<Integer> stack = new Stack<>();	//사용할 Stack
        StringBuilder sb = new StringBuilder();
        //숫자들을 탐색하여 Stack에 pop과 push를 진행
        for(int i=0;i<N;i++){
            int temp = charToInt(str.charAt(i));	//현재 숫자
            if(K==0){	//숫자를 지우는 횟수를 소모하였을 때
                stack.push(temp);	//남은 숫자 모두 Stack Push()
                continue;
            }
            //Stack이 비어있을 때 Push
            if(stack.isEmpty())
                stack.push(temp);
            //Stack.peek()값이 현재값보다 더 작을 때
            else if(stack.peek() < temp){	
                //숫자 지우기 진행
                stack.pop();
                K--;
                //Stack에 현재값보다 작은 숫자들도 지우기 진행
                while(!stack.isEmpty()){
                    if(stack.peek() >= temp || K == 0)
                        break;
                    stack.pop();
                    K--;
                }
                //현재값 Stack Push
                stack.push(temp);
            }else	//Stack.peek값이 현재값보다 클 경우 현재 숫자 push
                stack.push(temp);
        }
        //Stack에 저장된 수 StringBuilder 저장
        while(!stack.isEmpty()){
            int temp = stack.pop();
            if(K==0)
                sb.insert(0, temp);
            else	//지우는 소모 횟수가 남았을 때
                K--;
        }
        bw.write(sb.toString());	//숫자를 지운 후 최대값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //char → Int 변경 함수
    static int charToInt(char c){
        return Character.getNumericValue(c);
    }
}

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 지울 수 있는 범위에서만 탐색을 진행하여 숫자를 지우기 진행 

 

3. K개의 숫자를 지웠을 때 수를 결과로 출력합니다. 

 

 

숫자 지우기

 

가장 큰 값을 구하려면 앞의 있는 숫자들이 큰 숫자로 분포되어있어야 합니다.

 

앞부분부터 지울 수 있는 범위에서 큰 값이 올 수 있도록 탐색을 진행합니다.

 

N = 4, K = 2

 

수 : 2132일 때

 

 

2	1	3	2
(	~	)

2개의 숫자를 지울 수 있기 때문에 앞부분부터 지울 수 있는 범위를 탐색합니다.

2	1	3
X	X	최대값

최대값 : 3이기 때문에 앞에 있는 부분들은 2개(2, 1)를 지워줍니다.

다음 수가 올 수 있는 범위를 탐색합니다.

 

2	1	3	2
			(~)

범위안에 수가 2밖에 없기 때문에 2가 저장됩니다.

모든 수를 탐색하였으며 2개의 숫자도 지워졌기 때문에 저장된 값을 출력합니다.

 

가장 큰 값 : 32

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N : 7

K : 3

 

1

2

3

1

2

3

4

2. 지울 수 있는 범위에서만 탐색을 진행하여 숫자를 지우기 진행 

앞에서부터 지울 수 있는 범위 탐색

 

1	2	3	1	2	3	4
(	~	~	)

 

최대값 확인

 

1	2	3	1
X	X	최대값

 

최대값 : 3이기 때문에 앞에 있는 부분들은 2개(1, 2)를 지워줍니다.

 

다음 수가 지울 수 있는 범위를 탐색

1	2	3	1	2	3	4
			(	)

 

최대값 확인

 

1	2
X	최대값

 

최대값 : 2이기 때문에 앞에 있는 부분들은 1개(1)를 지워줍니다.

 

다음 수가 지울 수 있는 범위를 탐색

 

1	2	3	1	2	3	4
					(~)

 

최대값 확인

 

3

최대값

 

최대값 : 3이기 때문에 앞에 있는 부분들은 0개를 지워줍니다.

 

다음 수가 지울 수 있는 범위를 탐색

 

1	2	3	1	2	3	4
						(~)

 

최대값 확인

 

4

최대값

 

최대값 : 4이기 때문에 앞에 있는 부분들은 0개를 지워줍니다.

 

 

3. K개의 숫자를 지웠을 때 수를 결과로 출력합니다. 

 

3개(1, 2, 1)을 지운 수 : 3234 결과로 출력합니다.

 

1	2	3	1	2	3	4
X	X	O	X	O	O	O

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• Stream.of()를 사용하여 N자리의 수를 int[] 배열로 변경하여 저장하였습니다.
• 각 지울 수 있는 범위와 최대값을 구해서 숫자를 지우기 시작합니다.
• K개의 숫자를 모두 지웠을 때 수를 결과로 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

492ms Code

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int dif = N - K;
        //입력되는 N자리의 수 int 배열로 변경
        int[] num = Stream.of(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
        StringBuilder sb = new StringBuilder();
        int start = 0;	//범위 시작 위치
        //N자리 숫자 범위 탐색
        while(sb.length() < dif){
            //지울 수 있는 범위의 최대값 시작값으로 초기화
            int max = num[start];
            int id = start;
            //지울 수 있는 범위 탐색
            for(int i=start;i<=K+sb.length();i++){
                if(max == 9)	//9는 항상 가장 큰 값
                    break;
                if(max < num[i]){	//큰 값인지 비교하기
                    max = num[i];
                    id = i;
                }
            }
            //최대값 기준 앞에 숫자 지우기 및 저장
            start = id + 1;
            sb.append(max);
        }
        bw.write(sb.toString());	//K개의 수를 지운 값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}