[백준/Java] 도키도키 간식드리미 12789

 

 

 

문제 

https://www.acmicpc.net/problem/12789

12789번: 도키도키 간식드리미

 

 

 

 

귀여운 간식 문제

과연 승환이는 간식을 먹을 수 있을까...?

 

 

 

 

 

 

 

 

풀이

1. stack 2개로 풀기 

스택 2개로 풀었는데 큐 하나 스택 하나로도 풀어도 될 것 같다. 

거꾸로 스택에 넣었는데, 알고보니 큐를 사용하면 똑바로 삽입하고 추출할 수 있었다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static int peekStack(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return -1;
        } else {
            return stack.peek();
        }
    }

    public static void popStack(Stack<Integer> stack) {
        if (!stack.isEmpty()) {
            stack.pop();
        }
    }

    public static void pushStack(int x, Stack<Integer> stack) {
        stack.push(x);
    }

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

        int num = Integer.parseInt(br.readLine());
        int start = 1;
        int[] arr = new int[num];

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

        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();

        for (int i = arr.length - 1; i >= 0; i--) {
            stack1.add(arr[i]);
        }

        while (!stack1.isEmpty()) {
            if (peekStack(stack1) == start) {
                popStack(stack1);
                start++;
            } else if (peekStack(stack2) == start) {
                popStack(stack2);
                start++;
            } else {
                int peekNum = peekStack(stack1);
                popStack(stack1);
                if (peekNum != -1) {
                    pushStack(peekNum, stack2);
                }
            }
        }

        int length = stack2.size();
        for (int i = 0; i < length; i++) {
            if (stack2.peek() == start) {
                popStack(stack2);
                start++;
            }
        }

        if (stack1.isEmpty() && stack2.isEmpty()) {
            bw.write("Nice");
        } else {
            bw.write("Sad");
        }

        bw.flush();
        bw.close();
    }
}

 

 

 

 

 

 

 

 

2. queue랑 stack으로 풀기 

package algorithm;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Algorithm {
    public static int peekStack(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return -1;
        } else {
            return stack.peek();
        }
    }

    public static void popStack(Stack<Integer> stack) {
        if (!stack.isEmpty()) {
            stack.pop();
        }
    }

    public static void pushStack(int x, Stack<Integer> stack) {
        stack.push(x);
    }
    
    public static int peekQueue(Queue<Integer> queue) {
        if(queue.isEmpty()) {
            return -1;
        } else {
            return queue.peek();
        }
    }
    
    public static void popQueue(Queue<Integer> queue) {
        if(!queue.isEmpty()) {
            queue.poll();
        }
    }

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

        int num = Integer.parseInt(br.readLine());
        int start = 1;
        int[] arr = new int[num];
        Queue<Integer> queue = new LinkedList<>();
        Stack<Integer> stack2 = new Stack<>();
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < num; i++) {
            queue.add(Integer.parseInt(st.nextToken()));
        }
      

        while (!queue.isEmpty()) {
            if (peekQueue(queue) == start) {
                popQueue(queue);
                start++;
            } else if (peekStack(stack2) == start) {
                popStack(stack2);
                start++;
            } else {
                int peekNum = peekQueue(queue);
                popQueue(queue);
                if (peekNum != -1) {
                    pushStack(peekNum, stack2);
                }
            }
        }

        int length = stack2.size();
        for (int i = 0; i < length; i++) {
            if (stack2.peek() == start) {
                popStack(stack2);
                start++;
            }
        }

        if (queue.isEmpty() && stack2.isEmpty()) {
            bw.write("Nice");
        } else {
            bw.write("Sad");
        }

        bw.flush();
        bw.close();
    }
}

 

 

 

 

 

 

 

정답

1. queue랑 stack이랑 풀기

2. stack 2개로 풀기