프로그래머스 체육복 Kotlin 빠른 답안

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

프로그래머스

 

Edge 케이스 분석

1. 여벌 체육복이 있지만, 도난 당한 학생은 다른 학생에게 빌려줄 수 없다.

예를 들어 5, [3,4], [4,5]의 경우 3번 학생이 4번 학생으로부터 체육복을 빌릴 수 있으면 정답은 5명이다. 하지만 4번 학생은 여벌 체육복을 도난 당했기에 다른 학생에게 빌려줄 수 없다. 비록 5번 학생으로부터 빌릴 수 있더라도 말이다.

 

2. greedy시 정렬 여부 확인하기

greedy로 앞에 있는 학생, 뒤에 있는 학생 순으로 빌리도록 구현했는데, 이것은 lost가 정렬되어 있다는 전제하에 동작한다.

lost의 정렬 여부에 대한 조건이 없는데, 테스트 케이스 13, 14번이 정렬되어 있지 않은 예시 같다.

 

 

더 빠른 코드를 위한 팁

1. Map을 이용해서 학생의 체육복 여부 탐색을 O(1) 만에 가능하도록 만든다.

2. lost는 정렬되어 있지 않다. lost에서 여벌이 있는 학생을 제외한, 진짜 도난 당해서 없는 학생을 추린다. 이 과정에서 PriorityQueue를 사용하면 도난당한 학생을 순서대로 삽입할 수 있다. ArrayList나 IntArray에 넣고 sort 함수를 호출하는 것보다 훨씬 빠르다.

 

Kotlin 코드

import java.util.PriorityQueue

class Solution {
    fun solution(n: Int, lost: IntArray, reserve: IntArray): Int {
        val reserveMap = hashMapOf<Int, Int>()

        // 여벌이 있는 학생 map에 저장
        for (idx in reserve) {
            reserveMap[idx] = 1
        }

        // 도난 당했지만 여벌이 있는 학생 제외하기
        val realLostPerson = PriorityQueue<Int>(lost.size)
        for (num in lost) {
            if (reserveMap.remove(num) == null) {
                realLostPerson.add(num)
            }
        }

        var answer = n

        // 이전 번호 학생 -> 다음 번호 학생 순으로 여벌을 빌린다.
        for (studentIdx in realLostPerson) {
            if (studentIdx-1 in reserveMap) {
                reserveMap.remove(studentIdx-1)
                continue
            } else if (studentIdx+1 in reserveMap) {
                reserveMap.remove(studentIdx+1)
                continue
            }
            answer--
        }

        return answer
    }
}