[자료구조] 백준 - 카드 2

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

2164번: 카드2

 

-문제해설

큐를 이용해서 쉽게 풀 수 있었다. 먼저 1부터 입력값인 n까지 큐에 삽입한다. 그러면 아래와 같이 큐에 쌓인다.

6

5

4

3

2

1

이제 조건이 큐 사이즈가 1 초과일 때만 실행되는 반복문 안에서

첫 번째 큐값을 뺀다. 그리고 두 번째 큐값을 빼고 tmp 변수에 저장한 뒤 큐에 tmp를 다시 삽입한다.

이를 반복하다가 큐 사이즈가 1이되면 반복문을 빠져나오고

큐 안에 하나남은 값을 출력하면 정답이다.

 

 

 

-자바

package queue;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class BJ2164 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt( br.readLine() );
		
		Queue<Integer> que = new LinkedList<Integer>();
		for( int i=1; i<=n; i++ ) que.add( i );
		
		int tmp = 0;
		while( que.size() > 1 ) {
			que.poll();
			tmp = que.poll();
			que.add( tmp );
		}
		System.out.println( que.poll() );
	}
}

 

-파이썬

import sys
from collections import deque

readline = sys.stdin.readline
n = int( readline() )
que = deque()

for i in range( 1, n+1 ):
    que.append( i )

tmp = 0
while len( que ) > 1:
    que.popleft()    
    tmp = que.popleft()
    que.append( tmp )
print( que.pop() )