BOJ-2437 저울 Swift

문제

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 

입력

첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

출력

첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

내가 푼 풀이

- 주어진 추와 같은 무게의 물건을 잴 수 있고, 추로 잴 수 없는 무게의 최솟값을 구한다.

- 추의 무게를 오름차순으로 정렬 후, 추가 추가 될때마다 잴 수 있는 무게들을 배열에 두었다.

- 배열의 최솟값과 최댓값이 연속된다면, 잴 수 없는 무게는 최댓값+1 이 되고, 연속되지 않는다면 끊어진 무게 중 최솟값을 출력했다.

- 결과는 시간초과가 떴다.

- 연산 시간을 줄일 방법이 떠오르지 않아서, 결국 다른 사람의 풀이를 참고했다.

- 추의 무게를 오름차순으로 정렬후, 한 개씩 추가해 가며 측정할 수 있는 범위를 갱신한다.

- 추를 추가했을때 측정범위와, 이전 측정범위가 연속되지 않는다면, 이전 측정범위의 최댓값 + 1 이 측정할 수 없는 무게의 최솟값이 된다.

- 추를 모두 추가했는데 연속된다면, 측정범위의 최댓값 + 1 이 최솟값이 된다.

- 오름차순으로 정렬된 추의 첫 번째 무게가 1보다 크면, 측정할 수 없는 무게의 최솟값은 1 이 된다.

 

도움을 받은 글: https://aerocode.net/392

 

예제입력을 통해 예시를 들어보자

무게배열: [3,1,6,2,7,30,1] 이 주어졌을 때

오름차순으로 정렬하면 [1,1,2,3,6,7,30]이다.

 

- 무게 1을 추가했을 때

• 이전 측정범위: [0, 0]
• 추가한 측정범위: [1, 1]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 2

- 무게 1을 추가했을 때

• 이전 측정범위: [0, 1] 
• 추가한 측정범위: [1, 2]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 3

- 무게 2를 추가했을 때

• 이전 측정범위: [0, 2] 
• 추가한 측정범위: [2, 4]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 5

- 무게 3을 추가했을 때

• 이전 측정범위: [0, 4] 
• 추가한 측정범위: [3, 7]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 8

- 무게 6을 추가했을 때

• 이전 측정범위: [0, 7] 
• 추가한 측정범위: [6, 13]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 14

- 무게 7을 추가했을 때

• 이전 측정범위: [0, 13] 
• 추가한 측정범위: [7, 20]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 21

- 무게 30을 추가했을 때

• 이전 측정범위: [0, 20] 
• 추가한 측정범위: [30, 50]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하지 않는다.
• 이는 측정범위가 연속되지 않으므로 끊어진 범위중 최솟값을 구한다. [21,22,23,...,29] 중 최솟값
• 측정할 수 없는 무게의 최솟값: 21

 

따라서 주어진 추로 측정할 수 없는 무게의 최솟값은 21이 되는 것이다.

이를 바탕으로 코드로 구현한다.

 

import Foundation

let count = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{ Int($0)! }
var rangeNum = [0,0]
var min = 0
var sortedArr = arr.sorted{ $0 < $1}

// 추의 무게가 담긴 배열을 오름차순으로 정렬한다.
// 첫번째 추의 무게가 1보다 큰 수라면 최솟값은 1이된다.
// 첫번째 추의 무게가 1이고, 추의 갯수가 1 이라면 최솟값은 2가된다.
for i in 0..<sortedArr.count {
    if i == 0 {
        if sortedArr[i] != 1 {
            min = 1
        } else {
            rangeNum = [0,1]
            min = 2
        }
    } else {
        // range는 추가된 추로 새롭게 측정할 수 있는 범위
        // rangeNum은 이전의 추로 측정할 수 있는 범위이다.
        var range = rangeNum.map{ $0 + sortedArr[i]}
        
        
        // 이전의 측정가능한범위의 최댓값+1이 새롭게 측정가능한 범위의 최솟값 보다 크거나 같다면 연속된것
        // 연속됬다면 새롭게 측정가능한 범위의 최댓값+1이 정답이 된다.
        // 반대라면 끊어진 범위중 최솟값 출력
        if rangeNum[1]+1 >= range[0] {
            rangeNum = [0, range[1]]
            min = rangeNum[1] + 1
        } else {
            min = rangeNum[1] + 1
            break
        }
    }
    
}

print(min)