[코딩테스트 + 성능 회고] 🎯 양궁대회 - Kakao 2023

문제링크

문제링크

난이도

레벨2

유형

백트래킹

소요시간

1시간

회고

제한 시간이 넉넉해서 더럽게 풀어도 일단 통과는 된 것 같다. 예싵 테스트 케이스에 엣지 케이스를 친절하게 알려줘서 문제 난이도가 낮아진거 같다. 그럼에도 백트래킹은 쉽지만은 않은 것 같다.

1. 점수별 상태 트리를 조합을 구한다.

2. 상태 트리 점수 계산

3. 점수 계산 과정에서 조건에 맞지 않는 경우 소거

• 상태트리를 만들 수 없는 경우 - 남은 화살이 부족한 경우
• 어피치가 이기는 경우
• 점수가 현재 답과 이미 일치하는 경우 소거

회고2 성능

다른 스터디원이 채점 결과를 올렸는데 케이스 별로 속도 차이 극적인 부분이 신기했다.
팀원의 풀이는 특정 케이스에는 0.xx초로 나의 풀이보다 빨랐지만 또 특정 케이스에는 216ms 걸리는 등의 차이를 보였다.

그래서 풀이 방식이 어떻게 다르기에 결과가 차이가 날까? 고민하게 되었다.

첫째: 조합을 만드는 방식 차이에 따른 배열 크기 차이
  나) 해당 점수를 선택하지 말지의 [Bool] 배열을 만들어서 최대 조합의 수는 0 - 10점까지의 2의 11승 고정
      k가 커져도 조합의 갯수는 일정함, 대신 k가 작아도 고정적인 조합 생성

  팀원) 0 - 10점까지 화살의 몇(k)개 사용할지를 판단 C(10 + k, k)
      k = 1일 경우, C(11, 1)= 11
      k=20일 경우, C(30, 20) = 30,045,015
둘째: 가지치기, 이기는 경우, 최소한의 화살만 사용하여 케이스 소거
      true인 경우, 어피치보다 + 1만 더하여 라이언 화살 사용
      화살이 남지 않는 경우, 케이스 소거

풀이에 따른 케이스별 성능 비교

코드

var count = 0
var infos = [Int]()
var max = 0
var answer = [Int]()

func solution(_ n: Int, _ info: [Int]) -> [Int] {
    count = n
    infos = info

    combi()

    return answer.isEmpty ? [-1] : answer
}

func combi(_ index: Int = 0, _ current: [Bool] = []) {
    if index == 11 {
        calc(current, count)
        return
    }

    combi(index + 1, current + [false])
    combi(index + 1, current + [true])
}

func calc(_ current: [Bool], _ count: Int) {
    var remain = count
    var score = Array(repeating: 0, count: 11)

    var A = 0
    var L = 0

    for i in (0..<11) {
        if i == 10 {
            score[i] = remain
            break
        }

        if current[i] {
            remain -= infos[i] + 1
            if remain < 0 { return }
            score[i] = infos[i] + 1
        }
    }

    if score == answer { return }

    for i in (0..<11) {
        if score[i] == infos[i] && score[i] == 0 { continue }
        if score[i] > infos[i] {
            L += 10 - i
        } else {
            A += 10 - i
        }
    }

    if L <= A { return }

    if L - A > max {
        max = L - A
        answer = score
    } else if L - A == max {
        if answer.isEmpty { return }
        let reverseAnswer = Array(answer.reversed())
        let reverseScore = Array(score.reversed())

        for i in (0..<11) {
            if reverseAnswer[i] == reverseScore[i] { continue }

            if reverseScore[i] > reverseAnswer[i] {
                answer = score
                break
            } else {
                break
            }
        }
    } else { return }
}