본문 바로가기

Fundamentals/Algorithms

[해커랭크] Picking Numbers

문제링크

 

Picking Numbers | HackerRank

What's the largest size subset can you choose from an array such that the difference between any two integers is not bigger than 1?

www.hackerrank.com

주어진 정수 배열에서, 어떤 두 요소 간의 절대 차이가 1 이하인 가장 긴 부분 배열을 찾아야 합니다.

예를 들어, 두 부분 배열 [1, 1, 2, 2, 4, 4, 5, 5, 5]와 [4, 4, 5, 5, 5]가 있을 때, 최대 길이를 가진 부분 배열은 요소가 5개인 배열입니다.

 

풀이 :

function pickingNumbers(a) {
    let result = 0
    const frequency = new Array(100).fill(0)
    
    for(let item of a){
        frequency[item]++
    }
    
    for(let i=1; i<100; i++){
        result = Math.max(result, frequency[i]+frequency[i-1])
    }
    return result
}

 

우선, 처음 문제 해결을 위해 배열 요소를 오름차순으로 정렬하고 배열간의 절대값 차이가 1인 요소룰 찾아 새로운 배열로 분리하는 방안을 고려했으나 복잡하고 효율성도 낮아서 해결하기 어려웠으나 위 풀이에서는 배열의 요소를 100개 생성하여 0 값으로 초기화 한 후 각 배열의 빈도수를 계산하고 반복문으로 순회하면서 이전 요소와 현재 요소의 빈도수 합이 높은 걸 찾아 결과값으로 반환하여 해결합니다

'Fundamentals > Algorithms' 카테고리의 다른 글

[해커랭크] Forming a Magic Square  (0) 2023.12.12
[해커랭크] Cats and a Mouse  (0) 2023.12.06
[해커랭크] Electronics Shop  (0) 2023.12.06
[해커랭크] Counting Valleys  (0) 2023.12.06
[해커랭크] Sales by Match  (0) 2023.12.05