[프로그래머스] 체육복

문제 설명

 

문제 분석

• 일부 학생들이 체육복을 도난당했습니다.
• 여벌 체육복이 있는 학생이 도난당한 학생에게 체육복을 빌려줄 수 있습니다.
• 학생들은 자신의 번호의 앞뒤 번호의 학생에게만 체육복을 빌려줄 수 있습니다.
• 최대한 많은 학생이 체육 수업을 들을 수 있도록 해야 합니다.

 

첫 번째 접근: reduce() O(n * m)

function solution(n, lost, reserve) {
    const duplication = lost.filter(el => reserve.includes(el))
    lost = lost.filter(el => !duplication.includes(el))
            .sort((a, b) => a - b)
            .map(el => [el - 1, el + 1])
    reserve = reserve.filter(el => !duplication.includes(el))
    
    return lost.reduce((a, [min, max]) => {
        let [idx1, idx2] = [reserve.indexOf(min), reserve.indexOf(max)]
        
        if(idx1 > -1 || idx2 > -1) {
            a += 1
            reserve.splice(idx1 > -1 ? idx1 : idx2, 1)
        }
        
        return a
    }, n - lost.length)
}

 

• 중복 제거: 여벌 체육복을 가져온 학생이 도난당한 경우를 먼저 처리합니다. 
• 정렬: 낮은 번호부터 처리하여 최적의 결과를 도출합니다.
• 앞뒤 번호 매핑: 각 학생의 앞뒤 번호를 배열로 변환합니다. 
• 체육복 분배: reduce를 사용하여 가능한 많은 학생에게 체육복 분배합니다.

 

 

 

개선된 해결책( O(n log n) )

function solution(n, lost, reserve) {
    // Set을 활용한 더 효율적인 중복 처리
    const lostSet = new Set(lost.sort((a, b) => a - b));
    const reserveSet = new Set(reserve);
    
    // 여벌 체육복이 있지만 도난당한 학생 처리
    const actualLost = new Set(
        [...lostSet].filter(student => !reserveSet.has(student))
    );
    const actualReserve = new Set(
        [...reserveSet].filter(student => !lostSet.has(student))
    );
    
    // 체육복 빌려주기
    for (const student of actualLost) {
        if (actualReserve.has(student - 1)) {
            actualReserve.delete(student - 1);
            actualLost.delete(student);
        } else if (actualReserve.has(student + 1)) {
            actualReserve.delete(student + 1);
            actualLost.delete(student);
        }
    }
    
    return n - actualLost.size;
}

개선 사항

1. Set 자료구조 활용
   • O(1) 시간 복잡도로 검색/삭제 가능
   • includes() 대신 has() 사용으로 성능 향상
   • 중복 제거가 자동으로 이루어짐
2. 메모리 효율성
   • filter와 splice 대신 Set 연산 사용
   • 불필요한 배열 복사 최소화
3. 코드 가독성
   • 더 명확한 변수명 사용
   • 로직 흐름이 직관적
4. 성능 최적화
   • indexOf 연산 제거
   • 불필요한 map 연산 제거

핵심 개선 포인트

1. 자료구조 선택: Array에서 Set으로 변경하여 검색 효율성 향상
2. 메모리 관리: 불필요한 배열 복사 및 변환 작업 제거
3. 알고리즘 단순화: 복잡한 reduce 연산을 직관적인 for...of 루프로 대체

 

* Set은 해시 테이블을 사용해 요소를 저장

• 요소의 위치를 해시함수로 개산해 즉시 접근 가능(Set.has v.s. Array.includes)
• incldes()는 선형 검색으로 O(n)의 시간복잡도를 가짐
• Set은 filter와 같은 반복 작업과 함께 사용될 때 Set의 성능 이점이 더욱 커짐