본문 바로가기
코딩테스트

[JAVA] 스택, 큐, 덱

you__me 2024. 2. 6. 11:12

28728 스택 2

import java.io.*;
import java.util.Stack;

public class Main {

    static Stack<Integer> stack = new Stack<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        while(N --> 0){
            solution(br.readLine());
        }

        br.close();

        System.out.println(sb);
    }

    static void solution(String query){
        char c = query.charAt(0); //첫번째 문자는 명령어

        switch (c){
          case '1' : stack.push(Integer.parseInt(query.substring(2))); return; // idx=1은 공백문자
          case '2' : sb.append(stack.isEmpty() ? -1 : stack.pop()).append("\n"); return;
          case '3' : sb.append(stack.size()).append("\n"); return;
          case '4' : sb.append(stack.isEmpty() ? 1 : 0).append("\n"); return;
          case '5' : sb.append(stack.isEmpty() ? -1 : stack.peek()).append("\n"); return;
          default: break;
      }
    }
}

JAVA에서 제공하는 Stack의 메소드를 이용하여 푼다.

While(N --> 0) 은 증감연산자(--)와 비교 연산자(>)를 합친 것이라 한다. 처음 알았는데 유용할듯!

코드를 최대한 간편하게 하려면 switch-case 구문이 좋은 것 같다. 여기에 삼항연산자까지 이용했다.

 

나도 비슷하게 작성해서 풀었는데 나는 왜 답이 안나왔을까...풀다 넘 화났음

10773 제로

import java.io.*;
import java.util.Stack;

public class Main {

    static Stack<Integer> stack = new Stack<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        while(N --> 0){
            solution(br.readLine());
        }

        br.close();

        int sum = 0;
        while (stack.size() > 0) sum += stack.pop();
        System.out.println(sum);
    }

    static void solution(String query){
        char c = query.charAt(0);

        if (c == '0'){
          stack.pop(); 
          return;
        }
        else stack.push(Character.getNumericValue(c)); return;
    }
}

 

 

 

 

 

9012 괄호

import java.io.*;
import java.util.Stack;

public class Main {

    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        for (int i=0;i<N;i++){
            if (solution(br.readLine())) sb.append("YES").append("\n");
            else sb.append("NO").append("\n");
        }

        br.close();

        System.out.println(sb);
    }

    static boolean solution(String str) {
        Stack<Integer> stack = new Stack<>();
        
        for (int i=0; i<str.length(); i++){
          if (str.charAt(i) == ')'){
            if (stack.isEmpty()) {
              return false;
            }
            else stack.pop();
          }
          else stack.push(1);
        }
        if (stack.isEmpty()) return true;
        else return false;
    }
}

이것도 응용. 괄호가 알맞지 않은 경우는 비어있는데 '('을 삽입하거나 검사를 끝냈는데 stack이 비어있지 않은 경우이다.

 

4949 균형잡힌 세상

import java.io.*;
import java.util.Stack;

public class Main {

    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true){
          Stack<Character> stack = new Stack<>();
          String str = br.readLine();
          if (str.equals(".")) break;

            for (int i=0; i<str.length(); i++){
              if (str.charAt(i) == '[' || str.charAt(i) == '(') stack.push(str.charAt(i)); 
              else if (str.charAt(i)==']') {
                if (!stack.isEmpty() && stack.peek() == '[') stack.pop();
                else {
                  stack.push(']');
                  break;
                  }
              }
              else if (str.charAt(i)==')'){
                if (!stack.isEmpty() && stack.peek() == '(') stack.pop();
                else {
                  stack.push(')');
                  break;
                }
              }
            } 
          if (stack.isEmpty()) System.out.println("yes");
          else System.out.println("no");
          }
        
    }

}

어려운건 아닌데 코드가 복잡해서 헷갈린다.

나도 괄호의 늪에 빠졌다...

 

12789 도키도키 간식드리미

