Algorithm

[99클럽 코테 스터디 12일차 TIL] dp, set, stack

kimphoby 2025. 4. 15. 18:26

📌  키워드 

  • dynamic programming 
  • set
  • stack 

 📌  문제및 문제별 키워드 

 

Beginner : 임스와 함께하는 미니 게임  _ O(n)

보자마자 자료구조 하나가 바로 툭 떠올라서 쉽게 풀었던 문제이다. 임스가 게임을 할 인원을 찾는데, 중복된 인물을 제외하고 게임을 한다. 가능한 게임 판 수를 구하면 되는 문제이다. 중복을 제거한다 했을때 바로 떠올릴 수 있는건 set, map 인데, pair는 필요없으니 set을 사용하면 된다. 

 

입력 받은 모든 이름을 set에 저장하면 알아서 중복된 인원이 제거되고 key 값들만 남는다. set 의 size 가 바로 참여 가능한 인원이 된다. 

그러면 각 게임 한판을 진행하는 것에 필요한 인원을 구해 전체 인원에서 나누면 된다. 이따 게임 한판당 필요한 인원에는 임스도 포함되어 있으므로  총 진행 가능한 게임 판 수는 stack.size() / (게임 한판당 필요한 인원 수 - 1) 이다. 

 

class Main {
    public static void main(String[] args) throws IOException {
        // 입력 :  게임 신청 횟수 n , 게임 중류 (Y, F, O => 2,3,4)
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 로직 : 동일한 사람과 게임을 진행하지 않음. 총 몇번 할 수 있을까?
        String[] inputs = br.readLine().split(" ");
        int n = Integer.parseInt(inputs[0]);
        String kind = inputs[1];
        Set<String> set = new HashSet<String>();
        for(int i=0; i<n; i++){
            set.add(br.readLine());
        }
        int result;
        if (kind.equals("Y")) result = set.size() / 1;
        else if (kind.equals("F")) result = set.size()  / 2;
        else result = set.size() / 3;

        System.out.println(result);
    }
}

 

Middler : 포도주 시식  _  O(n)

힌트를 봐서 dp로 푼다는 것까지 알고 있었는데도도저히 안풀려서 구글링했다. (dp 최약체..)  이해는 했지만 로직이 크게 와닿지 않아서 다음에 한번 더 풀어봐야될 것 같다. 주석은 나만 알아듣게 작성한 점이 좀 있는 것  같아서 참고하지 않는 것을 추천한다. 

 

wine[i] :  i 번째 포도주 용량

dp[i] :  i 번째 포도주까지 고려했을때 먹을 수 있는 최대 용량 , Max(case1, case2, case3) 

  • case1 : i 번쨰 와인을 먹지 않을 때,  dp[i-1]
  • case2 : i-1 번째 와인을 먹지 않을때, dp[i-2] + wine[i]
  • case3 : i-2 번째 와인을 먹지 않을 때, dp[i-3] + wine[i-1] + wine[i-2]
class Main {
    public static void main(String[] args) throws IOException {
        // 입력 : n (1<= n <=10000) , n개 포도주의 양 각각 나열
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 로직 : 연속으로 놓여있는 3잔을 모두 마실 수는 없다.
        int[] wine = new int[n];
        int[] dp = new int[n];

        for(int i=0; i<n; i++){
            wine[i] = Integer.parseInt(br.readLine());
        }

        if (n==1) {
            System.out.println(wine[0]);
            return;
        }
        else if (n==2) {
            System.out.println(wine[0] + wine[1]);
            return;
        }

        dp[0] = wine[0];
        dp[1] = wine[0] + wine[1];
        int temp = Math.max(dp[1],dp[0] + wine[2]); // 나자신 제외, 중간 제외
        dp[2] = Math.max(temp, wine[1] + wine[2]); // 맨 왼쪽 제외

        for (int i=3; i<n; i++){
            temp = Math.max(dp[i-1],dp[i-2]+ wine[i]); // 맨 오른쪽 제외, 중간 제외
            dp[i] = Math.max(temp,dp[i-3] + wine[i-1] + wine[i]); // 맨 왼쪽 제외
        }
        // 출력 : 최대로 마실 수 있는 포도주의 양 (2초)
        System.out.println(dp[n-1]);
    }
}

