스택 / 큐란?
스택(Stack)은 FIFO(First In First Out)
큐(Queue)는 LIFO(Last In First Out)
스택의 경우, 끝에서 삽입, 확인, 삭제연산이 일어날 경우 사용하고,
큐는 사용범위가 워낙 광범위해서 특정하기 힘든데, 일단 BFS에서 주로 사용한다.
🚀주요 사용하는 기능 in JAVA
Queue
Queue<V> queue = new ArrayDeque<>();
Queue<V> queue = new LinkedList<>();
Queue는 Interface이기 때문에, 위와같이 해당 인터페이스를 구현하는 두 가지 클래스로 생성하여, 저장할 수 있다.
이론적으로는 연결리스트의 특성을 갖는 LinekdList가 효율이 좋아야 하지만, 실제로는 여러 이유때문에 ArrayDeque이 속도가 조금 더 빠르다고 한다.
어차피 알고리즘 문제 내에서 큰 차이는 없을 것 같으니 아무거나 쓰자. 본 글에서는 ArrayDeque을 사용했다.
Stack
Stack<V> stack = new Stack<>();Stack은 위의 Queue와는 달리 인터페이스가 아니라 클래스다. 그렇기 때문에 귀찮은 고민할 필요 없이 Stack 클래스로 생성한 인스턴스를 저장해주고 사용하면 된다.
프린터 (Level 2)
Queue에 대한 기본적인 활용 문제.
KeyPoint는 같은 값이 중복해서 들어갈 수 있기 때문에, location에 해당하는 값에 대한 표시가 필요하다는 것. 일반적으로 다음과 같은 두가지 방법이 해결법이 될 수 있다.
1.각 요소를 Paper 클래스로 묶는다.
2.location변수를 Queue의 값 이동과 함께 이동시킨다.
전에도 이 문제를 한 번 풀어본 적이 있었는데 당시엔 2번 방법을 통해 풀었었고, 이번엔 1번 방법으로 풀어봤다.
import java.util.*;
class Solution {
public int solution(int[] priorities, int location) {
Queue<Paper> queue = new ArrayDeque<>();
for(int i=0 ; i<priorities.length ; i++){
Paper p = new Paper(priorities[i]);
if(i == location){
p.my = true;
}
queue.add(p);
}
Arrays.sort(priorities);
int pointer = priorities.length -1;
int answer = 1;
while(!queue.isEmpty()){
Paper p = queue.poll();
if(p.priority == priorities[pointer]){
if(p.my){
return answer;
}
answer++;
pointer--;
}else{
queue.add(p);
}
}
return answer;
}
}
class Paper{
int priority;
boolean my;
Paper(int priority){
this.priority = priority;
this.my = false;
}
}탑 (Level 2)
역시 별다른 설명이 필요없을 정도로 기초적인 문제.
사실 예전에 비슷한 문제로 애먹은 경험이 있어서, 처음 맞딱뜨렸을 때는 살짝 고민했었는데, 문제의 탑의 개수제한(100이하, 즉 O(N^2)이어봤자 10000번 남짓..)을 보고 그냥 이중 for문으로 풀어버리기로 했다.
실제로 별 문제없이 풀렸다.
class Solution {
public int[] solution(int[] heights) {
int len = heights.length;
int[] answer = new int[len];
for(int i=0 ; i<len ; i++){
boolean flag = false;
for(int j=i-1 ; j>=0 ; j--){
if(heights[j]>heights[i]){
flag = true;
answer[i] = j+1;
break;
}
}
if(!flag){
answer[i] = 0;
}
}
return answer;
}
}쇠막대기 (Level 2)
다른사람들 풀이를 보니 대부분 Stack자료구조를 사용하고 있다. 근데 난 안썼다.
솔직히 이 문제의 경우엔, 안쓰고 푸는게 더 쉽다고 생각한다.
Stack은 자료구조다. 자료구조는 안에 값을 저장하고 꺼내는 역할을 하기 위해 존재한다.
하지만 이 문제의 경우 값을 저장하고 꺼낼 필요가 없다.
그렇기 때문에, 어느정도까지 막대기가 중첩됐는지를 표시해 줄 int형 변수 하나를 선언해주는 것으로 충분하다.
class Solution {
public int solution(String arrangement) {
int stack = 0 ;
int answer = 0;
for(int i=0 ; i<arrangement.length() ; i++){
char c = arrangement.charAt(i);
if(c == '('){
if(arrangement.charAt(i+1) == ')'){
//레이저 확정
answer += stack;
i++;
}else{
stack++;
}
}else{
answer++;
stack--;
}
}
return answer;
}
}다리를 지나는 트럭 (Level 2)
위 문제처럼 굳이 억지로 스택/큐를 사용할 필요는 없다고 생각한다.
그렇기 때문에 이번 문제도 조금 특이하게 HashMap을 통해 풀었다.
이 문제를 보다보니, SWEA의 유명한 고난이도 문제인 원자소멸 시뮬레이션 가 생각이 났는데, 거기서 아이디어를 조금 착안해냈다.
바로 미래의 도착시간을 저장하는 것! 이다. 이렇게하면 time변수만 설정해서 1씩 증가시키기만 해도, 해당 시간에 다리를 빠져나가는 트럭이 있는 지 알 수 있다.
만약 Queue로 풀었다면, Truck 클래스를 따로 정의해서, 빠져나가는 시간을 함께 저장하는 식으로 담아 Queue에 저장했을 것 같다.
import java.util.*;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
HashMap<Integer, Integer> map = new HashMap<>();
int time = 1;
int total = 0;
int p = 0;
while(true){
if(map.containsKey(time)){
total -= map.get(time);
map.remove(time);
}
if(total + truck_weights[p] <= weight){
map.put(time+bridge_length, truck_weights[p]);
total += truck_weights[p];
p++;
if(p == truck_weights.length){
return time + bridge_length;
}
}
time++;
}
}
}기능개발 (Level 2)
남은 개발량을, 개발 속도로 나눠서 시간을 구하면.
위의 탑문제와 거의 동일한 방법으로 풀 수 있다. 그러니 설명은 생략~
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
int len = speeds.length;
int[] patch = new int[len];
for(int i=0 ; i<len ; i++){
patch[i] = ( 100 - progresses[i])/speeds[i];
if((100-progresses[i]) % speeds[i] != 0){
patch[i]++;
}
}
ArrayList<Integer> arr = new ArrayList<>();
int i = 0;
while(i<len){
int tmpA = patch[i];
int tmpV = 0;
while(i<len && tmpA>=patch[i]){
i++;
tmpV++;
}
arr.add(tmpV);
tmpV=0;
}
int[] answer = new int[arr.size()];
for(i=0 ; i<arr.size() ; i++){
answer[i] = arr.get(i);
}
return answer;
}
}주식가격 (Level 2)
최장증가 부분수열 유사문제.
가격이 떨어지지 전까지의, 최장거리. 만약 어떤 시점에 가격이 주어졌다면 그 가격은 무엇이랑 비교해야 될까?
바로 가장 최근 주식의 가격일 것이다.
왜냐면 가장 최근 주식 가격에 비해 떨어졌다면, 이전 시점 주식의 가격이 떨어지지 않은 기간즉 정답배열의 값을 갱신시켜야 하기 때문이다.
여기서 핵심은 가장 최근 주식 가격이 중요하다는 점이다. 이는 자료구조의 측면에서 얘기하자면 가장 끝 부분에서 계속 넣고, 확인하고 빼는 연산이 이뤄진다는 것.
이러한 특성을 가진 자료구조는? STACK!!
import java.util.*;
class Solution {
public int[] solution(int[] prices) {
Stack<Joo> stack = new Stack<>();
int len = prices.length;
int[] answer = new int[len];
for(int i=0 ; i<len ; i++){
while(!stack.isEmpty() && stack.peek().price>prices[i]){
Joo j = stack.pop();
answer[j.time] = i - j.time;
}
stack.push(new Joo(prices[i], i));
}
while(!stack.isEmpty()){
Joo j = stack.pop();
answer[j.time] = len - j.time-1;
}
return answer;
}
}
class Joo{
int time;
int price;
Joo(int price, int time){
this.price = price;
this.time = time;
}
}