[백준] 2164번 카드2 - 큐(Queue)/선입선출/스택을 이용한 방법/

문제

 

 

로직

N 입력받기

num 변수 선언(반복문의 횟수 변화에 이용 예정)

 

스택1, 2선언

 

1. 반복문

- 스택에 1~N값 삽입

 

2. while 반복문 - stack에 값이 1개만 남을 때까지 횟수(stack.size()로 하면 안의 for반복문에서 걸림)

while반복문의 로직

위와 같은 로직으로

2개의 스택에서 pop(), push()하며 후입선출인 스택을 선입선출이 되도록 구현했다.

큐를 이용하면 더욱 효율적이었을 텐데 그 생각을 처음에 못했다.

 

마지막 남은 카드 값 출력

 

 

 My Code(스택 이용)

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

public class Main {
static int n;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
int num = 2;

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

for (int i = N; i >= 1; i--){
stack.push(i);
}
while(N-num >= 1){
stack.pop();
n = stack.pop();

for (int j = 0; j < N-num; j++){
stack2.push(stack.pop());
}
for (int j = 0; j < N-num; j++){
if(stack.empty()) stack.push(n);
stack.push(stack2.pop());
}
num++;
}
System.out.println(n);
}
}

 

 

 

문제의 핵심 및 알게된 점

이 문제는 큐를 어떻게 이용하나, 큐의 원리 이해가 핵심이었다.

맨 위의 카드를 버리고 그 다음 앞의 값을 맨 뒤로 넘기는 것은 선입선출과 연관이 있기 때문이다.

근데 나는 스택으로 푸는 사서 고생,,,

하지만 덕분에 큐로 하면 간단한 문제를 스택으로 하면 얼마나 비효율적이고 복잡한지 깨달았다.

용도에 맞는 자료구조 이용의 중요성을 크게 느꼈다.

왜냐하면 위의 로직을 세우려고 2시간 넘게 고민했기에 스택과 큐의 차이를 확실히 알 수 있게 됐다.

 

 

 

참고 Code(큐 이용)

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
static int n;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
Queue<Integer> cardQueue = new LinkedList<>();

for (int i = 1; i<=N; i++){
cardQueue.add(i);
}
while(cardQueue.size() > 1){
cardQueue.poll();
cardQueue.add(cardQueue.poll());
}
System.out.println(cardQueue.poll());
}
}

 

 

 

참고 강의_인프런의 Do it! 알고리즘 코딩테스트 with JAVA