코틀린 코딩테스트 강좌, 조약돌 꺼내기

문제 설명

조약돌 꺼내기 문제는 주어진 수의 조약돌을 특정 규칙에 따라 꺼내는 문제입니다.
각 조약돌은 특별한 무게를 가지고 있으며, 우리는 두 가지 규칙에 따라 꺼낼 수 있습니다.

조약돌의 무게가 x 이하인 경우 꺼낼 수 있습니다.
조약돌을 꺼내면 그 조약돌의 무게가 0이 되며, 주변의 조약돌에 영향을 미칩니다.

문제 입력

첫 번째 줄에는 조약돌의 개수 N (1 ≤ N ≤ 100,000)과 무게 제한 X (1 ≤ X ≤ 10,000)가 주어집니다.
두 번째 줄에는 각 조약돌의 무게가 공백으로 구분되어 주어집니다. (1 ≤ 무게 ≤ 10,000)

예시

문제 해결 과정

이 문제를 해결하기 위해서는 다음과 같은 단계가 필요합니다:

1단계: 문제 분석

주어진 조약돌의 무게를 비교하는 문제입니다.
우리는 X 이하의 조약돌을 선택할 수 있으며, 이를 통해 몇 개의 조약돌을 꺼낼 수 있을지를 계산해야 합니다.
주어진 예제에서, 조약돌 무게는 [4, 5, 3, 2, 1]이고, X는 5입니다.
그래서 X 이하의 조약돌 무게(즉, 5 이하)를 가진 조약돌들은 5개입니다.
결과적으로, 우리는 5개의 조약돌을 꺼낼 수 있습니다.

2단계: 알고리즘 설계

문제를 해결하기 위해 사용할 수 있는 알고리즘은 다음과 같습니다:

입력된 조약돌의 개수를 세고, 각 조약돌의 무게를 확인합니다.
무게가 X 이하인 조약돌을 카운트합니다.
최종적으로 카운트한 개수를 출력합니다.

3단계: 코틀린 코드 구현

아래는 위의 알고리즘을 코틀린으로 구현한 코드입니다:

        
        fun main() {
            val input = readLine()!!.split(" ").map { it.toInt() }
            val n = input[0]
            val x = input[1]

            val weights = readLine()!!.split(" ").map { it.toInt() }
            val count = weights.count { it <= x }

            println(count)
        }

4단계: 시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)입니다.
각각의 조약돌 무게를 확인해야 하므로, 입력받는 조약돌의 개수에 비례하여 시간 복잡도가 결정됩니다.

결론

조약돌 꺼내기 문제는 조건에 따라 데이터를 필터링하는 기초적인 알고리즘 문제입니다.
코틀린을 활용하면 이러한 문제를 간결하게 해결할 수 있으며, 기본적인 데이터 처리 기술을 연습하는 데에 좋은 학습 자료입니다.