코딩 테스트 문제 정리 - Stack (Gold 이하 문제)

멘토링 준비도 할 겸해서 코딩 테스트 고수 지인 분의 도움을 받아 코딩 테스트 문제를 조금씩 풀고 있다.

 

솔직히 피곤하고 힘들지만 한달간 꾸준히 푼 결과 solved.ac에서 측정하는 레벨이 꽤나 올랐다.

 

4~5년 정도 골드4에 주차되어 있었다.

 

어떤 카테고리부터 푸는게 좋을지 고민 중이었는데, 스택을 추천 받았다.

 

그런데, 스택 코딩 테스트 문제는 일반적인 자료구조 사용법과 같이 만만하지 않았다.

 

브론즈부터 벽을 좀 느꼈달까

 

문제를 푼 순서는 다음과 같다.

 

1. 막대기 : https://www.acmicpc.net/problem/17608

2. 괄호 : https://www.acmicpc.net/problem/9012

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

4. 스카이라인 쉬운거 : https://www.acmicpc.net/problem/1863

5. 오큰수 : https://www.acmicpc.net/problem/17298

 

스택 문제는 당연하지만 어떤 걸 스택에 넣고 꺼낼지가 중요하다.

 

문제가 쉬울 때는 일단 주어진 데이터를 스택에 다 넣고 뺄 때, 조건을 비교하고 출력하는 것이었다.

 

그런데, 문제가 어려워질수록 스택에 넣어야 하는 데이터의 조건이 복잡해지고 테스트 데이터 중간에 반드시 스택이 다 비는 경우가 존재해서 추가적인 처리가 필요하다.

 

그리고 몇 가지 테크닉이 눈에 띈다.

 

1. 스택 최상단의 데이터를 꺼내지 않고 확인할 수 있는 peek을 알아야 더 쉽게 접근이 가능하다.

2. 스카이라인 문제는 처음에 0을 넣어주면 정말 풀기 쉬워진다. 

3. 스택을 제외하고 초기 데이터를 저장해놓은 array가 필요할 수 있다.

4. index들을 함께 저장해야하는 경우가 있다. 그리고 index를 치환해가며 진행해나가야 하는 경우가 있다.

 

골드 문제부터는 난이도가 확 오르는걸 느꼈고, 코테가 어렵다는걸 다시 한번 느끼고 있다.

 

한창 취준할 때(4~5년 전)에도 코테 통과율이 60% 정도긴 했다.

 

1. 막대기

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

        int n = sc.nextInt();
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<n;i++) {
            int num = sc.nextInt();
            stack.push(num);
        }
        int max = 0;
        int count = 0;
        for(int i=0;i<n;i++) {
            int c = stack.pop();
            if(c > max) {
                count++;
                max = c;
            }
        }
        System.out.println(count);
    }
}

2. 괄호 

public class Main {
    public Main() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        for(int i = 0; i < N; i++) {
            String candidate = sc.next();
            Stack<String> stack = new Stack<>();
            boolean isVPS = true;
            for(int j = 0; j < candidate.length(); j++) {
                String str = String.valueOf(candidate.charAt(j));
                if("(".equals(str)) {
                    stack.push(str);
                } else {
                    if(!stack.isEmpty()) {
                        stack.pop();
                    } else {
                        isVPS = false;
                        break;
                    }
                }
            }
            if(!stack.isEmpty()) {
                isVPS = false;
            }
            System.out.println(isVPS ? "YES" : "NO");
        }
    }

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

3. 탑

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Tower {
    int index;
    int height;

    public Tower(int index, int height) {
        this.index = index;
        this.height = height;
    }

    int getIndex() {
        return this.index;
    }
    int getHeight() {
        return this.height;
    }
}

public class Main {
    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());		//탑 개수

        StringTokenizer st = new StringTokenizer(br.readLine());
        Stack<Tower> stack = new Stack<>();
        StringBuilder answer = new StringBuilder();
        for(int i=0;i<N;i++) {
            Tower tower = new Tower(i+1, Integer.parseInt(st.nextToken()));
            while(true) {
                // 스택이 비었다는건 최고점이라는 뜻
                if(stack.isEmpty()) {
                    stack.push(tower);
                    answer.append(0)
                          .append(" ");
                    break;
                }
                Tower peek = stack.peek();
                // 이전 값이 현재 들어온 값보다 작다. 클때까지 pop
                if(peek.getHeight() < tower.getHeight()) {
                    stack.pop();
                } else { // 이전 값이 현재 들어온 값보다 크다.
                    answer.append(peek.getIndex())
                          .append(" ");
                    stack.push(tower);
                    break;
                }
            }

        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws IOException {
        new Main();
    }
}

4. 스카이라인 쉬운거

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

        int N = sc.nextInt();
        int[] arr = new int[N];
        for(int i=0;i<N;i++) {
            sc.nextInt();
            arr[i] = sc.nextInt();
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int count = 0;
        for(int i=0;i<N;i++) {
            while(!stack.isEmpty() && stack.peek() > arr[i]) {
                stack.pop();
            }
            if(stack.isEmpty() || stack.peek() < arr[i]) {
                count++;
            }
            stack.push(arr[i]);
        }
        System.out.println(count);
    }
}

5. 오큰수

public class Main {
    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Stack<Integer> stack = new Stack<>();
        int[] array = new int[N];
        for(int i=0;i<N;i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }
        for(int i=0;i<N;i++) {
            while (!stack.isEmpty() && array[stack.peek()] < array[i]) {
                int index = stack.pop();
                array[index] = array[i];
            }
            stack.push(i);
        }

        while(!stack.isEmpty()) {
            array[stack.pop()] = -1;
        }

        StringBuilder answer = new StringBuilder();
        for(int i=0;i<N;i++) {
            answer.append(array[i]).append(" ");
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws IOException {
        new Main();
    }
}

 

개인적으로는 탑, 오큰수가 어려웠다.

 

스택에 어떤 데이터를 넣어야하는지부터가 혼란이 왔고, 초기 데이터 처리에 애를 먹었다.

 

결론은 둘 다 초기 데이터를 저장하는 배열을 따로 들고 있게끔 하면 되는 거였다. 

 

초기에 저장하는 정도로 반복문을 구성하는건 단순히 O(N)이라 메모리에 부담을 주지 않는 것 같다.

 

그리고 문제의 등급이 올라갈수록 O(N^2)를 허용하지 않는다.

 

O(N^2)이 허용되면 대부분 이중 for문으로 해결하면 되기 때문이지 싶다.