프로그래머스 Stack / Queue 문제풀이 - Java

🍓 Stack

- 후입선출 특징을 가진 자료구조 

- add, pop, peek 

 

[ 괄호 회전하기 ]

https://school.programmers.co.kr/learn/courses/30/lessons/76502

프로그래머스

[ 로직 ]

- i개의 칸 만큼 원소 이동 시킨 후 괄호 가능 여부 개수를 센다. isPair함수 따로 빼서 구현 

- 시작 지점을 (index + i) % chars.length 로 주면 index칸만큼 뒤에서 시작하는 효과를 낼 수 있음 

- 문자열 읽으면서 여는 괄호가 나오면 스택에 닫는 괄호 형태를 넣어주고,  닫는 괄호 읽으면 같은 괄호 쌍이 스택에 있는지 확인

import java.util.*;
class Solution {
        public int solution(String s) {
            char[] chars = s.toCharArray();
            int answer = 0;
            for (int i = 0; i < s.length(); i++) {
                if (isPair(chars, i)) {
                    answer++;
                }
            }

            return answer;
        }

        public boolean isPair(char[] chars, int index) {
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < chars.length; i++) {
                char c = chars[(index + i) % chars.length];
                switch (c) {
                    case '[' -> stack.push(']');
                    case '{' -> stack.push('}');
                    case '(' -> stack.push(')');
                    case ')', '}', ']' -> {
                        if (stack.isEmpty()) return false;
                        if (c != stack.pop()) return false;
                    }
                }
            }
            return stack.isEmpty(); // 스택에 원소가 남아있다면 그것도 짝 안먖는 경우이므로 false
        }
    }

---

[ 주식가격 ]

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

[ 로직 ] 

- 각 가격의 위치에서 자신보다 작은 값이 어디에 최초로 등장하는지 출력하는 문제. 

- 가격이랑 인덱스(배열에서의 위치)를 클래스로 구현해서 스택에 넣었다. 

- 스택이 비어있지 않고, 스택의 탑 원소(stack.peek())가 현재 읽은 가격보다 크다면 가격이 떨어진 것! -> 이 경우 스택의 탑원소가 더 큰 값이 나올때까지 꺼내고, 꺼내진 애들의 index 토대로 계산해서 answer 배열에 넣기. 

- 스택에 남아있는 원소들은 끝까지 안 떨어진 or 맨 마지막에 들어간 원소이므로 prices.length에서 인덱스와 1을 빼준다. (0부터 시작하므로 1빼줌)

 

import java.util.*;
class Solution {
    public int[] solution(int[] prices) {
        Stack<Stock> stack = new Stack<>();
        int[] answer = new int[prices.length];
        for (int i = 0; i < prices.length; i++) {
            if (!stack.isEmpty() && stack.peek().price > prices[i])  {
                while (stack.peek().price > prices[i]) {
                    Stock temp = stack.pop();
                    answer[temp.index] = i - temp.index;
                    if (stack.isEmpty()) {
                        break;
                    }
                }
            }       
            stack.push(new Stock(prices[i], i));        
        }
        
        while (!stack.isEmpty()) {
            Stock stock = stack.pop();
            answer[stock.index] = prices.length - stock.index - 1;
        }
        return answer;
    }
    
    class Stock {
        int price;
        int index;
        Stock(int price, int index) {
            this.price = price;
            this.index = index;
        }
    }
}

 

 

---

🍓 Queue 

- 선입선출 

- add, poll, peek

 

[ 기능개발 ]

https://school.programmers.co.kr/learn/courses/30/lessons/42586

프로그래머스

[ 로직 ]

- 뒤에 있는 기능은 앞의 기능이 배포될 때 같이 배포되어야 함

- 날짜 계산을 해야하므로 현재 며칠이 지났는지 계산하는 day 변수 필요

- 함께 배포될 기능들 카운트 하는 count 변수 필요

- 각 기능별로 며칠 걸리나 계산해서 큐에 넣어놓고, 하나씩 꺼내면서 카운팅! 이때 올림 해야하는거 잊지말자

 

import java.util.*;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> answer = new ArrayList<>();
        for (int i = 0; i < progresses.length; i++) {
            int work = (int) Math.ceil((double) (100 - progresses[i]) / speeds[i]);
            queue.add(work);
        } // 큐에 걸리는 날짜 계산해서 넣어두기 
        
        int day = 0;
        int count = 0;
        while (!queue.isEmpty()) {
            int work = queue.poll();
            if (day < work) { // 더 걸리는 작업이 들어왔으면 앞에꺼 배포 
                if (day != 0) {
                    answer.add(count);
                    count = 0; // 같이 배포되는 작업 개수들 0으로 초기화 
                    
                }
                day = work; // 배포된 날짜로 경과한 날짜 갱신 
            }
            count++; // 앞기능 끝날때까지 기다려야하므로 카운트만 증가 
        }
        answer.add(count); // 뒤에 남은 애들도 배포해줘야하므로 카운트 변수도 정답에 추가 
        return answer.stream().mapToInt(Integer::intValue).toArray(); // 배열로 바꿔주기
    }
}

---

[ 다리를 지나는 트럭 ]

https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

[ 로직 ]

- 다리에 현재 얼만큼의 무게가 올라가 있는지 저장해둘 변수 bridgeWeight, 흐른 시간 측정용 answer, index는 인풋 배열에서 값 꺼내기 위한 변수 

- 큐 == 다리라고 생각. 다리 길이만큼 일단 0으로 큐에 넣어두기 

- 큐에서 하나 poll : 다리를 하나 지남, 다음 트럭이 올라갈 수 있을지 없을지 여부를 검사

    - 올라갈 수 있다면 큐에 넣고 bridgeWeight, index 증가시킴 

    - 올라갈 수 없다면 기다려야 함. 큐에 0을 넣는 이유는 큐 개수 다리 길이로 계속 맞춰놓으려고 

- answer( 시간 ) 증가시키기. 이 반복문을 모든 트럭이 다리에 오를 때까지 수행

 

모든 트럭이 올라가면 다리에 올라간 애들 다 지나갈 때까지 시간 재기 

 

import java.util.*;
class Solution {
    Queue<Integer> queue;
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int index = 0; // 트럭 어디까지 지났는지 체크용 인덱스 
        int answer = 0; // 총 시간(출력할 정답)
        int bridgeWeight = 0; // 현재 다리에 올라간 무게 
        queue = new LinkedList<Integer>();
        for (int i = 0; i < bridge_length; i++) {
            queue.add(0);
        }
        
        while (index < truck_weights.length) {
            bridgeWeight -= queue.poll();
            int temp = truck_weights[index]; // 다음 트럭 올라갈 수 있는지 검사
            if (temp + bridgeWeight <= weight) {
                queue.add(temp);
                bridgeWeight += temp;
                index++;
            } else {
                queue.add(0);
            }
            answer++;
        }
        
        // 다리에 올라간 애들 다 지나갈때까지 answer++
        while (bridgeWeight > 0) {
            bridgeWeight -= queue.poll();
            answer++;
        }
        
        return answer;
    }
}