[프로그래머스] 2024 카카오 WINTER INTERNSHIP : 가장 많이 받은 선물 코틀린 풀이

 

오늘은 2024 카카오 WINTER INTERNSHIP 기출 문제를 풀어보려한다.

문제 링크는 다음과 같다.

나는 코틀린으로 문제를 풀었다.

---

문제를 정리해보자.

✅ 문제 핵심

• 각 친구쌍 A-B에 대해
  • A가 B에게 더 많이 선물 줬으면 → B는 A에게 1개 받는다.
  • 같거나 주고받은 기록이 없으면 → 선물지수가 높은 쪽이 1개 받는다.
  • 선물지수도 같으면 아무 일도 없다.

✅ 자료구조 설계

1. nameToIndex: 이름 → 인덱스 변환 (빠른 조회용)
2. giftMatrix[i][j]: i번 사람이 j번 사람에게 준 선물 수
3. giftGiven[i]: i번 사람이 총 준 선물 수
4. giftReceived[i]: i번 사람이 총 받은 선물 수
5. nextMonthGifts[i]: i번 사람이 다음 달에 받을 선물 수

 

처음 작성한 코드는 다음과 같다. (최적화 전)

fun main() {
    val friends = listOf("muzi", "ryan", "frodo", "neo")
    val gifts = listOf(
        "muzi frodo",
        "muzi frodo",
        "ryan muzi",
        "ryan muzi",
        "ryan muzi",
        "frodo muzi",
        "frodo ryan",
        "neo muzi"
    )

    // nameToIndex: 이름 → 인덱스 변환 (빠른 조회용)
    //giftMatrix[i][j]: i번 사람이 j번 사람에게 준 선물 수
    //giftGiven[i]: i번 사람이 총 준 선물 수
    //giftReceived[i]: i번 사람이 총 받은 선물 수
    //nextMonthGifts[i]: i번 사람이 다음 달에 받을 선물 수

    // 순서
    // 1. 선물 기록 반영
    // 2. 선물 지수 계산

    // 코드 흐름
    // giftMatrix[i][j] += 1: 선물 기록을 행렬에 쌓고,
    //giftGiven[i], giftReceived[i]로 총합 계산
    //다음 달 받을 선물 수는 조건 분기해서 nextMonthGifts[i]에 저장
    //최종적으로 max()로 가장 많이 받은 수를 리턴

    val nameToIndex = friends.withIndex().associate { it.value to it.index }

    val giftMatrix = Array(friends.size) { IntArray(friends.size) }
    val giftGiven = IntArray(friends.size) // [0,0,0,0,]
    val giftReceived = IntArray(friends.size) // [0,0,0,0,]

    for (i in gifts.indices) {
        val gift = gifts[i].split(" ")

        val gi = gift.first()
        val re = gift.last()

        val giver = nameToIndex[gi]
        val receiver = nameToIndex[re]

        giftMatrix[giver!!][receiver!!] += 1
        giftGiven[giver!!] += 1
        giftReceived[receiver!!] += 1

    }

    val giftScores = IntArray(friends.size)
    for (i in friends.indices) {
        giftScores[i] = giftGiven[i] - giftReceived[i]
    }

    // nextMonthGifts
    val nextMonthGifts = IntArray(friends.size)
    for (i in friends.indices) {
        for (j in friends.indices) {
            if (i == j) continue

            val aToB = giftMatrix[i][j]
            val bToA = giftMatrix[j][i]

            if (aToB > bToA) {
                nextMonthGifts[i] += 1
            } else if (aToB == bToA) {
                if (giftScores[i] > giftScores[j]) {
                    nextMonthGifts[i] += 1
                }
            }
        }
    }

    println(nextMonthGifts.maxOrNull() ?: 0)
}

 

정말 연습장처럼 고민한 흔적들을 주석으로 남겨둔 코드고

아래에 코드는 추가로 최적화한 코드이다.

 

fun solution(friends: Array<String>, gifts: Array<String>): Int {
    val n = friends.size
    val nameToIndex = friends.withIndex().associate { it.value to it.index }

    val giftMatrix = Array(n) { IntArray(n) }  // A -> B 선물 횟수
    val giftGiven = IntArray(n)               // 총 준 선물
    val giftReceived = IntArray(n)            // 총 받은 선물

    // 선물 기록 반영
    for (gift in gifts) {
        val (giver, receiver) = gift.split(" ")
        val gi = nameToIndex[giver]!!
        val ri = nameToIndex[receiver]!!

        giftMatrix[gi][ri] += 1
        giftGiven[gi] += 1
        giftReceived[ri] += 1
    }

    // 선물 지수 계산
    val giftScores = IntArray(n) { i -> giftGiven[i] - giftReceived[i] }

    val nextMonthGifts = IntArray(n)

    for (i in 0 until n) {
        for (j in 0 until n) {
            if (i == j) continue

            val aToB = giftMatrix[i][j]
            val bToA = giftMatrix[j][i]

            if (aToB > bToA) {
                nextMonthGifts[i] += 1
            } else if (aToB == bToA) {
                if (giftScores[i] > giftScores[j]) {
                    nextMonthGifts[i] += 1
                }
            }
        }
    }

    return nextMonthGifts.maxOrNull() ?: 0
}

 

✅ 코드 흐름 설명

• giftMatrix[i][j] += 1: 선물 기록을 행렬에 쌓고,
• giftGiven[i], giftReceived[i]로 총합 계산한다.
• 다음 달 받을 선물 수는 조건 분기해서 nextMonthGifts[i]에 저장한다.
• 최종적으로 max()로 가장 많이 받은 수를 리턴한다.

---