2164번 문제 : 카드 2

2164번: 카드2 (acmicpc.net)

2164번: 카드2

 

1부터 N 까지의 카드 -> List로 생성

0번째를 버림 

버리고 나서 제일 위에 있는 거를 제일 끝으로 옮김

size()가 1일 때까지 반복 -> while문으로 

그때 남아있는 카드 번호 출력

 

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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());
		List <Integer> list = new ArrayList<>();
		
		for(int i =1;i<=N;i++) { //저장되는 카드번호는 1부터 N까지
			list.add(i);
		}
		while(list.size() != 1) {
			list.remove(0); //제일 위에 요소 없애고
			list.add(list.size(),list.get(0)); //그다음 젤 위에있는거 젤 뒤로 추가
			list.remove(0); //뒤로 추가한 거 제일 앞에서 없앰.
		}
		System.out.println(list.get(0));
	}	
}

엄청쉽다 했더니 시간초과가 나왔당 ..ㅋ

 

add메소드는 해당 index~끝까지의 배열을 arraycopy로 옮겨 자리를 확보하고 , 그 자리에 요소를 삽입하는 식으로 동작한다. 문제에서 input이 최대 50만이라 했으므로, 1개를 제거 - 49만~개를 복사 - 1개를 삽입 같은 작업이 반복해서 일어나게 되고, 시간초과가 발생.

 

큐를 써보았다 !

그래서 해결 !!

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;

public class Main{
	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 N = Integer.parseInt(br.readLine());
		LinkedList <Integer> q = new LinkedList<>();
		
		for(int i =1;i<=N;i++) { //저장되는 카드번호는 1부터 N까지
			q.add(i);
		}
		while(q.size() != 1) {
			q.poll(); //제일 위에 요소 없애고
			q.offer(q.poll()); //그다음 젤 위에있는거 없애고 바로 반환 받아서 젤 뒤로 추가
		}
		bw.write(Integer.toString(q.peek()));
		bw.flush();
		bw.close();
	}	
}

poll() 삭제(맨 앞에서) offer()추가(맨 뒤에)