이 문제... 옛날에 python으로 풀때는 아무도 반례를 알려주지않아서 못풀었다.

지금은 그래도 꽤 반례가 나와 풀 수 있었다.

순서가 맞으면 간식을 받으러 가고, 맞지 않으면 대기열(stack)에 들어간다.

이때, 순서가 맞는지 확인할 때마다 대기열에서 대기하고 있는 수도 순서가 맞는지 계속해서 확인해줘야 한다!!

이걸 잘 알려주는 반례가

2
2 1 3

이거였다!

예제가 이러한 부분을 잘 보여주면 좋았을텐데

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      int n = Integer.parseInt(br.readLine());
      Stack<Integer> stack = new Stack<>();
      int cnt = 1;
      StringTokenizer st = new StringTokenizer(br.readLine());
      for (int i=0; i<n;i++){
        int a = Integer.parseInt(st.nextToken());
        if (a==cnt){
          cnt++;
        }
        else {
          while (!stack.isEmpty() && stack.peek()==cnt){
            stack.pop();
            cnt++;
          }
          if (a==cnt) cnt++;
          else stack.push(a);
        }
      }
      while (!stack.isEmpty()){
        if (stack.pop() == cnt) cnt++;
      }

      if (cnt==(n+1)) System.out.println("Nice");
      else System.out.println("Sad");
        
    }

}

while(!stack.isEmpty()~~ 부분이 반례를 해결해주는 핵심이다.

 

18258 큐 2

양쪽에서 접근가능한 큐인 덱을 사용한다.

LinkedList를 사용하여 덱을 구현했다. ArrayList를 사용하면 시간초과가 난다.(탐색에 유리한 자료구조)

ArrayDeque를 사용하는 방법도 있더라.

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        Deque<Integer> q=new LinkedList<>();
        int n=Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while(n-- > 0){
            StringTokenizer st=new StringTokenizer(br.readLine());
            String str=st.nextToken();

            switch(str){
                case "push":
                    q.offer(Integer.parseInt(st.nextToken()));
                    break;

                case "pop":
                    if(q.isEmpty()) sb.append(-1).append("\n");
                    else sb.append(q.poll()).append("\n");
                    break;

                case "size":
                    sb.append(q.size()).append("\n");
                    break;

                case "empty":
                    if(q.isEmpty()) sb.append(1).append("\n");
                    else sb.append(0).append("\n");
                    break;

                case "front":
                    if(q.isEmpty())sb.append(-1).append("\n");
                    else sb.append(q.peek()).append("\n");
                    break;

                case "back":
                    if(q.isEmpty()) sb.append(-1).append("\n");
                    else sb.append(q.peekLast()).append("\n");
                    break;
            }
        }
        System.out.println(sb);
    }
}

 

2164 카드2

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
      BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
      Queue<Integer> q = new LinkedList<>();

      int N = Integer.parseInt(br.readLine());

      for(int i = 1; i <= N; i++) {
        q.offer(i);
      }


      while(q.size() > 1) {
        q.poll();	
        q.offer(q.poll());
      }

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

자바에서 제공하는 Queue 메소드를 사용하면 간단한 문제.

앞의 원소를 빼는 메소드 poll()과 삽입 메소드 offer(), 크기를 확인하는 size() 메소드를 사용했다.

 

11866 요세푸스 문제 0

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
      BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
      Queue<Integer> q = new LinkedList<>();
      Queue<Integer> q2 = new LinkedList<>();
      StringTokenizer st = new StringTokenizer(br.readLine());

      int n = Integer.parseInt(st.nextToken());
      int k = Integer.parseInt(st.nextToken());
      int cnt=1;

      for(int i = 1; i <= n; i++) {
        q.offer(i);
      }


      while(q.size() > 0) {
        if (cnt==k){
          q2.offer(q.poll());
          cnt=1;
        }
        else{
          q.offer(q.poll());
          cnt++;
        }
      }
     // System.out.println(q.size());
      
      StringBuilder sb = new StringBuilder();
      sb.append("<");
      while(true){
        if (q2.size()==1){
          sb.append(q2.poll().toString());
          break;
        }  
        sb.append((q2.poll()).toString()).append(", ");
      }
      sb.append(">");

      System.out.println(sb);	
    }
}

