[JAVA] 백준 스택 부수기 1

 

 

괄호문제만 나오면 긴장하는 나 자신을 발견했다.

스택쪽만 집중적으로 부술 필요가 있을 것 같아서 스택 부수기를 해보려고 한다.

 

 

4889 안정적인 문자열 - 실버1

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

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringBuilder sb = new StringBuilder();
int idx = 1;
while (true) {
    String input = br.readLine();
    if (input.charAt(0) == '-') {
        break;
    }

    int result = 0;

    Deque<Character> stack = new ArrayDeque<>();
    for (int i =0; i<input.length(); i++) {
        char character = input.charAt(i);
        if (stack.isEmpty()) {
            stack.addLast(character);
            continue;
        }

        if (stack.peekLast() == '{' && character == '}') {
            stack.pollLast();
            continue;
        }

        stack.addLast(character);
    }

    //뺄 친구들은 다 뺀 상태
    while (!stack.isEmpty()) {
        char a = stack.pollLast();
        char b = stack.pollLast();

        if (a != '}') {
            result ++;
        }

        if (b != '{') {
            result++;
        }
    }

    sb.append(idx + ". " + result).append("\n");
    idx++;
}

System.out.print(sb);

 

일단 뺄 수 있는 걸 다 빼고, 스택형식으로 바꿔주면 어떤 케이스든 같은 변환 횟수가 나온다. 그래서 그대로 풀었더니 맞았다.

 

 

2841 외계인의 기타 연주 - 실버1

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

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

int melodyCnt = Integer.parseInt(st.nextToken());
int pretCnt = Integer.parseInt(st.nextToken());

boolean[][] visit = new boolean[7][pretCnt+1];

Deque<Integer>[] arr = new ArrayDeque[7];
for (int i =1; i<7; i++) {
    arr[i] = new ArrayDeque<>();
}

int result = 0;
for (int i =0; i<melodyCnt; i++) {
    st = new StringTokenizer(br.readLine());

    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());

    Deque<Integer> stack = arr[a];
    if (stack.isEmpty()) {
        stack.addLast(b);
        visit[a][b] = true;
        result ++;
        continue;
    }

    //떼야하는 상황
    int peek = stack.peekLast();
    while (peek > b) {
        int poll = stack.pollLast();
        visit[a][poll] = false;
        result++;

        if (stack.isEmpty()) 
            break;

        peek = stack.peekLast();
    }

    if (!stack.isEmpty()) {
        if (!visit[a][b]) {
            stack.addLast(b);
            visit[a][b] = true;
            result ++;
        }
    } else {
        stack.addLast(b);
        visit[a][b] = true;
        result ++;
    }
}

System.out.print(result);

 

문제를 잘못읽어서 시간이 많이 들었다. 다시 보니 각 줄 별 스택만 만들어주면 그닥 어렵지 않은 문제였다.

 

 

 

25918 북극곰은 괄호를 찢어 - 실버1

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

 

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    Stack<Character> st = new Stack<>();
    int ans = 0;
    int N = Integer.parseInt(br.readLine());
    String input = br.readLine();

    for (int i = 0; i < N; i++) {
        char c = input.charAt(i);
        if (st.empty() || c == st.peek()) {
            st.push(c);
        } else {
            st.pop();
        }
        ans = Math.max(ans, st.size());
    }

    if (st.empty()) {
        System.out.println(ans);
    } else {
        System.out.println(-1);
    }
}

 

감도 안잡혀서 다른 풀이를 보고 외웠다. 스택에 들어가있던 최대 개수를 구하면 쉽게 구할 수 있었다. 

아직 이런 풀이에 익숙하지 않아서 많이 풀어봐야겠다. 

 

 

