프로그래머스) 명예의 전당 (1) 문제 풀이 (JavaScript)

 > 휴일간에 프로그래머스 사이트에서 명예의 전당 (1) 문제를 풀면서 발생한 일과 깨달은 점을 기록해봤습니다.

 

학습 키워드: javascript, js, array, out of bounds, code kata

 

프로그래머스 - 명예의 전당 (1)

1) 문제 설명 (자세한 설명은 하단의 문제 링크 참고):

 - 어떤 TV 프로그램에서 매일 1명의 가수가 노래를 부르면 시청자들이 점수를 매기고 이 점수를 k 만큼의 등수가 있는 명예의 전당에 등록합니다. 출연한 가수들의 점수가 방영 일자별로 순서대로 담긴 배열 score 를 통해 매 방영일의 명예의 전당 최소 점수를 담은 배열을 반환하는 함수를 작성하는 문제입니다.

 - 조건: 3 <= k <= 100, 7 <= score.length <= 1000, 0 <= score[i] <= 2000

 

 

2) 작성한 스크립트:

function solution(k, score) {
    const hof = new Array(2001).fill(0);
    const ret = new Array(score.length);
    let min = score[0];
    hof[score[0]]++;
    ret[0] = min;
    for (let i = 1; i < Math.min(k, score.length); i++) { // #1
        hof[score[i]]++;
        if (score[i] < min) min = score[i];
        ret[i] = min;
    }
    
    for (let i = k; i < score.length; i++) { // #2
        if (score[i] > min) {
            hof[score[i]]++;
            if (hof[min]-- <= 1) {
                for (let j = min + 1; j < hof.length; j++) {
                    if (hof[min = j] > 0) break;
                }
            }
        }
        ret[i] = min;
    }
    return ret;
}

 

3) 풀이:

 - push, shift 등의 배열 조작 method를 사용하지 않는 방식으로 작성했습니다.

 - 먼저, 명예의 전당에 들어간 점수의 수를 세어 보관할 배열 hof를 최대 점수 2000점 + 1 만큼의 크기로 생성하고 0 값을 채워줍니다. 이렇게 하면 매 점수마다의 전당 등수 sorting 과정을 생략할 수 있어 동작 시간을 크게 단축할 수 있습니다.

 - 반환할 배열 ret은 매 방영일의 전당 최소 점수를 담아야하므로 score 배열과 같은 길이로 생성합니다.

 - 최소 값을 기억할 변수 min을 생성하고 score 배열의 첫 번째 항목을 미리 할당합니다. 전당의 count 또한 늘려주고, 첫 째 날의 점수가 그날의 유일한 점수이므로 반환할 배열의 0번째 index에도 똑같이 해당 값을 할당해줍니다.

