[Kotlin, S4] 백준 1337번 올바른 배열

출처: unsplash.com

 

올바른 배열(1337번)

Silver 4

#구현 #정렬 #투 포인터

 

문제 내용

 

 

문제 접근

문제에서 올바른 배열은 리스트의 원소 5개가 연속적인 값을 가지는 리스트를 뜻한다.

정렬되지 않은 리스트가 주어질 때, 리스트를 정렬하고 나서 올바른 배열을 만들기 위해서는 몇 개의 원소를 추가해야 하는지 최소 개수를 출력한다.

입력 예제 1을 예로 들어 보면

3
5
6
7

리스트 5, 6, 7이 원소로 존재하는데, 5, 6, 7은 이미 연속된 수이기 때문에 2개만 있으면 올바른 배열을 만들 수 있다.

3, 4 또는 7, 8이 있으면 된다.

 

리스트의 원소 하나하나를 연속된 원소의 첫 원소라고 가정하고 올바른 배열을 만들기 위해 추가해야 할 원소의 개수는 최소 0개에서 최대 4개가 된다.

이미 올바른 배열인 경우에는 0개일 것이고, 연속되는 원소들이 하나도 없을 경우 4개가 된다.

입력 예제 1을 예로 들어 보면 5의 경우에는 연속되는 수 6, 7이 있기 때문에 2개만 있으면 된다.

6의 경우는 7이 있고 추가고 8, 9, 10이 있어야 해서 3개가 필요하고, 7은 4개가 필요할 것이다.

이런 방식으로 정답을 구해 나가면 된다. 입력받는 리스트의 길이가 50을 넘지 않기 때문에 가능하다.

 

입력받은 배열을 한 번 정렬해 주고 나서 반복을 돌려야 한다. 그래야 연속된 수의 개수를 세기 편하기 때문이다.

기준이 되는 리스트의 원소를 start로 삼고 반복을 돌리고, 올바른 배열을 만들기 위해 필요한 수의 개수를 needCnt로 정의하고 탐색할 index를 end로 설정한다.

for (start in 0 until list.size - 1) {
    var needCnt = 0
    var end = start + 1
    
    . . .
}

이제 기준을 start로 잡았으니, 5번 반복해서 start의 원소값을 기준으로 올바른 배열을 구성해 보자.

이미 리스트는 정렬되어 있기 때문에 연속되지 않아도 가장 작은 값부터 오게 된다.

 

<조건 1>

우선 end를 계속 이동시키면서 탐색해야 한다.

그런데 end가 list의 범위를 벗어날 수도 있다. 입력 예제 1에서 6을 기준으로 돌아야 할 때, 올바른 배열은 6, 7, 8, 9, 10이 되어야 하는데 8부터는 list의 범위를 벗어나게 된다.

즉, 올바른 배열을 만들기 위해 무조건 필요해지는 원소가 된다.

if (end in 0 until list.size) {
	. . .
} else {
    // 리스트의 범위를 벗어남. 그래서 수가 더 있어야 함.
    needCnt++
}

else로 빠지게 되면 list의 범위를 벗어난 위치이기 때문에 무조건 값이 추가되어야 한다.

만약 if로 들어가게 되면 이제 list값에서 연속된 값을 찾아줘야 한다. 조건 2로 들어간다.

 

<조건 2>

조건 1의 if로 들어오게 되면, list를 탐색하면서 연속된 값을 찾아야 한다.

연속된 수를 찾기 위해서는 start번째 원소에 순회 횟수만큼 더해 주면 필요한 값을 구할 수 있게 된다. 이 값이 리스트에 포함되어 있으면 end를 한 칸씩 뒤로 밀어주고, 아니면 필요한 원소이기 때문에 needCnt를 늘려 줘야 한다.

if (list[end] != list[start] + move) needCnt++
else end++

조건을 만족하게 된다면 필요한 숫자가 없다는 뜻이기 때문에 needCnt를 늘려 주고, 만족하지 못하면 필요한 숫자가 있다는 뜻이기 때문에 다음 list 원소를 확인하면 된다.

 

문제의 입력 예제 2를 예시로 들어 보겠다.

6
5
7
9
8492
8493
192398

이 예제의 정답은 2이다. 2인 이유는 5, 7, 9에서 6과 8을 추가해 주면 올바른 배열이 되기 때문이다.

5를 start로 잡고 순회를 돌면, 5는 조건 2의 else를 만족하게 돼서 end를 늘려 준다. 이제 다음 값을 6일 때는 값이 없기 때문에 needCnt를 늘린다. 이를 반복해 주면 if에는 6, 8일 때 들어와서 needCnt를 늘리고 그 외의 경우에는 else로 들어가 다음 원소를 탐색할 수 있게 해 준다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val size = readLine().toInt()
    val list = mutableListOf<Int>()

    for (i in 0 until size) {
        list.add(readLine().toInt())
    }
    list.sort()

    var consecutiveNumberCnt = 4
    for (start in 0 until list.size - 1) {
        var needCnt = 0
        var end = start + 1

        for (move in 1 until 5) {
            if (end in 0 until list.size) {
                if (list[end] != list[start] + move) needCnt++
                else end++
            } else {
                // 리스트의 범위를 벗어남. 그래서 수가 더 있어야 함.
                needCnt++
            }
        }

        consecutiveNumberCnt = min(consecutiveNumberCnt, needCnt)
    }

    println(consecutiveNumberCnt)
}

 

문제 풀이

입력받은 list를 정렬해 주고 조건 1과 조건 2를 수행해 최소의 추가되어야 할 원소의 개수를 구한다.

원소를 구하고 나면 consecutiveNumberCnt에 서로 값을 비교해 더 작은 값을 적용하면 된다.

consecutiveNumberCnt는 초기값이 추가되어야 할 최댓값인 4가 들어 있다.

 

 

문제 해결 과정

리스트의 원소를 타깃으로 만들어야 할 올바른 배열을 나타내고, 값이 없는 원소가 몇 개인지 구하는 아이디어 자체는 금방 떠올렸다.

근데 구현이 좀 귀찮았다. 구현 난이도도 딱 Silver 4에 맞는 문제인 듯하다.

리스트에서 start와 end를 동시에 사용하는 투 포인터 문제이다. 투 포인터로 구현하면 쉽게 해결 가능하다.