새로운 덱(q2)를 선언하고 q에서 poll()해준 요소들을 차례대로 저장했다.

출력이 복잡하다.

 

28279 덱 2

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        Deque<Integer> q=new LinkedList<>();
        int n=Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while(n-- > 0){
            StringTokenizer st=new StringTokenizer(br.readLine());
            String str=st.nextToken();

            switch(str){
                case "1":
                  q.push(Integer.parseInt(st.nextToken()));
                  break;  
                
                case "2":
                    q.offer(Integer.parseInt(st.nextToken()));
                    break;

                case "3":
                    if(q.isEmpty()) sb.append(-1).append("\n");
                    else sb.append(q.poll()).append("\n");
                    break;
                
                case "4":
                  if(q.isEmpty()) sb.append(-1).append("\n");
                  else sb.append(q.pollLast()).append("\n");
                  break;

                case "5":
                    sb.append(q.size()).append("\n");
                    break;

                case "6":
                    if(q.isEmpty()) sb.append(1).append("\n");
                    else sb.append(0).append("\n");
                    break;

                case "7":
                    if(q.isEmpty())sb.append(-1).append("\n");
                    else sb.append(q.peek()).append("\n");
                    break;

                case "8":
                    if(q.isEmpty()) sb.append(-1).append("\n");
                    else sb.append(q.peekLast()).append("\n");
                    break;
            }
        }
        System.out.println(sb);
    }
}

여기부터 새롭게 추가된 문제다.

기본적인 덱을 다루는 문제라 크게 어렵지는 않은 듯.

 

2346 풍선 터뜨리기

import java.io.*;
import java.util.*;

public class Main{

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());

    Deque<int[]> q = new ArrayDeque<>();
    StringTokenizer st = new StringTokenizer(br.readLine());

    int[] arr = new int[n];
    for(int i=0; i<n; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }

    StringBuilder sb = new StringBuilder();
    sb.append("1 ");
    int in = arr[0];

    for(int i=1; i<n; i++){
      q.add(new int[] {(i+1), arr[i]}); // {풍선 idx, 내용}
    }

    while(!q.isEmpty()) {
      // 양수인 경우 
      if(in >0) {
        // 순서 뒤로 돌리기 
        for(int i=1; i<in; i++) {
          q.add(q.poll());
        }

        int[] nxt = q.poll();
        in = nxt[1];
        sb.append(nxt[0]+" ");
      }
      // 음수인 경우 
      else {
        for(int i=1; i<-in; i++	) {
          q.addFirst(q.pollLast());
        }

        int[] nxt = q.pollLast();
        in = nxt[1];
        sb.append(nxt[0]+" ");
      }
    }

    System.out.println(sb.toString());

  }
}

양수면 덱을 앞으로 움직이고, 음수면 덱을 뒤로 움직인 후 poll()을 적용하는 것까지는 알겠는데

번호와 그 값을 어떻게 매치시킬까 고민했다.

검색해보니 Deque안에 배열을 넣어서 저장하는 방법이 있었다! (idx 번호(즉, 풍선 번호), 풍선값)으로 저장한다.

 

24511 queuestack

