Kotlin/Algorithm Problems

<프로그래머스> 귤 고르기(Lv.2)

re트 2023. 11. 15. 16:26
728x90

https://github.com/heesoo-park/ForCodeKata/tree/main/%EA%B7%A4%20%EA%B3%A0%EB%A5%B4%EA%B8%B0

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

 

처음에 문제 이해하는데 시간이 좀 걸렸다.

점심을 먹고 얼마 안 돼서 그런건가...

여러번 차근차근 읽고 문제 풀이 진행 시작!

 

가장 먼저 막힌 순서는 '귤의 크기와 개수의 쌍을 어떻게 저장할 것인가?'였다.

 

 

그냥 배열로 하자니 천만개의 배열이니까 아무리 많이 써도 10퍼센트 밖에 안 쓰는데 너무 공간 낭비 같았고, 이후에 정렬할 때를 생각해봐도 좋지 않은 방법 같았다.

그 다음에 생각한건 Pair를 원소로 갖는 List였다.

'이거 괜찮은데...?' 라는 생각이 들었었지만 접근할 때가 좀 불편해서 고민하다가 최종적으로 선택한 자료구조는 Map이다.

Map을 이용해 귤의 크기와 개수의 쌍을 저장하면 접근도 편하고 이후 정렬에서도 좋겠다는 걸로 최종 결정했다.

(다 풀고 나서 알게된 걸로 내가 왜 이렇게 고민했나 싶긴 했지만 그건 나중에...)

 

그 다음 순서는 '귤의 크기를 어떻게 다룰 것인가?'였다.

 

 

그냥 반복문을 돌면서 저장하려다가 이렇게 하다가는 Map 내에서 해당 크기가 있는지 체크한다고 시간이 다 지나갈 거 같더라...

그래서 메서드를 좀 찾아봤는데 toSortedSet()이 있더라!

'원소를 유니크하게 가지고 정렬까지 해준다니...!! 아이 행복해~' 하면서 썼지만 지금 생각해보면 어짜피 뒤에서 정렬할거니까 그냥 toSet() 써도 됐을 거 같다.

그래도 여기까지 해결완료~

 

그리고 나서는 Map 변수에 집어넣고 Map의 value 값에 오름차순으로 정렬시켰다.

Map은 value 값을 기준으로 정렬할 때는 List로 변환시키고 다시 Map으로 변환시키는 과정이 필요하다고 해서 참 안타까웠다.

 

그 뒤는 그냥 반복문에서 덧셈, 뺄셈하면서 쉽게 작성하고 제출을 했는데... 실패가 97퍼센트..!?
이게 무슨 일인가 싶어서 케이스들을 좀 더 찾아봤는데 내가 짠 코드에서는 먼저 크기에 해당하는 모든 값을 없애고 시작해서 생기는 문제였다.

그래서 그 부분은 조건문을 추가하는 것으로 해결했다.

(* 실패한 코드는 깃허브에 추가되어있다.)

 

해당 방법으로 작성한 코드는 다음과 같다.

class Solution {
    fun solution(k: Int, tangerine: IntArray): Int {
        var group = mutableMapOf<Int, Int>()
        val itemSet = tangerine.toSortedSet()
        var answer: Int = itemSet.size

        for (item in itemSet) {
            group[item] = 0
        }
        for (item in tangerine) {
            group[item] = group[item]!!.plus(1)
        }

        val sortedGroup = group.toList().sortedBy { it.second }.toMap()
        var sub = 0
        for (i in sortedGroup) {
            sub += i.value
            answer--

            when {
                tangerine.size - sub == k -> {
                    break
                }
                tangerine.size - sub < k -> {
                    answer++
                    break
                }
                answer == 1 -> {
                    break
                }
            }
        }

        return answer
    }
}

(이 문제를 풀고 나서 다른 사람의 풀이를 보는데 groupBy()라는 함수가 있더라... 배열 내의 값을 key로 보고 값의 개수를 value로 봐서 묶어주는 아주 훌륭한 함수였다.)

(이 함수를 사용했다면 초반 10줄은 딱 1줄이 됐을텐데...)

반응형