크게 만들기

📍 문제 설명

 

💡 접근

처음에 n개중에 k개를 제외시키는 조합으로 접근했으나 N의 범위가 커서 메모리 초과 판정을 받았다.

Stack을 이용하여 풀 수 있었다.

1.첫번째의 값은 무조건 큐에 넣어둔다.

2.스택 마지막 값 보다 현재 값이 더 작으면 스택에 넣어준다.

3.스택 마지막 값 보다 현재 값이 더 크면 pop 시켜주는 작업을 반복한다.

4.지워야하는 횟수를 모두 채웠으면 나머지 남은 숫자들을 더해준다.

5.지워야하는 횟수를 모두 채우지 않고 반복문이 끝났다면 지워야하는 횟수만큼 pop 시켜준다.

👩‍💻 코드

import java.util.*;

public class Main {
    static long n, m, k, cnt, max, min, sum, count, r, c, result, answer = Integer.MAX_VALUE;
    static char[][] board, clone, dis;
    static boolean[][] visited;
    static String str;
    static int[] ch, pm, combi, graph, temp;
    static boolean flag = false;
    static int[] dx = {-1, 0, 1, 0,}; //북동남서
    static int[] dy = {0, 1, 0, -1};
    static ArrayList<Integer> list = new ArrayList<>();

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        k = kb.nextInt();
        kb.nextLine();
        str = kb.nextLine();
        if(n==k) System.out.println(0);
        else T.solution();
    }


    private void solution() {
        Stack<Character> s = new Stack<>();

        //숫자를 지운 횟수
        int cnt = 0;

        //첫번째 값은 무조건 먼저 넣어두기
        s.push(str.charAt(0));

        for (int i = 1; i < str.length(); i++) {
            if(s.peek() > str.charAt(i)) s.push(str.charAt(i));
            //현재값이 더 크면 계속 꺼내고 푸시해
            else {
                while (!s.isEmpty() && s.peek() < str.charAt(i)) {
                    char c = s.peek();
                    //스택 꼭대기의 값과 현재의 값을 비교
                    //현재의 값을 꺼내고 지운 횟수를 증가시켜준다.
                    s.pop();
                    cnt++;
                    if(cnt == k) break;
                }
                //지금 있는 값을 넣어준다.
                s.push(str.charAt(i));//[7,7,5,8]
                //나머지 숫자를 더해줘야한다.
                if(cnt == k) {
                    while(i++ < str.length()) {
                        if(i >= str.length()) break;
                        s.push(str.charAt(i));
                    }
                }
            }
        }
        //다 지우지 않았는데 for문이 끝나는 경우도 있다..
        if(cnt != k) {
            while(true) {
                s.pop();
                cnt++;
                if(cnt == k) break;
            }
        }

        StringBuffer numberStr = new StringBuffer();
        for(char x : s) numberStr.append(x);
        System.out.println(numberStr);
    }
}