백준 - 카드2
구해야 하는 것
- 제일 위 카드를 버리고 그 다음 제일 위의 카드를 제일 아래로 옮기는 동작을 반복했을 때 마지막에 남게 되는 카드
주어진 자료
- 맨 위에서부터 1 ~ N 까지의 카드가 순서대로 놓여있음
- 동작은 다음과 같음
- 제일 위에 있는 카드를 버림
- 남은 카드 중 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮김
- 카드가 한 장 남을 때까지 반복
조건
- N은 1 이상 500,000 이하
계획
- 큐에 1 ~ N까지 넣는다.
- 동작을 반복한다.
- 큐의 크기가 1이 될 때까지 아래 과정을 반복한다.
- 큐의 첫번째 값을 삭제한다.
- 큐의 첫 번째 값을 꺼낸 후 삭제한다.
- 꺼낸 값을 큐에 추가한다.
- 큐의 첫 번째 값을 return 한다.
실행
public class Main {
// 동작
public void move(Queue<Integer> q) {
while(q.size() != 1) {
q.remove(); // 첫 번째 값 삭제
int first = q.poll(); // 첫 번째 값 꺼낸 후 삭제
q.offer(first); // 꺼낸 값을 큐에 추가
}
}
// 큐에 카드 넣기
public void addCard(Queue<Integer> q, int n) {
for(int i = 1; i <= n; i++) {
q.add(i);
}
}
public int solution(int n) {
// 1. 큐에 1 ~ N까지 넣는다.
Queue<Integer> q = new LinkedList<>();
addCard(q, n);
// 2. 동작을 반복한다.
move(q);
// 3. 큐의 첫 번째 값을 return 한다.
int answer = q.peek();
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int answer = new Main().solution(n);
System.out.println(answer);
}
}
반성
- Scanner를 사용해서 입력을 받도록 했는데, BufferedReader를 사용하는게 더 빠르다고 한다. 다음부터는 BufferedReader를 써보자