Part 05 Stack과 Queue

  Note) list interface의 메서드

  - list.remove(인덱스) : 꺼내서 제거 - pop()

    -> 인덱스 말고 데이터의 값을 제거하려면? 

    ex) 데이터가 int일 때 =>  list.remove(Integer.valueOf(지우고 싶은 값)) 으로도 표현 가능

  - list.get(인덱스): 꺼내서 보여준다. - peek()

 

1. Stack

  - LIFO구조

  - push / pop / peek

 

2. Queue

  - FIFO구조

  - offer / poll / peek

 

3. Deque

  - 앞이나 뒤에서도 꺼낼 수 있다.

  - 인터페이스로 제공

  - offer(First / Last) / poll(First / Last) / peek(First / Last)

 

 

  Ex) 올바른 괄호 

  - 괄호가 올바르게 입력되는지 확인

  - s.toCharArray(): String s를 char [] 배열로 바꾼다.

java

열기 줄바꿈

import java.util.*;
class Solution {
	boolean solution(String s) {
		Stack<Character> stack = new Stack<>();
		
		for(char c : s.toCharArray()) {     // 매개변수 s를 char[]배열로 바꾸어 한 글자씩 확인한다. 
		
			if(c == '(') {                  // "("가 들어올 때마다 push()한다.
				stack.push(c);              // 
			}else {
				if(stack.isEmpty()) return false;   	//우괄호가 과하게 들어오는 경우
				stack.pop();                            
                //empty()가 거짓일 때(즉 스택에 좌괄호 원소가 있을 때),  pop()해준다.
			}
		}
        return stack.isEmpty() == true;
	}
}

 

  Ex) 기능 개발 

  - 순서대로 입력받아 처리하므로 Queue를 이용한다.

    -> 각 작업이 앞으로 며칠 더 걸리는지 구해서 daysQueue에 넣는다.

  - int d = (100 - progresses[i] + speeds[i] - 1) / speeds[i]; 

     -> 나누는 수보다 1작은 수(speeds[i] - 1)를 분자에 더해주면 기존 값( (100 - progresses[i]) /  speeds[i]  ) 을 올림한 상태로 계산할 수 있다.

    -> 그러면 Math.ceil()과 같은 결과가 나온다. 

  - 마지막에 cnt를 꼭 넣어줘야한다. 

java

열기 줄바꿈

import java.util.*;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
       
        Queue<Integer> daysQueue = new LinkedList<>();
        Queue<Integer> resQueue = new LinkedList<>();

        for(int i = 0;i < progresses.length; ++i) {
            int d = (100 - progresses[i] + speeds[i] - 1) / speeds[i];  
            // 올림한다. ceil()과 같음
            
            daysQueue.offer(d);
            // daysQueue = [7, 3, 9] 로부터 [2, 1]을 반환하도록 한다.
            // 즉, [7 2] [9]로 찢어서 [2, 1]를 반환하도록 한다.
        }

        int day = daysQueue.poll();     // 7
        int cnt = 1;

        while(!daysQueue.isEmpty()){
            int n = daysQueue.poll();   // 3
            
            if(day >= n){       //  기준값(day)보다 작은 값이 나오면? (기준값보다 큰 값이 나올 때 까지 ++cnt)
                ++cnt;
                continue;
            }
            
            // 기준값(day)보다 n이 큰 경우는?
            // 현재 cnt를 resQueue에 넣고 cnt를 1로 초기화해야하는 상황
            resQueue.offer(cnt);
            cnt = 1;
            day = n;    // 7이었던 비교 기준이 9로 바뀐다.
        }
        
        resQueue.offer(cnt);    // 마지막 데이터에 대한 cnt를 넣는다.
        return resQueue.stream().mapToInt(Integer::intValue).toArray();
    }
}

 

 

  Ex) 주식 가격

  - 초 단위로 기록된 주식 가격이 담긴 배열 prices가 매개변수로 주어질 때,

  - 가격이 떨어지지않은 기간은 몇 초인지 return하는 함수를 만든다.

  - j는 i+1부터 비교한다.

  - 가격이 작아지면 반복문 break

java

열기 줄바꿈

class Solution {
    public int[] solution(int[] prices) {
       
        int []answer = new int[prices.length];
      
        for(int i = 0; i < prices.length; ++i){
            int price = prices[i];
            int seconds = 0;
            
            for(int j = i + 1; j < prices.length; ++j){
                ++seconds;      //  가격이 떨어지지 않으면 계속 카운트한다.
                if(price > prices[j]) break;    // 가격이 떨어지면 반복문 break
            }
            
            answer[i] = seconds;
        }
        return answer;
    }
}

 

 

  Ex) 프린터: 중요한 문서를 먼저 인쇄한다. 이 때, 맨 앞의 문서는 뒤로 밀려난다.

java

열기 줄바꿈

import java.util.*;
class Solution {
    class Paper{            // 새로운 클래스 Paper( Int p, boolean isMine), 
        boolean isMine;		// 내문서인지 아닌지
        int priority;		// 우선순위
        Paper(int p ,boolean m){ 	// Paper 생성자
            priority = p; 
            isMine = m; 
        }
    }
    
    public int solution(int [] priorities, int location){   
        // 문서의 중요도 나타내는 배열 priorities
        // 내가 요청한 문서 번호 location
        
        List<Paper> q = new LinkedList<>();		// 중간에 있은 값을 가져오기 위해 큐보다는 List가 적당
        
        for(int i = 0; i < priorities.length; ++i){
            q.add(new Paper(priorities[i], i == location)); 
            // Paper( 우선순위 , i==location) 형태로 큐에 넣기
            // 내문서인지 아닌지 확인
        }
        
        int answer = 0; // 내문서를 뽑을 수 있는 차례
        while(!q.isEmpty() ){
            
            Paper now = q.remove(0);	// List에는 poll()이 없어서 remove로 꺼내온다.
            boolean printable = true;
            
            for(Paper p : q){       // q의 모든 Paper객체 p에 대해
                if(now.priority < p.priority){
                    printable = false;
                    break;   
                }
            }
            
            if(!printable){     // printable이 false이면 출력하지 않고 q에 now를 넣는다. (q의 맨 뒤에)
                q.add(now);		// q의 맨뒤에 추가한다.
                continue;		// 다음 루프로..
            }
            
            ++answer;       // 프린트 가능해질 때까지 answer가 1씩 커진다. 
            
            if(now.isMine) return answer;
           }         
           return answer;                         
    }
}

 

 

 

출처: https://programmers.co.kr/learn/courses/13577

[Java] 어서와! 자료구조 알고리즘은 처음이지?