프로그래머스 체육복

프로그래머스 체육복 LV1

카테고리: 탐욕법(Greedy)

해당 문제링크: https://programmers.co.kr/learn/courses/30/lessons/42862

나의 해답:

function solution(n, lost, reserve) {
    let students = {};
 
    for(let reserved of lost) { // 추후 검색시 시간복잡도를 줄이기위해 객체에 체육복을 읽어버린 학생번호를 key로 할당
        if(!students[reserved]) {
            students[reserved] = "I have a extra suite"; 
        } 
    }

    for(let i = 0; i < reserve.length; i++) { // 체육복을 잃어버렸지만, 자신의 여분을 챙겨온 학생들을 위한 로직.
        if(students[reserve[i]]) {
            delete students[reserve[i]];
            reserve[i] = -1;
        }

        if(Object.keys(students).length === 0) return n; // 실행시간을 줄이기위한 리턴문
    }

    for(let j = 0; j < reserve.length; j++) {
        if(students[reserve[j] - 1]) {
            delete students[reserve[j] - 1];
            reserve[j] = -1;
        } else if(students[reserve[j] + 1]) {
            delete students[reserve[j] + 1];
            reserve[j] = -1;
        }

        if(Object.keys(students).length === 0) return n; // 실행시간을 줄이기위한 리턴문
    }

    return n - Object.keys(students).length;
}

이 로직의 목적

2중 for문은 최대한 자제하고, 되도록 O(N)의 복잡도를 가지도록 풀어보고 싶었다. 아니면 코드 실행시간을 최대한 줄여보고 싶었다. 그래서 조금은 길지만 for문을 위 아래로 여러번 나열해서 작성해 보았고, 객체를 이용하는 방식을 써보았다.

[다른 사람의 풀이보기]에서 유명한 답 테스트케이스 실행시간이 대략 5.0ms정도 인 것보다 실행시간이 생각보다 빨리나와서 기분이 좋다.
아마도 indexOf나 filter같은 메소드들을 쓰지 않아서 그런 것 같다.

아쉬운 점

1. 원래는 reverse배열에 splice를 써서 잃어버린 학생 번호와 비교하며 하나씩 없애나가는 방식으로 진행했는데, 오류가 나와서 알고보니, splice를 써서 그 다음 반복 때, index에 변화를 주어서 reverse.splice(j, 1)이런 로직이 제대로 작동을 안했었다.

아마 일찍 캐치했으면 더 빨리 풀 수 있었을 텐데(debugging의 중요성...!)

그래서 splice로 빼는 대신, -1 을 할당하여 비교에서 제외시키는 방식으로 했다.

2. 아무리 실행시간을 줄인다지만 로직이 좀 긴 것 같다. 실행시간은 짧으면서, 적게 쓸 수 있는 방식은 없을까?

배운 점

그리드 알고리즘은 일단 취할 수 있는 가장 좋은 경우를 취한다고는 알고 있었는데, 막상 풀어보니 테스트 케이스에 걸리는게 많았다. 알고보니, 경우의 수를 상상해야 한다는 것 다르게 말하면 가설을 세워야 한다고 할까? 내가 로직을 짰지만, "이 로직이, 이런 상황에서는 걸릴까? 저런 상황에서는 안걸릴까?"를 상상해보면서, 테스트도 해보고 비교해봐야 한다는 것을 알았다.