프로그래머스 | n번째로 삭제된 숫자 찾기

📌 문제

배열 arr에, 1부터 차례대로 숫자가 입력됩니다. 그런데, 이 중에서 어느 숫자들은 다시 삭제가 됩니다. 이때 n 번째로 삭제가 된 숫자를 구하세요.

입출력 예시
arr = {2, 4, 5, 7}
n = 3

첫 번째 삭제된 숫자는 1
두 번째 삭제된 숫자는 3
세 번째 삭제된 숫자는 6이므로 정답은 6입니다.

✨ 해결 방법

map 함수를 이용하여 검사하는 방법과, 배열을 직접 검사하는 방법 두 가지가 있습니다. map 함수를 이용할 경우 코드는 다소 복잡하지만 효율성이 좋고, 직접 검사하는 방법은 코드가 간단하고 직관적이지만 큰 배열에서는 성능 저하의 문제가 있을 수 있습니다.

💻 solution 1

function solution(arr, n) {
    let resultMap = new Map();
    let deletedNum = 1;

    for (let i = 1; i <= arr.length + n; i++) {
        if (!arr.includes(i)) {
            resultMap.set(deletedNum, i);
            deletedNum++;
        }
        if (deletedNum === n) {
            return resultMap.get(n);
        } 
    }
  
  return -1; // n번째 주문이 없는 경우 -1 반환
}

삭제된 숫자들만 모을 새로운 map을 선언합니다.
삭제된 번호의 인덱스인 deletedNum를 1로 설정합니다.
arr.length + n만큼 순회하면서 삭제된 숫자를 탐색합니다.

여기서 +n으로 설정한 이유는, arr 배열에 있는 숫자와, n 번째로 삭제된 숫자들을 모두 고려하여 여유를 두고 루프를 돌기 위해서입니다.

예를 들어, arr 가 [2, 4, 5, 7]이고 n이 3이라면, 다음과 같이 루프가 돌아갑니다:

i = 0: 0 확인 (없음)
i = 1: 1 확인 (없음)
i = 2: 2 확인 (이미 있음)
i = 3: 3 확인 (없음)
i = 4: 4 확인 (이미 있음)
i = 5: 5 확인 (이미 있음)
i = 6: 6 확인 (없음)
i = 7: 7 확인 (이미 있음)
i = 8: 8 확인 (없음)

이런 식으로 arr.length까지는 arr 배열의 숫자를 확인하고, 그 이후부터는 n번째로 삭제된 숫자를 찾기 위한 여유를 두기 위해 arr.length + n로 범위를 설정한 것입니다.
사실 +n부분의 경우 임의의 상수 +10 등으로 설정해도 좋습니다. 하지만 종종 배열의 크기가 크고 주어진 데이터에 따라 범위가 불확실할 때는 조금 더 안전하게 배열의 길이에 기반하여 범위를 설정하는 것이 좋습니다.

그 다음으로, arr에 i 번째 숫자가 없을 경우, 즉 삭제된 숫자일 경우 인덱스 값과 함께 해당 값을 resultMap에 넣고, 인덱스 값을 하나 증가시킵니다. i번째 숫자가 존재하는 숫자라면 그냥 넘어갑니다.

이렇게 반복하다가, 만약 삭제된 숫자의 인덱스가 n까지 도달한다면, resultMap에서 n번째 값을 가져와서 반환합니다.

💻 solution 2

function solution(arr, n) {
    let deletedNum = 0;

    for (let i = 1; i <= arr.length + n; i++) {
        if (!arr.includes(i)) {
            deletedNum++;
            if (deletedNum === n) {
                return i;
            }
        }
    }

    return -1; // n번째 주문이 없는 경우 -1 반환
}

배열을 따로 저장하지 않고 검사만 하는 방식입니다. 초기 인덱스 값을 0으로 우선 설정하고, 만약 삭제된 숫자인 경우에 1씩 증가시킵니다. 계속 증가시키기다가 만약 인덱스 값이 n가 같아지게 되면, 해당하는 숫자를 반환합니다.