보이는 학생 JavaScript 풀이

현재 학생이 보이는지는 바로 앞 학생 한 명만으로 판단할 수 없습니다. 현재 위치보다 앞에 있는 학생 중 가장 큰 키와 비교해야 합니다. 따라서 첫 학생의 키를 maxHeight로 두고, 뒤의 학생을 차례대로 확인합니다.

현재 키가 maxHeight보다 크면 앞의 모든 학생보다 큰 것이므로 보이는 학생 수를 늘립니다. 이때 현재 키를 새로운 최댓값으로 저장합니다. 키가 같으면 문제 조건의 ‘크면 보인다’를 만족하지 않으므로 세지 않습니다.

알고리즘 설계

1. 맨 앞 학생은 항상 보이므로 개수를 1로 시작합니다.
2. 맨 앞 학생의 키를 현재 최댓값으로 저장합니다.
3. 두 번째 학생부터 최댓값보다 큰지 비교합니다.
4. 더 크면 개수를 늘리고 최댓값을 현재 키로 갱신합니다.

예제에서는 130, 135, 148이 차례대로 최댓값을 바꿉니다. 140과 145는 148보다 작아 보이지 않습니다. 첫 번째 150은 새 최댓값이지만, 다음 150은 같기 때문에 제외되고 마지막 153이 선택됩니다.

JavaScript 풀이

const fs = require("fs");

const input = fs.readFileSync(0, "utf8").trim().split(/\s+/).map(Number);
const count = input[0];
const heights = input.slice(1, count + 1);

let visibleCount = 1;
let maxHeight = heights[0];

for (let index = 1; index < heights.length; index += 1) {
  if (heights[index] > maxHeight) {
    visibleCount += 1;
    maxHeight = heights[index];
  }
}

console.log(visibleCount);

split(/\s+/)은 공백과 줄바꿈을 함께 구분하므로 LF와 CRLF 입력을 모두 처리합니다. trim()은 입력 문자열의 앞뒤 공백과 줄바꿈을 제거합니다. 입력의 첫 수만 N으로 사용하고 이어지는 N개의 값을 학생 키로 읽습니다.

복잡도와 검증

학생 N명을 한 번씩 확인하므로 시간 복잡도는 O(N)입니다. 입력 배열은 O(N) 공간을 사용하지만, 최댓값과 개수 등 풀이 자체의 추가 공간은 O(1)입니다.

현재 값과 직전 값만 비교하는 문제와의 차이는 큰 수 출력하기 JavaScript 풀이에서 함께 비교해 보실 수 있습니다.