[백준 1874번, 2164번] 스택과 큐(Java)

스택과 큐는 배열에서 발전된 형태의 자료구조이다.

 

스택

• 삽입과 삭제 연산이 후입선출(LIFO) -> 삽입과 삭제가 한쪽에서 일어남
• 용어
  • top : 삽입과 삭제가 일어나는 위치
  • push : top 위치에 새로운 데이터를 삽입하는 연산
  • pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
  • peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산
• DFS(깊이 우선 탐색), 백트래킹 종류의 코딩 테스트에 효과적

 

큐

• 삽입과 삭제 연산이 선입선출(FIFO) -> 삽입과 삭제가 양방향에서 일어남
• 용어
  • rear : 가장 끝 데이터를 가리키는 영역
  • front : 가장 앞 데이터를 가리키는 영역
  • add : rear 부분에 새로운 데이터를 삽입하는 연산
  • poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산
  • peek : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산
   
• BFS(너비 우선 탐색)에서 자주 쓰임

 

 

011. 스택으로 오름차순 수열 만들기(백준 1874번)

 

힌트 필수다

 

 

 

NO만 나와야 하는데 + - 도 다 나옴 ㅡㅡ

모아놨다가 출력해야하나바

 

 

 

StringBuilder를 사용하면 출력결과를 한 번에 출력할 수 있다.

 

pop() 으로 나온 값(st)이 수열의 수(S[i])보다 크면 StringBuilder가 아닌 "NO"를 출력해야하니까

boolean 타입의 변수를 둬서 "NO"를 출력할 땐 false로 StringBuilder가 출력이 되지 않도록하자

 

 

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] S = new int[n];
        for (int i = 0; i < n; i++) {
            S[i] = sc.nextInt();
        }

        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        boolean flag = true;
        int num = 1;
        for(int i = 0; i < n; i++){
            if(S[i] >= num){
                while(S[i] >= num){
                    stack.push(num++);
                    sb.append("+\n");
                }
                stack.pop();
                sb.append("-\n");
            } else {
                int st = stack.pop();
                if(st > S[i]) {
                    System.out.println("NO");
                    flag = false;
                    break;
                } else {
                    sb.append("-\n");
                }
            }
        }
        if(flag){
            System.out.print(sb.toString());
        }
    }
}

 

 

013. 카드 게임(백준 2164번)

 

가장 위의 카드를 가장 아래에 있는 카드 밑으로 옮기는 동작은 큐의 선입선출 성질을 이용하면 쉽게 구현할 수 있다.

카드의 개수가 500,000이므로 시간 복잡도 제약도 크지 않다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Queue<Integer> queue = new LinkedList<>();
        for(int i=1; i<=n; i++) {
            queue.add(i);
        }

        while(queue.size() > 1) {
            queue.poll();
            queue.add(queue.poll());
        }

        System.out.println(queue.poll());
    }
}

 

 

아 그리고 메타몽 나옴 💜