프로그래머스 코딩테스트 고득점 Kit : 스택/큐(Java)

1. 같은 숫자는 싫어(Level 1)

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12906

프로그래머스

 

문제 풀이

import java.util.*;

public class Solution {
    public int[] solution(int[] arr) {
        Stack<Integer> stack = new Stack<>();
		
        stack.push(arr[0]);
        for(int i=1; i<arr.length; i++) {
            if(stack.peek() != arr[i]) {
                stack.push(arr[i]);
            }
        }

        List<Integer> answer = new ArrayList<>();
        for(int i=0; i<stack.size(); i++) {
            answer.add(stack.get(i));
        }

        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

---

2. 기능 개발(Level 2)

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

프로그래머스

 

문제 풀이

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer> q = new LinkedList<>();
		List<Integer> answer = new ArrayList<>();
		
		int[] day = new int[progresses.length];
		for(int i=0; i<progresses.length; i++) {
			int num = 1;
		    while(speeds[i]*num + progresses[i] < 100) {
			    num++;
			}
			day[i] = num;
        }
		
		for(int i=0; i<day.length; i++) {
			q.offer(day[i]);
        }
        
        while(!q.isEmpty()) {
            int max = q.poll();
            int cnt = 1;
            while(!q.isEmpty() && q.peek() <= max) {
                q.poll();
                cnt++;
            }
            answer.add(cnt);
        }
        
        return answer.stream().mapToInt(Integer::intValue).toArray();
	}
}

 

* ArrayList -> arr 변환 코드

int[] arr = ArrayList.stream().mapToInt(Integer::intValue).toArray();

---

3. 올바른 괄호(Level 2)

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

 

문제 풀이

전형적인 스택을 사용하는 괄호 문제이다.

 

1. ')'로 시작하는 문자열은 올바른 괄호가 될 수 없다. -> 바로 false 반환

2. '('일 경우, 스택에 넣는다.

3. ')'일 경우, 스택에 있던 '('을 빼준다. -> pop()

4. 스택이 비었을 경우 올바른 괄호가 될 수 있다.

import java.util.*;

class Solution {
    boolean solution(String s) {
        Stack<Character> stack = new Stack<>();

        if(s.charAt(0) == ')') {
            return false;
        }
        
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if(c == '(') {
                stack.push(c);
            } else if(c == ')') {
                if(!stack.isEmpty()) {
                    stack.pop();
                }
            }
        }
        
        if(stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}

---

4. 프로세스(Level 2)

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42587

프로그래머스

 

문제 풀이

우선순위 큐 사용

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int answer = 0;
		
        for(int i=0; i<priorities.length; i++) {
            pq.offer(priorities[i]);
        }
		
        while(!pq.isEmpty()) {
            for(int i=0; i<priorities.length; i++) {
                if(pq.peek() == priorities[i]) {

                    pq.poll();
                    answer++;
                    
                    if(i == location) {
                        pq.clear();
                        break;
                    }
                }
            }
        }
        return answer;
    }
}

---

5. 다리를 지나는 트럭(Level 2)

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

프로그래머스

 

문제 풀이

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        
        Queue<Integer> q = new LinkedList<>();
        
        int sum = 0;
        int time = 0;
        
        for(int i=0; i<truck_weights.length; i++) {
            int nowWeight = truck_weights[i];
            while(true) {
                if(q.isEmpty()) {
                    // 최초 진입
                    q.offer(truck_weights[i]);
                    time++;
                    sum += truck_weights[i];
                    break;
                } else if(q.size() == bridge_length) {
                    // 다리가 꽉 찼다면 : 진입 불가능
                    sum -= q.poll();
                } else if(q.size() < bridge_length && sum + nowWeight <= weight)  {
                    // 다리에 올라갈 수 있는 최대 수보다 적게 올라가 있고, 총 무게 이하라면 : 진입 가능
                    q.offer(nowWeight);
                    sum += nowWeight;
                    time++;
                    break;
                } else if(sum + nowWeight > weight) {
                    // 무게가 꽉 찼다면 : 진입 불가능
                    q.offer(0);
                    time++;
                } 
            }
            
        }
        return time + bridge_length;
    }
}

---

6. 주식 가격(Level 2)

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

프로그래머스

 

문제 풀이

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
		int[] answer = new int[prices.length];
        /*
		for(int i=0; i<prices.length-1; i++) {
			int num = 0;
			for(int j=i+1; j<prices.length; j++) {
                num++;
				if(prices[i] > prices[j]) {
					break;
				}
			}
			answer[i] = num;
		}
        */
        
        Stack<Integer> stack = new Stack<>();
        // 주식이 떨어지면 answer에 넣고 동일하거나 증가하면 stack에 넣음
        for(int i=0; i<prices.length; i++) {
            while(!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                answer[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        
        // stack에 남아있는 값은 끝까지 주식이 떨어지지 않은 경우
        while(!stack.isEmpty()) {
            answer[stack.peek()] = prices.length - stack.peek() - 1;
            stack.pop();
        }
        return answer;
    }
}