[알고리즘] 2022 카카오 블라인드 테스트

문제 설명

카카오배 양궁대회가 열렸습니다.
라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다.
카카오배 양궁대회 운영위원회는 한 선수의 연속 우승보다는 다양한 선수들이 양궁대회에서 우승하기를 원합니다. 따라서, 양궁대회 운영위원회는 결승전 규칙을 전 대회 우승자인 라이언에게 불리하게 다음과 같이 정했습니다.

1. 어피치가 화살 n발을 다 쏜 후에 라이언이 화살 n발을 쏩니다.
2. 점수를 계산합니다.
   1. 과녁판은 아래 사진처럼 생겼으며 가장 작은 원의 과녁 점수는 10점이고 가장 큰 원의 바깥쪽은 과녁 점수가 0점입니다.
   2.  만약, k(k는 1~10사이의 자연수)점을 어피치가 a발을 맞혔고 라이언이 b발을 맞혔을 경우 더 많은 화살을 k점에 맞힌 선수가 k 점을 가져갑니다. 단, a = b일 경우는 어피치가 k점을 가져갑니다. **k점을 여러 발 맞혀도 k점 보다 많은 점수를 가져가는 게 아니고 k점만 가져가는 것을 유의하세요. 또한 a = b = 0 인 경우, 즉, 라이언과 어피치 모두 k점에 단 하나의 화살도 맞히지 못한 경우는 어느 누구도 k점을 가져가지 않습니다.**
       -   예를 들어, 어피치가 10점을 2발 맞혔고 라이언도 10점을 2발 맞혔을 경우 어피치가 10점을 가져갑니다.
       -   다른 예로, 어피치가 10점을 0발 맞혔고 라이언이 10점을 2발 맞혔을 경우 라이언이 10점을 가져갑니다.
   3.  모든 과녁 점수에 대하여 각 선수의 최종 점수를 계산합니다.
3. 최종 점수가 더 높은 선수를 우승자로 결정합니다. 단, 최종 점수가 같을 경우 어피치를 우승자로 결정합니다.

현재 상황은 어피치가 화살 n발을 다 쏜 후이고 라이언이 화살을 쏠 차례입니다.라이언은 어피치를 가장 큰 점수 차이로 이기기 위해서 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 구하려고 합니다.

화살의 개수를 담은 자연수 n, 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열 info가 매개변수로 주어집니다. 이때, 라이언이 가장 큰 점수 차이로 우승하기 위해 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 10점부터 0점까지 순서대로 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 만약, 라이언이 우승할 수 없는 경우(무조건 지거나 비기는 경우)는 [-1]을 return 해주세요.

---

대기업 코테 문제는 문제를 이해하는 것부터 쉽지 않다고 생각된다. 어려워보이지 않지만, 생각보다 고려해야 할 것이 많다. 

나는 dfs로 푸려고 했다. 하지만 dfs는 내가 잘 못하는 영역 중 하나이다. 때문에 chatgpt한테 물어봤다. 전능하신 chatgpt의 코드는 너무나 아름답고 깔끔했다. 당연하게도 내가 원하는대로 풀어주셨다. 이 아름다운 코드를 내 것으로 만들어야 한다. 생성해달라고 요구하고 이것을 반드시 내 것으로 만들어야 한다. 

 

앞에서부터 천천히 분석해보자.

def solution(n, info):
    max_diff = -float('inf')
    best_shot = [-1]

 

우선 max_diff를 설정한 이유는 최적의 해를 계산하기 위해서이다. 차이를 계산하기 위해서 초기값으로 나는 -9999 등과 같이 사용했는데, -float('inf')를 사용하면 그럴 필요가 전혀 없다. 그리고 best_shot이 [-1]로 설정된 이유는 라이언이 이기는 경우가 없을 때, [-1]을 반환하게 만들기 위해서이다. 

    def dfs(ryan_shot, idx, arrows_left):
        nonlocal max_diff, best_shot
        
        # 모든 과녁을 다 탐색했을 때
        if idx == 11 or arrows_left == 0:
            ryan_shot[10] += arrows_left  # 남은 화살은 0점 과녁에 다 쏘기
            ryan_score, apeach_score = 0, 0
            
            # 점수 계산
            for i in range(11):
                if info[i] == 0 and ryan_shot[i] == 0:
                    continue
                if info[i] >= ryan_shot[i]:
                    apeach_score += 10 - i
                else:
                    ryan_score += 10 - i
            
            diff = ryan_score - apeach_score

 

