[코딩테스트] 가장 많이 받은 선물 (feat. kotlin)

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

프로그래머스

 

문제 파악

문제에서 친구목록[friends]이 주어지지고 각 친구끼리 선물을 주고 받은 내용이 선물목록[gifts] 로 주어진다.
선물목록[gifts]는 "A B"형태의 문자열이다. A는 선물을 준 친구의 이름을 B는 선물을 받은 친구의 이름을 의미하며 공백 하나로 구분된다.
 
주어진 친구목록과 선물목록을 기준으로 선물을 더준 친구에게 선물을 주어야 한다.
만약 두 사람이 선물을 주고받은적이 없거나 주고받은 수가 같은경우에는 선물지수 를 계산하여 해당값이 지수가 더 큰 사람이 적은사람에게 받게된다.

선물지수 = 내가준선물수 - 내가받은선물수

 
선물을 주고 받은후에 가장 많이 선물을 받은 갯수를 정답으로 제출하면된다.
 
 

문제유추과정

해당 문제를 풀기위해 유추한 과정은 다음과 같다.
 
1. 각자 개인이 받은 선물과 준 선물을 기록한다.
2. 개인의 선물지수를 계산한다.
3. 모두 1:1 로 비교하여 각자가 선물을 줘야하는 상황인지 판단후에 선물을 주고받는다.
 

풀이과정

가장 오래걸리는 시간복잡도의 경우는 서로가 준 선물을 비교하는 과정인데 해당 과정에서 모든 친구를 1:1 로 비교할 경우 시간복잡도는 N x (N-1) 번 비교해야 하므로 O(n^2) 이 된다.
최대 친구의 수는 50 이므로 O(n^2) = 2500 이므로 완전탐색으로 시간내에 충분히 풀이가 가능하다 판단하였다.
 
처음 문제를 접했을때 Map을 이용하여 각 개인의 받은선물, 준선물, 선물지수 외에도 A 가 B 에게 준선물/받은선물을 모두 저장하여 완전탐색을 이용하여 모두 비교하였다.
 
1. 모든 결과를 컬랙션으로 저장하여 비교하기

  fun solution(friends: Array<String>, gifts: Array<String>): Int {
        // 각 친구가 준 선물과 받은 선물을 저장할 맵
        val sentGifts = mutableMapOf<String, Int>().apply { friends.forEach { this[it] = 0 } }
        val receivedGifts = mutableMapOf<String, Int>().apply { friends.forEach { this[it] = 0 } }

        // 선물 기록 처리
        gifts.forEach { gift ->
            val (giver, receiver) = gift.split(" ")
            sentGifts[giver] = sentGifts[giver]!! + 1
            receivedGifts[receiver] = receivedGifts[receiver]!! + 1
        }

        // 선물 지수 계산
        // associateWith -> 해당 키값을 갖는 키로 값을 계산하여 저장
        val giftIndex = friends.associateWith { friend ->
            sentGifts[friend]!! - receivedGifts[friend]!!
        }


        // 다음 달에 받을 선물 계산
        val nextMonthGifts = mutableMapOf<String, Int>()
            .apply {
                friends.forEach { this[it] = 0 }
            }

        val giveAndTakeMap = gifts.groupingBy { it }.eachCount()

        for (i in friends.indices) {
            for (j in i + 1 until friends.size) {
                val friend1 = friends[i]
                val friend2 = friends[j]
                val sentToFriend1= giveAndTakeMap["$friend1 $friend2"] ?: 0
                val sentToFriend2 = giveAndTakeMap["$friend1 $friend2"] ?: 0

                when {
                    sentToFriend1 > sentToFriend2 -> nextMonthGifts[friend2] = nextMonthGifts[friend2]!! + 1
                    sentToFriend2 > sentToFriend1 -> nextMonthGifts[friend1] = nextMonthGifts[friend1]!! + 1
                    giftIndex[friend1]!! > giftIndex[friend2]!! -> nextMonthGifts[friend1] = nextMonthGifts[friend1]!! + 1
                    giftIndex[friend1]!! < giftIndex[friend2]!! -> nextMonthGifts[friend2] = nextMonthGifts[friend2]!! + 1
                    else -> {}
                }
            }
        }
        // 가장 많이 받을 선물 수 반환
        return nextMonthGifts.values.maxOrNull() ?: 0
    }

 

 

알게된 코틀린 문법

 
1. Map 을 초기화 하는 방법.
  - MutableMap 의 apply 를 이용하여 초기화 하기
  - Array 의 groupingBy 함수를 이용하여 초기화 하기
  - associateWith 를 이용하여 초기화 하기
 
2. 컬랙션에서 값을 반환하는 방법.
  - 코틀린 컬랙션은 자바에서 배열형태 접근으로 값에 접근이 가능하다.
  - map["key"] 형태 또는 list[0(인덱스)] 형태
 
3. 각 컬랙션에서 사용되는 함수들
  - 배열.indices -> 배열을 순회하되 인덱스 값을 반환해줌. for 루프에서 사용됨.
  - Map 에서 value 중 최댓값 가져오기 : Map.values.maxOrNull()
 
4. 문자열 안에 변수로 문자열 만들기
  - "$변수 $변수" 형태로 두개의 문자열을 연결할수 있다.
 
5. when 절
  - when 절을 이용하여 if else 구문의 로직을 구성할 수 있다.
  - 각 람다형식은 한줄마다 하나의 조건으로 위에서부터 해당 조건이 맞는다면 해당 람다식을 수행하고 조건이 맞지 않을때는 최종 else 또는 when 절의 끝까지 도달하게 된다.
  - when(변수) 형태로 사용하게 된다면 java 에서 case 문으로도 사용이 가능하다.
 
 
6. Null 처리를 방지하기 위한 kotlin 의 요소들
  - !! -> 참조한 값이 절대 Null 이 될수 없다는 표현식. Null 일 경우 NPE 가 발생하게 된다.
  - ?: -> 해당 값이 Null 일 경우 콤마(:) 뒤에 오는 값으로 Default 값을 지정해 준다.