[백준] 2164 : 카드2

🙋🏻‍♀️큐 이용!

문제분석

가장 위의 카드를 가장 아래에 있는 카드 밑으로 옮기는 동작은 큐의 선입선출 성질을 이용하면 구현할 수 있다.
(보통 큐를 표현하는 그림에서 가장 아래에서 값을 빼고, 가장 위에 값을 넣는 그림을 보기때문에 헷갈렸다. 하지만 그 그림을 뒤집어서 생각하면 된다!)

N의 최대가 500,000으로 작기때문에 시간 복잡도의 제약이 크지않다.

문제 푸는 순서

1. poll을 수행해 맨 앞 카드를 버린다.
2. poll -> add를 수행해 맨 앞의 카드를 가장 아래로 옮긴다
3. 큐의 크기가 1이 될 때까지 과정 1~2를 반복한다. 남은 원소 출력한다.

슈도코드

N입력받기
myQueue 선언 (카드 저장 자료구조)
for(카드 개수만큼 반복) {
	큐에 가드 저장 
}
while(1장 남을때까지){
	poll
    int frontIt = poll
    add(frontIt)
}
peek 출력 

제출코드

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

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		Queue<Integer> myQueue = new LinkedList<>();
		
		for(int i=1; i<=N; i++) {
			myQueue.add(i);
		}
		
		while(myQueue.size() > 1) {
			myQueue.poll();
			int frontNum = myQueue.poll();
			myQueue.add(frontNum);
		}
		System.out.println(myQueue.peek());

	}
}

수정하면 좋을 부분

while(myQueue.size() > 1) {
	myQueue.poll();
	int frontNum = myQueue.poll(); // 여기부터 
	myQueue.add(frontNum); // 이 부분까지 두 줄이 비효율적
}

위의 코드는 내가 작성한 코드이다.
두번째 poll()을 할 때 fronNum이라는 변수를 만들어 변수에 값을 넣어두는데, 이렇게 변수를 따로 생성하지않아도 poll을 한 값을 add할 수 있다.

while(myQueue.size() > 1) {
	myQueue.poll();
	myQueue.add(myQueue.poll()); //이렇게 수정
}

위 코드로 수정하면 된다.

공부한 사항

• 큐의 크기 = size()
• 큐 선언 = Queue<type 작성> 이름 = new LinkedList<>()
  -> 큐는 LinkedList로 구현!!