25956 목차 세기 - 실버1

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

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());

        int[] input = new int[cnt];
        for (int i=0; i<cnt; i++) {
            int num = Integer.parseInt(br.readLine());
            input[i] = num;
        }

        if (input[0] != 1) {
            System.out.println(-1);
            return;
        }

        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{0,0});
        int[] result = new int[cnt+1];

        boolean isCorrect = true;
        for (int i =0; i<cnt; i++) {
            int num = input[i];

            if (stack.peek()[0] <= num) {
                if (num - stack.peek()[0] > 1) {
                    isCorrect = false;
                    break;
                }
                stack.push(new int[]{num, i+1});
                continue;
            }

            int count = 0;
            int prev = 0;
            while (stack.peek()[0] > num) {
                int[] tmp = stack.pop();

                if (prev != tmp[0]) {
                    result[tmp[1]] += count;
                    count = 1;
                    prev = tmp[0];
                } else {
                    count++;
                }
            }

            result[stack.peek()[1]] += count;
            stack.push(new int[]{num, i+1});
        }


        if (!isCorrect) {
            System.out.println(-1);
        } else {
            int count = 0;
            int prev = 0;
            while (stack.peek()[0] > 1) {
                int[] tmp = stack.pop();

                if (prev != tmp[0]) {
                    result[tmp[1]] += count;
                    count = 1;
                    prev = tmp[0];
                } else {
                    count++;
                }
            }
            result[stack.peek()[1]] += count;

            StringBuilder sb= new StringBuilder();
            for (int i =1; i<result.length; i++) {
                sb.append(result[i]).append("\n");
            }

            System.out.print(sb);
        }
    }
}

 

굉장히 좋은 stack문제라고 했는데 거의 10번을 틀렸다.

원인은 귀찮다고 StringBuilder없이 System.out으로 출력한 것..

힘들었지만 좋은 문제라고 생각한다. 더 간단한 풀이도 존재할 것 같다.

 

 

 

30892 상어 키우기 - 실버1

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

 

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int sharkCnt = Integer.parseInt(st.nextToken());
    int canEat = Integer.parseInt(st.nextToken());
    long sharkSize = Integer.parseInt(st.nextToken());

    PriorityQueue<Long> sharks = new PriorityQueue<>(sharkCnt);
    st = new StringTokenizer(br.readLine());
    for (int i =0; i<sharkCnt; i++) {
        sharks.add(Long.parseLong(st.nextToken()));
    }

    List<Long> sharkList = new ArrayList<>(sharkCnt);
    while (!sharks.isEmpty()) {
        sharkList.add(sharks.poll());
    }

    while (canEat > 0 && !sharkList.isEmpty()) {
        int start = 0;
        int end = sharkList.size();

        while (start < end) {
            int mid = (start + end)/2;

            if (sharkList.get(mid) < sharkSize) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        if (start == 0 && sharkList.get(0) >= sharkSize) {
            break;
        }

        sharkSize += sharkList.get(start - 1);
        sharkList.remove(start - 1);
        canEat--;
    }

    System.out.println(sharkSize);
}

 

시간을 줄일 수단으로 이진탐색을 사용했다. 하지만 값을 찾으면 해당 값을 없애고 다음 값을 찾아야하는 구조여서, 이진탐색 시 list.remove가 필수적이었다. list.remove의 시간복잡도는 O(n)이기 때문에(삭제를 위해 임시 배열을 생성하여 데이터 복사) 시간초과가 날까봐 걱정했지만 다행히 통과했다.

 

remove를 막 사용하지 않도록 visit 체크하는 방법도 생각했지만, 리스트의 크기가 커질수록 더 비효율적이라고 생각이 들었다. 그래서 일단 한 번 구현하고 시간복잡도를 비교해보려고 했는데.. 시간초과가 났다. 

 

 

