백준 1092번 배 - SWIFT

문제

---

지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

 

 

입력

---

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

 

 

문제 링크

---

 

1092번: 배

 

 

풀이

---

이 문제는 그리디 알고리즘으로 해결할 수 있다.

무게를 많이 들 수 있는 크레인에게 무거운 박스를 할당하면 문제가 해결된다.

기본적으로 크레인들은 병렬적으로 움직이기 때문에 최대한 많은 크레인들에게, 자기가 옮길 수 있는 최대의 무게의 박스들을 할당해주면 문제는 해결이 된다.

 

프로그램 동작

1. 가장 먼저 크레인과 박스들의 정보를 입력받는다. ▼

 

 

2. 그리고 이들을 내림차순으로 정렬해준다. ▼

 

 

3. 정렬된 크레인과 박스들을 처음부터 하나씩 비교해본다.

만약 크레인이 견딜 수 있는 무게보다 박스 무게가 적다면 옮길 수 있다는 뜻이다.▼

 

 

옮길 수 있다고 판단이 들면, 해당 박스를 제거하고 다음 크레인으로 옮긴다. ▼

 

하지만 맨 처음 크레인과 맨 처음 박스의 무게를 비교해봤을 때, 옮길 수 없다면 프로그램은 종료된다.
가장 처음 크레인은 가장 많은 무게를 들 수 있고, 가장 처음 박스는 가장 무게가 큰데 가장 많은 무게를 들 수 있는 크레인이 이를 옮기지 못한다는 것은 다른 크레인들도 이를 옮길 수 없다는 의미이므로 박스를 다 옮기는 것은 불가능해진다. ▼

 

 

4. 다음으로 이동한 후에도 옮길 수 있다면, 아까 했던 과정을 똑같이 해준다. ▼

 

 

하지만 옮길 수 없다면, ▼

박스는 제거하지 않고 처음 크레인으로 이동한다.
이렇게 처음으로 이동했다는 것은 최대한 많은 크레인들에게 할당했고, 더 이상 할당할 수 없다는 의미이므로 시간에 1을 추가해준다. ▼

 

 

5. 그리고 위의 과정을 박스가 없어질 때 까지 반복해준다.

 

 

Swift 코드

---

func solve() -> Int {
    var N = Int(readLine()!)!
    var crane = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted(by: >)
    var M = Int(readLine()!)!
    var box = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted(by: >)
    var answer = 0

    if box[0] > crane[0] {
        return -1
    }

    while !box.isEmpty {
        answer += 1
        for i in 0..<crane.count {
            for j in 0..<box.count {
                if crane[i] >= box[j] {
                    box.remove(at: j)
                    break
                }
            }
        }
    }
    return answer
}

print(solve())

위에서는 인덱스가 다시 처음으로 돌아갈 때 시간을 추가하던데 여기서는 왜 처음부터 추가하죠?
코드에서는 어차피 루프가 실행된 이상 옮길 박스가 있다는 것이고, 옮길 박스가 있다는건 시간에 1이 무조건 추가된다는 의미이므로 루프의 시작에 1을 추가해줬다.

 

함수로 감싸면 빨라진다?

사실 필자는 이 코드를 거의 1년 전에 제출했었다.

하지만 돌아오는 것은 시간초과였다.

 

Swift의 `remove(at: )`은 시간복잡도가 O(1)이 아니라 O(n)이기에 예상이 가는 결과였다.

그렇다고 인덱스로 해결하기엔 코드가 엄청나게 복잡해질 것 같아서 그냥 포기하고 다른 문제를 풀었다.

그런데 최근에 이 문제를 해결하기 위해 다시 도전을 하는데, 아무리 생각해도 이 방법 말고는 다른 방법은 너무나도 복잡하여 해결이 불가능할 거 같았다.

그래서 혹시 다른 Swift 이용자들은 어떻게 해결했나 하고 다른 분의 블로그를 봤더니, 내가 짠 로직과 완벽히 같은데 통과가 됐다는 글이 있었다. ▼

백준 1092번: 배 - Swift

 

