2018-11-17
[JS] Binary Gap
EASY

개요

작은 개구리가 강을 건너려 합니다. 작은 개구리는 강의 시작점에 있습니다(position 0). 건너려는 위치는 강 건너편입니다(position X+1). 나뭇잎이 강 표면에 떨어집니다.

N개의 정수로 채워진 배열 A가 주어집니다. A[K]는 K초 후에 나뭇잎이 떨어질 좌표를 의미합니다.

목표는 개구리가 강을 가장 빠르게 건널 수 있는 시간을 찾는 것입니다. 개구리는 한 번에 1칸 움직일 수 있습니다. (다시 말하면, 1부터 K까지 나뭇잎이 모두 놓여야 건널 수 있다는 뜻입니다.) 강은 흐름이 거의 없어서 놓여진 나뭇잎이 떠내려가지 않고 고정되어 있습니다.

예시

X = 5
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4

6초가 지났을 때, 개구리는 X(5)까지 갈 수 있습니다.

문제

개구리가 반대편에 가기 위해 필요한 최소한의 시간을 반환하주세요. 만약 반대편으로 건너갈 수 없다면 -1을 반환하세요.

제한

  • N, X는 1 ~ 100,000의 정수 범위를 갖습니다.
  • 배열 A의 모든 요소는 1 ~ X의 정수 범위를 갖습니다.

풀이

스코어 100%

function solution(X, A) {
  const N = A.length
  let road = []
  let count = 0
  
  for (let i =0; i < X; i++) {
    road[i] = false
  }
  
  for (let i = 0; i < N; i++) {
    if (road[A[i]-1] === false) {
      road[A[i]-1] = true
      count++
    }
    if (count === X) {
      return i
    }
  }
  return -1
}

설명

1부터 X까지의 값이 모두 모였을 때의 index를 찾는 문제입니다. 나뭇잎이 경로에 최소 한 번 씩 떨어져 있어야 하는 점에 주목하세요.

  1. 먼저 길이가 X인 경로 배열을 만듭니다:
for (let i =0; i < X; i++) {
  road[i] = false
}
  1. 나뭇잎이 처음 떨어졌다면 표시하고, 숫자를 셉니다
if (road[A[i]-1] === false) {
  road[A[i]-1] = true
  count++
}
  1. 경로에 처음 떨어진 나뭇잎이 X개라면 건널 수 있습니다.
if (count === X) {
  return i
}