그리고 스택으로 처리하는 방법으로도 한 번 구현해봤다.

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int sharkCnt = Integer.parseInt(st.nextToken());
    int canEat = Integer.parseInt(st.nextToken());
    long sharkSize = Integer.parseInt(st.nextToken());

    PriorityQueue<Long> pq = new PriorityQueue<>(sharkCnt);
    st = new StringTokenizer(br.readLine());
    for (int i =0; i<sharkCnt; i++) {
        pq.add(Long.parseLong(st.nextToken()));
    }

    Stack<Long> stack = new Stack<>();

    while (canEat > 0) {
        while (!pq.isEmpty() && pq.peek() < sharkSize) {
            stack.push(pq.poll());
        }

        if (stack.isEmpty()) {
            break;
        }

        sharkSize += stack.pop();
        canEat--;
    }

    System.out.println(sharkSize);
}

 

시간이 이진탐색보다 조금 크게 나왔는데, 테스트케이스의 특징때문이라고 생각한다. 상어를 굉장히 많이 먹을 수 있다면 스택을 쓰는 게 좋을 것 같고, 그 중 몇 개만 골라먹어야한다면 이진탐색이 빠를 것 같다.

 

 

 

 

 

2493 탑 - 골드5

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

 

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int topCnt = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());

    int[] result = new int[topCnt+1];
    Stack<int[]> stack = new Stack<>(); //height && index
    for (int i=1; i<=topCnt; i++) {
        int height = Integer.parseInt(st.nextToken());

        while (!stack.isEmpty() && stack.peek()[0] < height) {
            stack.pop();
        }

        if (stack.isEmpty()) 
            result[i] = 0;
        else 
            result[i] = stack.peek()[1];

        stack.push(new int[]{height, i});
    }

    StringBuilder sb = new StringBuilder();
    for (int i =1;i<result.length; i++) {
        sb.append(result[i] + " ");
    }

    System.out.println(sb);
}

 

스택에 잘 넣고빼면 어렵지 않은 문제다.

 

 

 

2504 괄호의 값 - 골드5

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

 

public class Main {
    static int OPEN1 = -1;
    static int OPEN2 = -2;
    static int CLOSE1 = -4;
    static int CLOSE2 = -3;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        boolean isNotCorrect = false;
        Stack<Integer> stack = new Stack<>();
        for (int i =0; i<input.length(); i++) {
            int value = 0;
            value = getValue(input, i, value);

            if (stack.isEmpty()) {
                stack.push(value);
                continue;
            }

            if (value == OPEN1 || value == OPEN2) {
                stack.push(value);
                continue;
            }

            //close인 상황
            int num = 1;
            if (stack.peek() > 0) {
                num = stack.pop();
            }

            if (stack.isEmpty()) {
                isNotCorrect= true;
                break;
            }

            Integer pop = stack.pop();
            if (pop + value == -5) {
                if (value == CLOSE1) {
                    num *= 2;
                } else {
                    num *= 3;
                }
            } else {
                isNotCorrect = true;
                break;
            }

            if (!stack.isEmpty() && stack.peek() > 0) {
                num += stack.pop();
            }

            stack.push(num);
        }

        if (stack.size() != 1 || isNotCorrect || stack.peek() < 0) {
            System.out.println(0);
        } else {
            System.out.println(stack.pop());
        }
    }

    private static int getValue(String input, int i, int value) {
        if (input.charAt(i) == '(') {
            return OPEN1;
        } else if (input.charAt(i) == ')') {
            return CLOSE1;
        } else if (input.charAt(i) == '[') {
            return OPEN2;
        } else {
            return CLOSE2;
        }
    }
}

 

이전에 너무 안풀려서 스트레스를 많이 받았던 문제다. 

이 문제는 고려해야할 상황이 많아서 설계자체를 잘해야한다는 걸 알고있었기 때문에 코드를 만지기 전 설계부터 했다. 그럼에도 예외 케이스 하나 ( ( )  때문에 99%에서 틀렸다... 괄호는 특히 예외 상황을 잘 고려해야하는 것 같다. 

 

정말 좋은 문제라서 몇 번 더 풀어보고싶다.