‘도대체 어떤 차이가 있어서 통과가 된걸까?’ 하고 위의 코드에서 사용한 거의 대부분의 기믹들을 하나씩 넣어보았다.

`enumerated()`로 인덱스 받아오기, 라이노 님의 `FileIO()` 대신 `readLine()`에 `split`과 `map`으로 입력받기, `while` 문에서 검사하지 않고, `while`문 내부에서 검사하기 등등… 많은 것을 넣어보았지만 시간초과는 그대로였다.

그래서 설마… 하는 마음에 모든 코드를 함수로 감싸고 실행을 했더니 통과가 되었다. ▼

1년전 나의 노력을 부정해버렸어…

 

 

위의 기믹들이 시간을 조금씩 줄여주다가, 마지막에 함수로 바꾼게 약간의 시간차이를 주어 통과가 된건가 싶어서 1년전에 제출했던 코드를 그대로 함수에 넣고 제출해봤더니 통과했다.

그게 바로 위에 있던 코드다.

그래서 그 이유가 무엇인지 조금 검색을 해보다가 chatGPT에게 물어봤는데, 꽤나 그럴듯한 답변을 주었다. ▼

Chat GPT의 답변
함수로 감싼 코드가 더 빠르게 실행되는 경우에는 주로 Swift 컴파일러의 최적화와 인라인화에 기인할 수 있습니다. Swift 컴파일러는 코드를 최적화하여 런타임 성능을 향상시키려고 노력합니다. 아래에 그 이유를 자세히 설명하겠습니다.
1. 인라인 최적화: Swift 컴파일러는 작은 함수 호출을 인라인으로 대체하는 최적화를 수행할 수 있습니다. 함수 호출은 실행 흐름을 변경하고 작은 오버헤드가 발생할 수 있기 때문에, 컴파일러는 이러한 함수 호출을 호출한 곳에 함수 본문을 직접 삽입하는 인라인 최적화를 수행합니다. 이로써 함수 호출 오버헤드를 피하고 성능을 향상시킬 수 있습니다.
2. 컨텍스트 스위칭 감소: 함수로 코드를 감싸면 컨텍스트 스위칭이 줄어듭니다. 컨텍스트 스위칭은 함수 호출 시에 스택 프레임을 생성하고 관리하는 작업을 의미하는데, 이 작업은 오버헤드를 초래할 수 있습니다. 함수 호출을 줄이는 것은 이러한 오버헤드를 감소시킬 수 있습니다.
3. 전역 범위와 비교할 때 더 적은 코드 양: 함수 내부로 코드를 감싸면 해당 함수 내에서 실행되는 코드의 양이 줄어듭니다. 작은 함수 내부에서 코드가 실행되면 캐시 지역성이 증가하고 CPU 캐시 활용이 개선될 수 있습니다.
4. 함수 내부의 로컬 변수 및 스택 프레임 최적화: 함수 내부에 있는 로컬 변수 및 스택 프레임은 컴파일러에 의해 더 효율적으로 관리될 수 있습니다. 컴파일러는 함수 내에서 사용되는 변수의 범위를 더 잘 이해하고 최적화할 수 있어서 성능 향상에 기여할 수 있습니다.
위와 같은 이유로, 함수로 코드를 감싸면 컴파일러가 더 효율적으로 최적화하고 인라인화하여 성능을 개선할 수 있습니다. 그러나 이러한 결과는 컴파일러의 동작과 Swift의 최적화 전략에 따라 다를 수 있습니다. 만약 성능이 크게 차이난다면, 성능 프로파일링 도구를 사용하여 성능 병목 현상을 파악하고 최적화할 부분을 찾아볼 수 있습니다.

 

chatGPT의 말을 100% 신뢰할 수 있는 것은 아니지만, 운영체제 수업과 프로그래밍 언어론에서 배웠던 내용들을 조합해봤을 때 이게 완전히 틀린 이야기는 아니라는 생각이 들었다.

함수로 감싸는게 프로그램 실행 시간을 더 줄일 수 있다는게 조금 충격이긴 하다...

다음에 문제를 풀때도 한 번 함수로 감싸서 제출해봐야겠다.