취업 면접이나 알고리즘 테스트에서 자주 등장하는 문제들을 풀이하는 과정을 다루는 이 글에서는, ‘선물 전달하기’라는 주제를 통해 코틀린의 기초와 문제 해결 능력을 동시에 키우는 방법을 제시합니다. 이 문제는 그래프 이론의 기본적인 개념을 기반으로 하여, 실생활에서도 적용할 수 있는 로직을 제공합니다.
문제 설명
주어진 배열 gifts에는 N개의 사람과 각 사람에게 전달해야 할 gift의 우선순위가 순서대로 나열되어 있습니다. 각 사람은 특정한 수의 선물을 가지고 있으며, 이 선물은 반드시 상대방에게 전달되어야 합니다. 우리의 목표는 모든 사람이 원하는 선물을 정확히 한 번씩 전달받도록 만들고, 이를 위해 필요한 최소한의 선물 전달 동작을 계산하는 것입니다.
예를 들어, 다음과 같은 입력이 주어진다고 가정합시다:
gifts = [2, 0, 1, 3]이 경우, 각 사람은 다음과 같은 사람에게 선물을 전달합니다:
- 사람 0: 사람 2에게 전달
- 사람 1: 사람 0에게 전달
- 사람 2: 사람 1에게 전달
- 사람 3: 자기 자신에게 전달
따라서 동작은 3회가 필요합니다. 이 문제를 해결하기 위한 알고리즘을 코틀린으로 구현해 보겠습니다.
문제 접근 방법
이 문제를 해결하기 위해서는 각 사람의 선물 전달을 명확히 이해하고, 전달적 순환구조를 파악해야 합니다. 간단한 예외 처리를 통해 만약 어떤 사람이 선물을 전달할 필요가 없다면 그를 건너뛰는 방식으로 접근할 수 있습니다.
접근 방법
- 입력 배열
gifts의 길이를 N이라고 정의합니다. - 각 사람이 전달해야 할 선물의 방향이 어떤지 확인합니다.
- 모든 사람을 방문하여 선물을 전달하는 과정을 시뮬레이션합니다.
- 그룹의 크기를 세어 받은 선물의 순환을 파악합니다.
- 최종적으로 필요한 최소한의 전달 동작 수를 계산합니다.
코드 구현
다음은 위 접근 방법에 따라 구현된 코틀린 코드입니다:
fun minGiftTransfers(gifts: IntArray): Int {
val visited = BooleanArray(gifts.size)
var transfers = 0
for (i in gifts.indices) {
if (!visited[i]) {
var current = i
var cycleSize = 0
do {
visited[current] = true
current = gifts[current]
cycleSize++
} while (current != i)
// 축을 제외 (1개는 서로 선물 전달)
if (cycleSize > 1) {
transfers += (cycleSize - 1)
}
}
}
return transfers
}
// 테스트 케이스
fun main() {
val gifts = intArrayOf(2, 0, 1, 3)
println("선물 전달에 필요한 최소 동작 수는: ${minGiftTransfers(gifts)}")
}테스트 케이스
주어진 함수를 테스트하기 위해 다음과 같은 다양한 테스트 케이스를 작성해보았습니다:
-
테스트 1: 입력
gifts = [1, 0]
expected output = 1(사람 0이 사람 1에게 선물을 전달) -
테스트 2: 입력
gifts = [1, 2, 0]
expected output = 1(3사람이 서로 연결됨) -
테스트 3: 입력
gifts = [1, 2, 3, 4, 0]
expected output = 4(모두 다른 사람에게 전달) -
테스트 4: 입력
gifts = [0, 1, 2, 3, 4]
expected output = 0(자기 자신에게 전달)
결론
이번 강좌에서는 코틀린을 사용하여 ‘선물 전달하기’ 문제를 해결하는 과정을 살펴보았습니다. 알고리즘 문제를 해결하기 위해서는 문제의 요구 사항과 제약 조건을 명확히 인지하고, 이를 효율적으로 처리할 수 있는 방법을 모색하는 것이 중요합니다. 이 과정을 통해 kotlin의 기초 문법을 복습함과 동시에 로직 구성 능력을 기를 수 있었습니다.
기타 관련 있는 알고리즘 문제를 연습하여 더 많은 경험을 쌓고 알고리즘 테스트에서 경쟁력을 높여보세요!