프로그래머스 Lv. 1 Swift 알고리즘 - 과일 장수

시간초과 오류가 났을 때 마음이 정말 아픈데...

그럼에도 불구하고 코드를 다시 짰을때 꽤나 간결해진 코드를 보고 있자면 마음에 평안이 온다.

이게 개발자들에게만 허락된 유일한 마약일까?

 

문제는 쉬웠다!

 

 

 

이 문제를 풀면서 생각한 논리적 흐름

1. score의 개수가 한 박스당 들어가는 개수인 m으로 나누어 떨어지면 1 box로 볼 수 있다.
2. 1번 테스트케이스의 경우 score가 7개고 한 박스당 4개가 들어가야하니 남은 3개는 자동으로 버려야한다.
3. 그러므로 score.count 개수를 m으로 나눈 몫들만 남기면 된다.(= boxCount)
4. 각 박스마다 최저 값을 구해야하는데 최대한 이익을 내기 위해서는 큰 값은 큰 값끼리, 작은 값은 작은 값끼리 들어가 있어야 유리하다.
5. 그래서 score를 오름차순 정리해준다.
6. 그 후 한 박스에 들어가는 개수 m만큼 값을 answerArray에 넣어준다.
7. 이 한 사이클이 끝나면 countNumber에 m만큼을 더해서 다음번 박스에 들어갈 원소들의 위치가 맞도록 조정해준다.
8. 이렇게 만든 박스들에서 최소값들을 찾아 값을 구한다.
9. 여기까지가 시간초과 오류 코드이다.
10. 오류를 해결하기 위해 다시 코드를 짜면서 느꼈다. 왜 이렇게 비효율적으로 코드를 짰을까..?
11. 결국 박스에 들어가는 값 중에 중요한 것은 최소값이고, sortedArray는 크기 순으로 정렬되어 있으니 박스에 들어갈 마지막 값들만 신경쓰면 됐다.
12. 그래서 stride를 이용해 각 박스의 마지막 원소들만 골라주었고 그 값들을 다 모아서 * m 해주었다.

 

 

* 첫번째 코드 (시간초과 오류)

import Foundation

func solution(_ k:Int, _ m:Int, _ score:[Int]) -> Int {
    let boxCount = score.count / m
    let sortedArray = score.sorted(by: >)
    var answerArray: [Int] = []
    var countNumber = 0
    var answer: [Int] = []
    var answerValue = 0
    
    if boxCount > 0 {
        for _ in 1...boxCount {
            for i in 0..<m {
                answerArray.append(sortedArray[i+countNumber])
            }
            answer.append(answerArray.min()!)
            countNumber += m
        }
    } else {
        answerValue = 0
    }
    
    for i in answer {
        answerValue += i * m * 1
    }
    
    return answerValue
}

 

* 두번째 코드 (통과)

import Foundation

func solution(_ k:Int, _ m:Int, _ score:[Int]) -> Int {
    let boxCount = score.count / m
    let sortedArray = score.sorted(by: >)
    var answerArray: [Int] = []

    if boxCount > 0 {
        for i in stride(from: m-1, to: score.count, by: m) {
            answerArray.append(sortedArray[i])
        }
    }

    return answerArray.reduce(0, +) * m
}

 

 

정리(Today I Learned)

1. 알고리즘을 풀때 항상 정해진 몇가지 함수들만 쓰다보니 익숙하지 않은 다른 함수들을 잘 안쓰게 된다. 코드를 짜는 것은 결국 효율화, 직관성과의 싸움이기에... 자주 쓸 수 있도록 노력해야겠다.