실수 했던 점

n==1, n==2 일때에 대한 예외처리를 해주지 않아서 dp 생성 과정에서 인덱스 범위 초과 오류가 났었다. 

 

Middler : 쇠막대기 _ O(n)

day7 때 못 풀었던 문제 오늘 풀었다. 

 

<첫번째 시도>

레이저로 잘리는 쇠막대의 갯수를 구하면 되는 문제인데, 패턴을 발견하기 어려워서 처음에는 아래와 같이 풀었다가 시간 초과가 났다. 최막대의 시작 위치, 끝나는 위치를 쌍으로 저장하고, 레이저의 위치도 저장한다. 한번의 반복문으로 모두 저장했을때, 2중 반복문(<--- 당연한 시간 초과 원인) 각 막대당 레이저가 몇개 위치하는지를 구해서 전체 총합을 했다. 

 

 

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

        ArrayList<Integer> laser = new ArrayList<>();
        ArrayList<Pair> pipe = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        /*
            로직 :  그냥 막대의 시작지점과 끝지점을 모두 구함, 레이저의 위치도 구함 (레이저는 시작 위치도 구함)
            각 막대에 대해 사이에 존재하는 레이저의 수를 모두 구하면 된다. => 시간 복잡도 예측이 잘 안된다.
         */
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);

            if (c == '(') {
                stack.add(i);
            }
            else if (c == ')') {

                // 레이저인 경우
                int start_point = stack.pop();

                if (start_point == i-1) {
                    laser.add(start_point);
                }

                else{
                    pipe.add(new Pair(start_point,i));
                }
            }
        }

        int answer = 0;
        /*
            레어저 포인터가 해당 위치에서 레이저를 쏘았을때 잘려진 쇠막대기의 총 갯수
         */

        for (Pair p : pipe){
            int laserPerPipe = 0;
            for (int l : laser){
                if (l < p.end && l > p.start){
                    laserPerPipe++;
                }
            }
            answer += (laserPerPipe + 1);
        }
        System.out.println(answer);
    }

}
class Pair {
    public int start;
    public int end;
    public Pair(int start, int end){
        this.start = start;
        this.end = end;
    }
}

 

<두번째 시도>

패턴을 발견하고 나서야 O(n)으로  문제를 풀 수 있었다. stack이 키워드인 문제인데.. 그냥 '(' 의 갯수만 필요한 문제라서 stack 안써도 될 것 같다. 나는 연습겸 굳이 stack을 썼다. 

 

  • 레이저 () 발견 => stack 에 들어있는 사이즈만큼의 막대 발생 => cnt += stack.size() 
  • 막대의 끝 ')' 발견 => 막대 갯수 하나 추가 =>  cnt +=1 
  • 막대 시작점 '(' => stack에  ( 위치 추가
class Main {
    public static void main(String[] args) throws IOException {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        // 로직 :  레이저 () => stack 에 쌓여있는 ( 갯수만큼 잘린다.
        //        막대 끝점 ) => 막대 갯수 1 추가
        //        막대 시작점 ( => stack에 추가
        int cnt_sticks = 0;
        for (int i = 0; i < input.length(); i++) {

            if (input.charAt(i) == '(') {
                stack.add(i);
            } else if (input.charAt(i) == ')') {
                int peek = stack.pop();
                // 레이저인 경우
                if (peek == i - 1) {
                    cnt_sticks += stack.size();
                } else { // 막대의 끝점인 경우
                    cnt_sticks += 1;
                }
            }
        }
        System.out.println(cnt_sticks);
    }
}