[조합] 배열 내의 숫자 조합 관련 문제

오랜만에 알고리즘 관련 문제를 풀어보려 합니다.

이번엔 조합 관련 문제입니다.

얼마 전에 코딩테스트가 있었고 거기서 영어 지문을 잘못 읽어서 실수를 했습니다. 다음날 문제를 잘못 읽은 걸 깨닫고 멘탈이 터졌던 관계로 다시는 이런 실수를 하지 말자는 의미에서 기억하고 있는 내용을 조금 변경 및 유사한 문제에 대해서 코테 연습 사이트를 참고해서 만들고 풀이를 해보려 합니다.

 

1. 문제

정수 배열 arr이 Parameter로 전달되는 함수 arrayChecker가 있고, 이 함수는 전달된 배열에서 가장 큰 수를 제외한 값들의 조합의 합에 대한 결과가 가장 큰 수와 동일한 경우 및 가장 큰 수를 제외한 값들을 활용하여 전달된 배열의 최대 및 세번째로 큰 값의 차와 동일한 조합의 합이 가능한지 여부를 true/false로 반환하는 함수입니다.

즉, 예를들어 가장 큰 수 10을 포함한 배열 [5, 1, 2, 4, 10]이 전달되었으면, 10을 제외한 5, 1, 2, 4를 조합해서 10과 동일한 값이 나오는지 확인을 하는 것입니다.

두 경우를 모두 만족하는 경우 true, 하나라도 만족하지 못하면 false를 반환하고, 배열의 갯수가 3개 이상이 아니라면 false를 반환합니다. 전달되는 배열은 음수를 포함할 수 있습니다.

 

2. 풀이

이 문제는 두가지 경우를 확인해야합니다.

첫번째로 전달된 배열의 값 중 가장 큰 수(max)를 제외하고, 그 나머지 값들(tempArr, max가 제외된 배열)의 조합 중 가장 큰 수와 동일한 경우가 있는지 확인을 해야하고

두번째로는 전달된 배열의 값 중 가장 큰 수(max)를 제외하고, 그 나머지 값들(tempArr, max가 제외된 배열)의 조합 중 가장 큰 수 와 세번째로 큰 수의 차와 동일한 값이 나올 수 있는지를 확인하고

위 두 결과값이 모두 true인 경우는 true를 반환, 그 외는 false를 반환해줍니다.

이 결과값들은 재귀를 통해서 한개의 function으로 해결할 수 있습니다.

2-1. 구현코드

func arrayChecker(_ arr: [Int]) -> Bool {
    guard arr.count >= 3 else { return false }
    var tempArr = arr.sorted(by: >) // O(n)
    let max = tempArr.removeFirst() // tempArr는 여기서 최대값이 제외된 배열이 된다.
    // let thirdBigNum = tempArr[1] // 최대값을 제외한 나머지 값이 내림차순으로 정렬되어 있기 때문에 1번 인덱스 값이 기존 arr의 3번째로 큰 값이 된다.
    let maxMinusThird = max - tempArr[1] // 최대값 - 세번째로 큰 값
    var combiFirstResult: Bool = false
    var combiSecondResult: Bool = false
    // 배열을 사용해서 값 계산
    func combi(_ nowArr: [Int], index: Int, isMax: Bool) {
        guard !(isMax ? combiFirstResult : combiSecondResult) && index < tempArr.count else {
            return
        }
        var combiArr = nowArr
        combiArr.append(tempArr[index])
        if combiArr.reduce(0, +) == (isMax ? max : maxMinusThird) {
            print("TRUE!")
            if isMax {
                combiFirstResult = true
            } else {
                combiSecondResult = true
            }
        } else {
            combi(combiArr, index: index + 1, isMax: isMax)
            combi(nowArr, index: index + 1, isMax: isMax)
        }
    }
    // 배열 사용 안하고 값으로 바로 계산
    func combiSecond(_ nowValue: Int, index: Int, isMax: Bool) {
        guard !(isMax ? combiFirstResult : combiSecondResult) && index < tempArr.count else {
            return
        }
        let addedValue = nowValue + tempArr[index]
        if addedValue == (isMax ? max : maxMinusThird) {
            print("TRUE!")
            if isMax {
                combiFirstResult = true
            } else {
                combiSecondResult = true
            }
        } else {
            combiSecond(addedValue, index: index + 1, isMax: isMax)
            combiSecond(nowValue, index: index + 1, isMax: isMax)
        }
    }
//    combi([], index: 0, isMax: true)
//    combi([], index: 0, isMax: false)
    
    combiSecond(0, index: 0, isMax: true)
    combiSecond(0, index: 0, isMax: false)
    return combiFirstResult && combiSecondResult
}

 

하..한동안 알고리즘과는 관계가 좀 떨어진 작업들을 해왔더니 머리가 굳었나봐요.. 예전 같으면 안 할 실수를 여기서 하다니;

이번에는 떨어졌겠지만, 다시 제대로 공부하고 지원해야 겠습니다.

(술 땡기네요)