2018-11-17
[JS] Frog River One
EASY

개요

integer N으로 구성된 배열 A가 주어집니다. 배열 A가 가지고 있지 않은 가장 작은 자연수를 구해주세요.

예시

  • A가 [1, 3, 6, 4, 1, 2]면, 5를 반환합니다.
  • A가 [1, 2, 3]이면, 4를 반환합니다.
  • A가 [-1, -3]이면, 1을 반환합니다.

문제

배열 A가 가지고 있지 않은 가장 작은 자연수를 반환하세요.

제한

  • N은 1 ~ 100,000 범위를 갖는 정수입니다.
  • 배열 A의 각 요소는 -1,000,000 ~ 1,000,000 범위를 갖는 정수입니다.

풀이

스코어 100%

function solution(A) {
  A = A.sort((a, b) => {
    return a-b
  })
  let answer = 1
  for (let i = 0; i < A.length; i++) {
    if (A[i] > 0 && A[i] === answer) {
      answer++
    }
  }

  return answer
}

설명

배열에 포함되어 있지 않은 가장 작은 자연수를 찾는 문제입니다. 자연수를 찾는 것이 목표이기 때문에 음수는 무시되는 점에 주목하세요.

  • 먼저 배열을 차근차근 세기 위하여 정렬합니다.
A = A.sort((a, b) => {
  return a-b
})
  • 음수로만 이루어진 배열의 경우 가장 작은 자연수는 항상 1입니다. 또, answer변수에는 가장 작은 자연수가 담깁니다.
let answer = 1
  • 만약 현재 index의 값이 양수면서, 현재까지 가장 작은 자연수와 같은 값이면 1을 더합니다.
if (A[i] > 0 && A[i] === answer) {
  answer++
}

이렇게 하면, 같은 값이 있을 때 마다 정답이 1씩 오르고, 비어있는 값을 만나면 정답은 멈춰있는 상태로 반복문이 진행됩니다.

비어있는 값을 찾았을 때 반복문을 즉시 종료하는 로직을 넣으면 어떨까 싶지만 시간복잡도에 미치는 영향은 미미합니다.