[baekjoon] 카드2(JavaScript)

📘 오늘의 코딩테스트 - 카드2(JavaScript)

🔢 문제 번호: 2164번

🔗 문제 링크: 백준 - 카드2

 

 

 

 

🧠 문제 요약

• • N장의 카드가 1부터 N까지 순서대로 쌓여있을 때,
  • 다음 동작을 카드가 1장 남을 때까지 반복한다
    1. 맨 위의 카드를 바닥에 버린다
    2. 그 다음 맨 위의 카드를 제일 아래로 옮긴다
  • 입력: N (1 ≤ N ≤ 500,000)
  • 출력: 마지막에 남는 카드의 번호

 

 

 

✅ 실행 예시 및 결과

입력: 6
출력: 4

 

 

 

✍️ 내 풀이

• 인덱스를 확용하여 실제 요소를 제거하지 않고 "가상 제거" 방식 사용
• start 변수로 현재 맨 앞 위치를 추적한다

 

 

 

💻 내가 푼 코드

const N = parseInt(require('fs').readFileSync('/dev/stdin').toString().trim());

const cards = [];
for(let i = 1; i <= N; i++) {
    cards.push(i)
}

let start= 0;
while(cards.length - start > 1) {
    start++;
    
    cards.push(cards[start])
    start++
}

console.log(cards[start])

 

 

 

📎 남이 푼 코드

const N = parseInt(require('fs').readFileSync(0, 'utf8').trim(), 10);

// 원형 버퍼 기반 덱 배열 (길이는 N 고정)
const deque = Array.from({ length: N }, (_, i) => i + 1);

let front = 0;      // 현재 맨 앞 인덱스
let rear = N - 1;   // 현재 맨 뒤 인덱스
let size = N;       // 남아 있는 카드 수

while (size > 1) {
  // 1) 맨 앞 카드 버리기
  front = (front + 1) % N;
  size--;
  if (size > 1) {
  
    // 2) 새로운 맨 앞 카드를 맨 뒤로 보내기
    rear = (rear + 1) % N;
    deque[rear] = deque[front];   // 맨 앞 값을 맨 뒤에 넣음
    front = (front + 1) % N;      // 앞에서 제거 처리
    // size는 그대로 유지 (재배치니까 카드 수는 줄지 않음)
  }
}

console.log(deque[front]);

• 덱(Deque) 자료구조를 원형 버퍼로 구현
• 배열 크기를 고정하고 앞/뒤 위치만 추적하는 방식
• front와 rear로 현재 앞뒤 위치를 가리킴
• % 연산으로 배열 끝에서 처음으로 돌아가는 원형 구조
• 실제 카드를 복사해서 뒤로 보내는 방식
• 배열이 커지지 않아서 메모리 효율 굳

 

 

 

🔍 회고 & 배운 점

• 처음에는 shift()와 push()로 구현하면 되겠다 했는데 시간초과로 연속된 실패;;;;;;
• 숫자가 작으면 괜찮은데 만 단위로 올라가면 shift()가 시간복잡도가 O(N)으로 실패....
• 인덱스로 접근해서 풀이 성공!!
• 덱 자료구조 방식 풀이는 처음 봤는데.... 공부하자 ㅋㅋ