[백준] 올바른 배열 (1337)

문제 설명

백준 1337번 문제 링크

입력 및 출력

» 입력

첫째 줄에 배열의 크기 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 배열의 원소가 한 줄에 하나씩 주어진다. 원소는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다. 두 개 이상의 원소가 같은 경우는 없다.

» 출력

첫째 줄에 입력으로 주어진 배열이 올바른 배열이 되게 하기 위해서 추가되어야할 원소의 최소 개수를 출력한다.

예제 입출력(테스트케이스)

입력	출력
3 5 6 7	2

문제 풀이 (KOTLIN)

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val arr = mutableListOf<Int>()

    repeat(n) {
        arr.add(readLine().toInt())
    }

    println(counter(arr.sorted()))
}

fun counter(list: List<Int>): Int {
    var left = 0
    var right = 0
    var min = Integer.MAX_VALUE

    while (right >= left) {
        if (right >= list.size) break

        if (list[right] - list[left] > 4) left++
        else {
            val requiredCount = 5 - (right - left + 1)
            if (min > requiredCount) min = requiredCount
            right++
        }
    }

    return min
}

문제 풀이 (SWIFT)

func calculator(arr: inout [Int]) -> Int {
    var left = 0
    var right = 0
    var min = Int.max
    
    // left index가 right index를 초과하지 않을때 동작
    while left <= right {
        // right index가 arr배열의 index를 초과하지 않도록 break
        if arr.count <= right { break }
        
        // 인접한 두 거리의 차이가 4보다 크면 left index를 right index쪽으로
        // 한 칸 당겨와서 탐색하도록 left index에 1 증가
        if arr[right] - arr[left] > 4 { left += 1 }
        // 인접한 두 거리의 차이가 4와 같거나 작으면 (5보다 작을때)
        else {
            // 인접한 두 거리 사이 원소의 갯수는 requiredDistance와 같음
            let requiredDistance = 5 - (right - left + 1)
            // 인접한 두 거리 사이 원소의 갯수를 기존 min(최소 원소의 갯수)와
            // 비교하여 최솟값 갱신을 수행하고 right index를 1 증가하여 탐색을 지속
            if requiredDistance < min { min = requiredDistance }
            right += 1
        }
    }
    
    // [1, 2, 3, 4, 5]와 같이 1씩 증가하는 연속된 숫자가 5개 있는 배열의 경우 == 0
    // [1, 2, 3, 4, 6]와 같이 1씩 증가하는 연속된 숫자가 4개 있는 배열의 경우 == 1
    // [1, 2, 3, 6, 8]와 같이 1씩 증가하는 연속된 숫자가 3개 있는 배열의 경우 == 2
    // [1, 2, 6, 15, 25]와 같이 1씩 증가하는 연속된 숫자가 2개 있는 배열의 경우 == 3
    // [1, 6, 15, 25, 35]와 같이 1씩 증가하는 연속된 숫자가 없는 배열의 경우 == 4
    return min
}

let N = Int(readLine()!)!
var arr = [Int](repeating: 0, count: N)

for i in 0..<N {
    arr[i] = Int(readLine()!)!
}

// 주어진 배열을 오름차순으로 제자리 정렬을 수행
arr.sort(by: <)
// 제자리 정렬된 배열을 이용하여 배열이 주어진 조건에 맞는 올바른 배열이 되기위한 원소의
// 갯수를 탐색
print(calculator(arr: &arr))