프로그래머스 LV.0 수열과 구간 쿼리 2

프로그래머스 LV.0 수열과 구간 쿼리 2

https://school.programmers.co.kr/learn/courses/30/lessons/181923

프로그래머스

 

1. 문제 명

수열과 구간 쿼리 2

2. 문제 설명

정수 배열 arr와 2차원 정수 배열 queries이 주어집니다. queries의 원소는 각각 하나의 query를 나타내며, [s, e, k] 꼴입니다.

각 query마다 순서대로 s ≤ i ≤ e인 모든 i에 대해 k보다 크면서 가장 작은 arr[i]를 찾습니다.

각 쿼리의 순서에 맞게 답을 저장한 배열을 반환하는 solution 함수를 완성해 주세요.

단, 특정 쿼리의 답이 존재하지 않으면 -1을 저장합니다.

3. 제한 사항

- 1 ≤ arr의 길이 ≤ 1,000

- 0 ≤ arr의 원소 ≤ 1,000,000

- 1 ≤ queries의 길이 ≤ 1,000

- 0 ≤ s ≤ e < arr의 길이

- 0 ≤ k ≤ 1,000,000

4. 예시

arr	queries	result
[0, 1, 2, 4, 3]	[[0, 4, 2],[0, 3, 2],[0, 2, 2]]	[3, 4, -1]

5. 기본 제공 코드

function solution(arr, queries) {
    var answer = [];
    return answer;
}

6. 제출한 내 답

const solution = (arr, queries) => {
  return queries.map((v) => {
    let tmp = arr.reduce((a, b, idx) => {
      return idx >= v[0] && idx <= v[1] && b > v[2] ? [...a, b] : a;
    }, []);
    return tmp.length === 0 ? -1 : Math.min(...tmp);
  });
};

 

6-2. VSC에 작성한 내용

const solution = (arr, queries) => {
  // queries의 요소는 query이며,
  // 이 query의 요소를 각각 s, e, k라고 한다.
  // query마다 순서대로 s <= i <= e인 모든 i에 대해
  // k보다 크면서 가장 작은 arr[i]를 찾아라

  // 단, 특정 쿼리의 답이 존재하지 않으면 -1을 저장한다

  return queries.map((v) => {
    let tmp = arr.reduce((a, b, idx) => {
      // idx가 v[0] 이상, v[1] 이하이며, v[2]보다 커야한다.
      return idx >= v[0] && idx <= v[1] && b > v[2] ? [...a, b] : a;
    }, []);
    // 요소가 없는 배열이라면 -1을 반환한다.
    return tmp.length === 0 ? -1 : Math.min(...tmp);
  });
};

// 테스트
console.log(
  solution(
    [0, 1, 2, 4, 3],
    [
      [0, 4, 2], // 0, 1, 2, 4, 3이며 2보다 크면서 가장 작은 수는 3
      [0, 3, 2], // 0, 1, 2, 4이며 2보다 크면서 가장 작은 수는 4
      [0, 2, 2], // 0, 1, 2이며 2보다 크면서 가장 작은 수는 없으므로 -1을 반환
    ]
  )
);

7. 특이사항

연산이 너무 오래걸린다

레벨 2처럼 효율성 검사까지 했으면 실패했을것 같다

테스트 1 〉	통과 (43.12ms, 39MB)
테스트 2 〉	통과 (21.27ms, 36.8MB)
테스트 3 〉	통과 (3.52ms, 36.7MB)
테스트 4 〉	통과 (0.83ms, 33.9MB)
테스트 5 〉	통과 (1.35ms, 34.3MB)
테스트 6 〉	통과 (0.62ms, 34.2MB)
테스트 7 〉	통과 (18.00ms, 37MB)
테스트 8 〉	통과 (27.41ms, 36.9MB)
테스트 9 〉	통과 (14.53ms, 36.8MB)
테스트 10 〉	통과 (41.36ms, 38.9MB)
테스트 11 〉	통과 (21.33ms, 36.9MB)

8. 다른 사람이 작성한 답

8-1. 좋아요를 가장 많이 받은 풀이법

function solution(arr, queries) {
    return queries.map(([s, e, k]) => arr.slice(s, e + 1).filter((n) => n > k).sort((a, b) => a - b)[0] || -1);
}