최근 chatgpt를 쓰면서 느낀건데, 알고리즘 문제를 풀 때 함수 안에 함수를 자주 사용한다. 난 이런 스타일을 쓸 생각도 못했지만, 생각보다 많이 사용하는 스타일인듯 하다. chatgpt는 내 진정한 스승님이다. 또 저 안에 nonlocal 이라는 키워드를 통해서 지역변수가 아닌 것을 명시적으로 알려주고 사용한다. 

 

dfs는 가장 앞에 종료조건이 나오게 된다. 이 경우 인덱스가 초과되거나, 남은 화살이 없는 경우이다. 남은 화살을 0점에 모두 쏘는 것도 사실은 설계의 하나가 아닌가 하는 생각이 든다. 

 

나는 코드를 짜면서 점수 계산을 하는 것이 비효율적이라 생각해서 인자로 넘겨줄까 했는데, 전능하신 gpt는 이것을 처음부터 계산한다. 안에서 계산해도 그렇게 오래 걸리지 않아서 그런가보다. 계산하는 코드는 문제 조건에 따라 내가 쏜 것이 더 많으면 점수로 인정하는 방식이다. 

 

그렇게 내 점수와 어피치의 점수 차이를 계산한다. 

            # 라이언이 이겼고, 가장 큰 점수 차이를 찾았을 때
            if diff > max_diff:
                max_diff = diff
                best_shot = ryan_shot[:]
            # 점수 차이가 같은 경우, 더 낮은 점수를 많이 맞힌 경우를 선택
            elif diff == max_diff:
                for i in range(10, -1, -1):
                    if ryan_shot[i] > best_shot[i]:
                        best_shot = ryan_shot[:]
                        break
                    elif ryan_shot[i] < best_shot[i]:
                        break
            
            ryan_shot[10] -= arrows_left  # 백트래킹
            return

 

라이언이 이긴 경우는 사실 양수가 되어야 하지만, 여기서는 그것은 제외한 듯하다. 라이언이 이기고 가장 큰 점수차이라면 best_shot을 업데이트 해준다. 이것이 정답으로 return 되는 것이다. 

 

와... 그리고 나는 점수 차이가 같은 경우는 생각도 안 하고 있었는데,,, 점수 차이가 같은 경우도 고려해야 한다. 까다롭다, 문제 예시에 있긴 했지만 수많은 경우를 머릿 속에서 구현해야 하고 이를 코드로 옮겨야 한다. 학교에서 4.32 받았지만, 이런건 이론 과는 상관 없이 코드를 그냥 많이 써봐야 한다고 생각한다. 

 

그리고 라이언이 마지막에 0점에 쏜 것은 다시 뽑아서 ryan_shot을 원상 복구하고 return 한다. 반환 값은 없어도 된다. list를 다룰 때는 dfs이후에 원상 복구를 하는 개념을 염두해야 한다. 

아래 경우도 마찬가지이다. 

 

        # 현재 점수대를 포기하는 경우
        dfs(ryan_shot, idx + 1, arrows_left)

        # 현재 점수대를 이기기 위해 필요한 화살을 쏘는 경우
        if arrows_left > info[idx]:
            ryan_shot[idx] = info[idx] + 1
            dfs(ryan_shot, idx + 1, arrows_left - ryan_shot[idx])
            ryan_shot[idx] = 0  # 백트래킹

 

건들인 경우에는, 원상복구를 하고 진행한다. 

 

    return best_shot if max_diff > 0 else [-1]

 

그런 후에, 마지막에는 max_diff가 0보다 큰 경우, 즉 이긴 경우가 있다면 best_shot을 반환하고, 없다면 [-1] return하는 아름답디 아름다운 코드이다.