문제

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

1차 풀이 - 시간초과

function run(input) {
  const result = Array.from({ length: Number(input) }, (_, i) => i + 1);
  let isDiscard = false;

  while (result.length > 1) {
    const pick = result.shift();
    if (!pick) break;

    if (isDiscard) {
      result.push(pick);
      isDiscard = false;
    } else isDiscard = true;
  }

  return result[0];
}

• while문 안에서 shift()로 인해 매번 배열의 요소들이 이동 → O(n)^2

개선

function run(input: number) {
  const result = Array.from({ length: Number(input) }, (_, i) => i + 1);
  let front = 0;

  while (result.length - front > 1) {
    front++;

    result.push(result[front]);
    front++;
  }

  return result[front];
}

• front라는 포인터를 두어 이동시켜 인덱스에 접근 O(1)
• 실제로 배열을 수정하지 않고 포인터만 이동시키기 때문에 O(1)이다