const hof = new Array(2001).fill(0);
const ret = new Array(score.length);
let min = score[0];
hof[score[0]]++;
ret[0] = min;

 - 명예의 전당에 점수가 기록되는 작업은 크게 두 개의 작업 파트로 나눌 수 있습니다. 첫 째는 전당의 등수가 아직 가득차지 않은 상태의 작업(loop #1)이고, 둘 째는 가득 찬 이후의 작업(loop #2)입니다.

 - 첫 번째 for loop는 index 1부터 시작해서 전당의 등수가 가득 차는 k일 까지의 새로운 점수를 현재 min 점수와 비교해 최소 점수를 갱신한 뒤 hof에서 점수 카운트를 늘리고 ret 배열에 그 날의 최소 점수를 담아줍니다. 주의할 점은 k가 score 배열의 길이보다 큰 값일 때 입니다. 조건에 Math.min을 사용하여 해당 케이스를 걸러줍니다.

for (let i = 1; i < Math.min(k, score.length); i++) { // #1
    hof[score[i]]++;
    if (score[i] < min) min = score[i];
    ret[i] = min;
}

 - 두 번째 for loop는 전당이 가득 찬 시점의 index인 k일 부터 마지막 방영일인 score.length - 1일 까지의 루프입니다.

 - 전당의 점수 갱신은 최소 값인 min 보다 높은 점수가 들어왔을 경우에만 이루어집니다. 갱신이 이루어질 때 마다 전당의 점수를 count한 배열 hof에 해당 점수 index의 값을 올려줍니다. min 값 보다 낮거나 같은 점수는 전당에 아무런 영향을 주지 않으므로 ret 배열에 최소 값만 기록하고 넘어갑니다.

 - 만약 위의 조건을 만족하여 점수가 갱신되는 경우, 전당의 마지막 등수의 점수가 차트를 이탈하게 되므로 다음 차례의 최소 점수를 찾아야합니다. 하지만 이탈한 최소 점수와 동일한 점수가 아직 전당에 남아있다면 min 값의 변동이 없어야합니다. 따라서 min값의 중복 여부를 hof 배열의 점수 index에 세어둔 count 값을 이용하여 확인합니다.

 - 최소 점수의 중복이 없을 경우, 다음 최소 점수를 찾기 위해 hof 배열을 min+1 index부터 시작하여 살피면서 최초로 1 이상의 count를 담고 있는 index를 min 값에 할당하여 최소 점수를 갱신해주고 break로 반복문을 이탈합니다.

 - 최소 점수의 중복이 있을 경우, 중복 값 하나가 전당에서 이탈했다는 의미로 hof 배열의 min index에 해당하는 값만 -- 처리한 채 넘어갑니다.

 - Loop #2의 매 iteration의 끝에서 ret 배열에 그 날의 최소 점수를 추가해줍니다.

for (let i = k; i < score.length; i++) { // #2
    if (score[i] > min) {
        hof[score[i]]++;
        if (hof[min]-- <= 1) {
            for (let j = min + 1; j < hof.length; j++) {
                if (hof[min = j] > 0) break;
            }
        }
    }
    ret[i] = min;
}

 - Loop #2가 완전히 끝나면 함수에서 배열 ret을 반환해줍니다.

return ret;

 

 

4) 결과:

 - 성능 요약: 메모리: 33.5 MB, 시간: 0.09 ms

 - 채점 결과: 정확성: 100.0, 합계: 100.0 / 100.0

 

5) 막혔던 부분:

 - 풀이에 적어둔 '주의할 점' 부분인데, 처음에 작성했던 스크립트는 loop #1의 조건이 i < k였다. 그런데 문제 조건을 읽다가 k >= score.length가 되는 케이스를 떠올리고 loop #1 안 쪽에 if문을 적었지만, 마지막 줄의 ret[i] = min 부분만 if 구문 밖에 두는 실수를 했다. 당연하게도 이렇게 하면 if문을 작성한 이유가 없어지는데, 문제는 여기서 에러가 출력되지 않아서 내가 눈치를 채지 못하고 넘어갔다는게 원인이었다. '조건 작성을 대충한건가? 이 케이스는 고려 안해도 되나보네?' 따위의 생각을 하고 기억에서 지워버렸던 것 같다. 나중에 k 가 score.length보다 큰 경우의 테스트 케이스를 추가하고 보니 i가 배열의 index를 초과했을 때 javascript에서는 에러 대신 배열의 크기를 마음대로 늘려서 값을 할당해버린다는 사실을 알았다. Out of bounds 같은 에러만 출력됐어도 순식간에 해결했을텐데 내 실수와 JS의 특징의 콜라보로 전혀 눈치채지 못하고 원인을 다른데서 찾느라 한참을 헤맸다.

 

요약: JS의 Array는 크기를 미리 지정한다고 해서 배열의 크기를 제한하지 않는다. Index가 초과되면 Out of Bounds를 출력하지 않고, 대신 새로운 index를 push한다.

 

 

--

 

REFERENCES:

 

프로그래머스

 > 프로그래머스, 명예의 전당 (1) 문제 링크