이 문제는 알고리즘 종류에서 알 수 있듯 큐를 쓰기 위한 문제 같았다. 그러나.. 저는 스포하자면 큐를 쓰진 않았습니다.
나의 코드
package source_code;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
// 1. 제일 위의 카드 버리기
// 2. 그 다음 위에 있는 카드를 제일 아래로 옮김
// 입력: N (마지막 카드 숫자)
// 출력: 가장 마지막에 남는 카드 숫자
// 1. 입력 받기
// 1-1. 카드를 순서대로 list에 저장
// 2. 규칙에 따라서 한 개의 카드가 남을 때까지 게임 play
// 3. list의 개수가 하나가 되면 멈추고 출력
public class B_S4_2164_Card2 {
public static void main(String[] args) {
// 1. 입력 받기
Scanner sc = new Scanner(System.in);
int lastNumber = sc.nextInt();
// 1-1. 카드를 순서대로 list에 저장
List<Integer> cards = new LinkedList<>();
for (int i = 0; i < lastNumber; i++) {
cards.add(i + 1);
}
// 2. 규칙에 따라서 한 개의 카드가 남을 때까지 게임 play
int lastCard = checkCardsCnt(cards);
// 3. list의 개수가 하나가 되면 멈추고 출력
System.out.println(lastCard);
}
private static int checkCardsCnt(List<Integer> cards) {
while (cards.size() > 1) {
playGame(cards);
}
return cards.get(0);
}
private static void playGame(List<Integer> cards) {
// 1번 규칙
cards.remove(0);
// 2번 규칙
int x = cards.get(0);
cards.remove(0);
cards.add(x);
}
}
우선 나는 큐를 생각하지 못하고 List를 사용하였다.
처음에는 습관처럼 ArrayList를 썼고, 시간초과로 실패하였다. 코드상에는 문제가 없는 것 같아서 자료구조를 바꾸기 위해 ArrayList 대신 LinkedList로 바꿨더니 통과 되었다.
✍🏻 ArrayList에서 시간초과가 난다면 LinkedList로 바꾸기 메모..
이쯤에서 시간복잡도의 개념에서 ArrayList, LinkedList, Queue를 비교해보았다.
ArrayList vs LinkedList vs Queue
| 연산 종류 | ArrayList | LinkedList | Queue (LinkedList 기반) |
|---|---|---|---|
addLast() | O(1) | O(1) | O(1) |
add(index) | O(n) | O(n) (탐색) | ❌ |
remove(index) | O(n) | O(n) (탐색) | ❌ |
removeFirst() | O(n) | O(1) | poll() → O(1) |
get(index) | O(1) | O(n) | ❌ |
순회(for) | 빠름 (O(n)) | 느림 (O(n)) | 보통 사용 안함 |
| 메모리 사용량 | 낮음 | 높음 | 보통 (LinkedList 기반) |
우선 큐는 특정 인덱스를 활용한 삽입/삭제/조회가 불가능하다.
ㄴ 그런데 이 문제에서는 첫 인덱스와 last 인덱스만 건드리기 때문에 큐를 써도 됨!
이 문제에서 시간복잡도가 차이가 났던 이유는 첫 번째 인덱스 값을 remove 하면서 문제가 발생했던 것이다.
arrayList의 경우 뒤의 값들을 다 당겨와야하기 때문에 오래걸리는데, linkedList는 배열의 개념이 아니므로 더 빠르게 첫 인덱스 값을 삭제할 수 있다.
반면, 특정 인덱스 값을 가져오는 것은 arrayList가 더 빠르다 (배열 개념이기 때문!)
각 자료구조를 언제 써야할까?
🍭 ArrayList
✅ 인덱스로 접근이 자주 필요한 경우
✅ 중간 삽입/삭제가 거의 없는 경우
❌ remove(0) 처럼 앞에서 삭제가 반복되면 느림 (O(n))
🌊 LinkedList
✅ 앞/뒤 삽입/삭제가 많을 때
❌ 인덱스로 자주 접근하면 느림 (O(n))
🎯 Queue (LinkedList 기반)
✅ FIFO 구조가 필요할 때 (먼저 들어온 걸 먼저 뺄 때)
offer() → 맨 뒤 삽입 O(1)
poll() → 맨 앞 제거 O(1)
ㄴ 큐는 참고로 줄 서기 문제 / 카드 버리기 / BFS 등에서 자주 쓰인다!
| 상황 | 추천 자료구조 |
|---|---|
| 인덱스로 자주 접근해야 한다 | ArrayList |
| 앞뒤로 삽입/삭제가 많다 | LinkedList or Deque |
| 큐처럼 앞에서 빼고 뒤에 넣는 구조다 | Queue (LinkedList or ArrayDeque) |
| 스택처럼 동작해야 한다 | Stack (Deque가 더 추천됨) |
| 정렬 필요하다 | ArrayList + Collections.sort() |
리팩토링 코드
package source_code;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class B_S4_2164_Card2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= n; i++) {
queue.offer(i);
}
while (queue.size() > 1) {
queue.poll(); // 1. 맨 앞 카드 버림
int card = queue.poll(); // 2. 다음 카드 뒤로
queue.offer(card);
}
System.out.println(queue.poll()); // 마지막 카드 출력
}
}