문제가 좀...난해하다... 해석을 여러개 읽고 겨우 이해했다.

  • 총 다섯 줄의 입력을 받는다.
  • 첫번째 줄은 자료구조의 개수 N이다. (4 -> 다음 줄에 4개 자료구조 종류 입력)
  • 두번째 줄은 N개 자료구조의 종류를 입력받는다. 0=큐, 스택=1이다. (0 1 1 0 -> 자료구조는 각각 큐 스택 스택 큐)
  • 세번째 줄은 N개 자료구조에 들어갈 값들이다. (1 2 3 4 -> 위 자료구조에 1 2 3 4를 각각 넣는다.)
  • 네번째 줄은 넣을 수의 개수 K이다. 넣을 수 하나당 자료구조를 한번씩 순환하므로 총 N*K번 반복하게 된다.(3)
  • 마지막 줄은 넣을 수의 값이다. K개 만큼 입력 받으며, 첫번째 자료구조부터 시작한다.(2 4 7)
    •  2부터 시작한다. 각 자료구조마자 삽입과 pop을 반복하며, pop된 값을 다음 자료구조에 넣는다.
    • 따라서 큐(0)인지 스택(1)인지에 따라 pop되는 값이 다르다는 것에 주목한다.
    • 예를 들어, 처음 자료구조(큐)에 있던 수는 1이다. 여기에 2를 삽입하고 pop을 수행하면 1이 나온다.
    • 이 1을 다음 자료구조(스택)에 넣고 pop하면 그대로 나오게 된다. 나온 수 1은 다음 자료구조(스택)에 전달.
    • 다음 자료구조(큐)는 1을 삽입하고 4을 pop()하게 된다.
    • 즉 값 2에 대한 반복을 끝낸 후 (0 1 1 0)에 들어있는 각 값은 (2 2 3 1)이 된다. 또한 return값, 즉 답의 첫번째 요소는 4가 된다.
    • 이것을 4, 7에 대해서도 반복한다!
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        // 1. 입력값 받아오기
        int N = Integer.parseInt(reader.readLine());

        int[] listQueuestack = new int[N];
        int[] currentList = new int[N];

        StringBuilder answer = new StringBuilder();
        // 1번 리스트 - 자료구조의 형태
        StringTokenizer input1 = new StringTokenizer(reader.readLine());
        for (int i = 0; i < N; i++) {
            listQueuestack[i] = Integer.parseInt(input1.nextToken());
        }
        // 2번 리스트 - 자료구조의 요소
        StringTokenizer input2 = new StringTokenizer(reader.readLine());
        for (int i = 0; i < N; i++) {
            currentList[i] = Integer.parseInt(input2.nextToken());
        }

        int M = Integer.parseInt(reader.readLine());
        int[] insertList = new int[M];
        // 3번 리스트 - 입력값 리스트
        StringTokenizer st3 = new StringTokenizer(reader.readLine());
        for (int i = 0; i < M; i++) {
            insertList[i] = Integer.parseInt(st3.nextToken());
        }
        // 큐 생성
        Deque<Integer> queue = new ArrayDeque<>();
        // 자료구조의 형태가 큐라면,
        for (int i = 0; i < N; i++) {
            if (listQueuestack[i] == 0) {
                queue.addFirst(currentList[i]); // 새로 만든 큐에 현재 요소를 담는다.
            }
        }
        for (int i = 0; i < M; i++) {
            queue.add(insertList[i]);
            answer.append((queue.pollFirst() + " "));
        }

        System.out.println(answer);
        reader.close();
    }
}

문제를 해석하는 것도 어려워서 풀이는 해석을 봤다.

막상 보니까 크게 어렵지 않은 것 같다.

결국 스택일때는 아무일도 일어나지 않으므로 큐에 주목하고, 큐인 경우 기존 요소를 갱신하고 뽑아내는 것이다.

 

# 회고

 

마지막 문제가 크리티컬이였다...

이제 진짜 파이썬으로 돌아가야지ㅜ

'코딩테스트' 카테고리의 다른 글

[Python] 우선순위 큐  (0) 2024.02.17
[Python] 그리디  (0) 2024.02.17
[JAVA] 약수, 배수와 소수 2  (1) 2024.02.04
[JAVA] 집합과 맵  (2) 2024.02.01
[JAVA] 정렬  (0) 2024.01.30

'코딩테스트' Related Articles

티스토리툴바