Kotlin] 프로그래머스 lv.1, 체육복

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

프로그래머스

 

* Greedy(탐욕 알고리즘)이란?

주어진 상황에서의 가장 최적의 해를 찾는 기법이다.

예를 들어, 내가 거스름돈 780원을 걸러줘야 하는 상황이다.

그렇다면 100원짜리 7개, 10원짜리 8개로 걸러줘도 되지만, 500원 1개, 100원 2개, 50원 1개, 10원 3개가 가장 동전을 적게 쓰는 방식으로 거슬러 줄 수 있다. 이렇게 최적의 값을 찾아가는 알고리즘이 탐욕 알고리즘이다.

물론 이 방법이 완벽한 최적의 해라곤 할 수 없지만 근사치에 접근할 수 있다.

 

 

이 문제를 그리디 알고리즘을 기반으로 본다.

가장 최적의 방식은 뭘까? 잃어버린 사람 중 여벌 체육복이 있는 사람을 먼저 제해버리고 남은 사람들끼리 매칭하되, 낮은 순서 -> 높은 순서로 올라가면서 작은 체육복을 우선적으로 빌려 입는 것이 제일 최선의 방식이다.

 

그래서 나온 코드는..

 

class Solution {
    fun solution(n: Int, lost: IntArray, reserve: IntArray): Int {
        var answer = n
        var borrow = 0

        lost.sort()
        reserve.sort()

        var arrayList = reserve.toMutableList()

        for(lostPeople in lost) {

			// 스스로 가져온 사람을 우선적으로 리스트에서 뺌.
            if(arrayList.contains(lostPeople)) {
                arrayList.remove(lostPeople)
                borrow += 1
                continue
            }
            
			// 작은 체육복 찾기
            if(arrayList.contains(lostPeople - 1)) {
                arrayList.remove(lostPeople - 1)
                borrow += 1
                continue
            }

			//큰 체육복 찾기
            if(arrayList.contains(lostPeople + 1)) {
                if (!lost.contains(lostPeople + 1)) {
                    arrayList.remove(lostPeople + 1)
                    borrow += 1
                }
                continue
            }
        }

        return answer - (lost.size - borrow)
    }
}

 

 

 

 

+) 시간이 욜라리 마음에 안 들어서 줄여보고자 리스트 변환을 없애고 쌩 배열만 사용해봤다.

class Solution {
    fun solution(n: Int, lost: IntArray, reserve: IntArray): Int {
        var answer = n
        var borrow = 0

        lost.sort()
        reserve.sort()

        for(lostPeople in lost) {

            if(reserve.contains(lostPeople)) {
                reserve[reserve.indexOf(lostPeople)] = -1
                borrow += 1
                continue
            }

            if(reserve.contains(lostPeople - 1)) {
                reserve[reserve.indexOf(lostPeople - 1)] = -1
                borrow += 1
                continue
            }

            if(reserve.contains(lostPeople + 1)) {
                if (!lost.contains(lostPeople + 1)) {
                    reserve[reserve.indexOf(lostPeople + 1)] = -1
                    borrow += 1
                }
                continue
            }
        }

        return answer - (lost.size - borrow)
    }
}

 

꽤 줄어든다. 컬렉션이 문제였나?...

라는 생각으로 세번째에 도전한다.

 

++)

이번엔 컬렉션을 이용해서 그냥 중복값을 빼버리는 알고리즘을 만들었다.

class Solution {
    fun solution(n: Int, lost: IntArray, reserve: IntArray) : Int {
        var answer = n

        lost.sort()
        reserve.sort()

        var reserveList = reserve.toMutableList()
        var lostList = lost.toMutableList()
        var borrowList = mutableListOf<Int>()

        reserveList.removeAll(lost.toList())
        lostList.removeAll(reserve.toList())

        for (lostPeople in lostList) {

            if (reserveList.contains(lostPeople)) {
                reserveList.remove(lostPeople)
                borrowList.add(lostPeople)
                continue
            }

            if (reserveList.contains(lostPeople - 1)) {
                reserveList.remove(lostPeople - 1)
                borrowList.add(lostPeople)
                continue
            }

            if (reserveList.contains(lostPeople + 1)) {
                reserveList.remove(lostPeople + 1)
                borrowList.add(lostPeople)
                continue
            }
        }

        lostList.removeAll(borrowList)

        return answer - lostList.size

    }
}

 

배열과 비교하면 어라? 일부 케이스에는 느리지만 일부 케이스에서는 빠른 결과가 나왔다.

아무래도 중복값을 삭제하고 삭제된 값을 더 이상 참조하지 않는 것이 큰 것 같다.

 

배열은 중복값 삭제 처리가 힘들어서 음(..)