[프로그래머스] 숫자 게임 (Python)

Problem : https://school.programmers.co.kr/learn/courses/30/lessons/12987#

프로그래머스

Status : Solved

Time : 00:30:31

 

---

 

문제 설명

 

xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다.

• 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다.
• 각 사원은 딱 한 번씩 경기를 합니다.
• 각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다.
• 만약 숫자가 같다면 누구도 승점을 얻지 않습니다.

전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 팀원들의 출전 순서를 정했습니다. 이때의 B팀이 얻는 승점을 구해주세요.
A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열 A와 i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열 B가 주어질 때, B 팀원들이 얻을 수 있는 최대 승점을 return 하도록 solution 함수를 완성해주세요.

 

입력 및 출력

 

제한사항

• A와 B의 길이는 같습니다.
• A와 B의 길이는 1 이상 100,000 이하입니다.
• A와 B의 각 원소는 1 이상 1,000,000,000 이하의 자연수입니다.

 

입출력 예

A	B	result
[5,1,3,7]	[2,2,6,8]	3
[2,2,2,2]	[1,1,1,1]	0

 

 

---

 

풀이

 

B팀의 최적의 전략은 "A팀의 각 원소를 초과하는 값 중 낼 수 있는 제일 작은 값을 제시하는 것"이 된다. 이 때 두 가지를 추가로 고려해 주어야한다.

 

1.  Upper bound : Upper bound는 이분 탐색의 변형 중 하나로써, 어떠한 배열에서 값 n을 탐색할 때 n을 초과하는 최소값을 찾는 알고리즘이다. 이를 적용하면 A의 각 원소에 대해 초과값 중 최솟값을 찾을 수 있다.
2.  Union Find : 또한 모든 값은 최소 1번밖에 사용하지 못하므로, 낼 수 있는 값은 사용하지 않은 값에 한정된다. 이를 체크하기 위해서 visited list등을 사용할 수 있으나, 나는 계산의 효율을 위해 union-find 방식을 채택했다. parent값을 스스로의 idx로 초기화하고, 1에서 구한 최소 idx는 다음과 같은 추가 과정을 거친다.
   1. idx의 parent는 그 idx이상의 값들 중 사용할 수 있는 최솟값의 idx를 가리킨다. find 함수는 그 idx의 parent p_idx를 반환한다.
   2. 만약 p_idx가 범위 내에 존재할 수 있는 값이면, answer를 1 증가시킨다. 그렇지 않으면 탐색을 종료한다.
   3. p_idx를 사용한 셈이므로 p_idx를 업데이트해 주어야 한다. 즉 바로 이후의 값인 p_idx+1의 parent를 find 값을 통해 구한다.
   4. 그리고 두 parent를 union함수를 통해 합하면, idx, p_idx, p_idx+1 의 parent는 모두 이후 사용 가능한 값의 idx를 가리키게 된다.

 

풀이 코드

def find(a, parent) :
    if a >= len(parent) or a == parent[a] :
        return a
    parent[a] = find(parent[a], parent)
    return parent[a]

def union(pa, pb, parent) :
    if pa < pb :
        parent[pa] = pb
    else :
        parent[pb] = pa

def solution(A, B):
    A.sort()
    B.sort()
    N = len(B)
    
    answer = 0
    parent = list(range(N))
    
    if A[0] > B[-1] :
        return 0

    for a in A :
        start, end = 0, N
        while start < end :
            mid = ( start + end ) // 2 
            if B[mid] <= a :
                start = mid + 1
            else :
                end = mid
        if end == N :
            continue
        idx = find(end, parent)
        if idx < N :
            answer += 1
            next_idx = find(idx+1, parent)
            union(idx, next_idx, parent)
    
    return answer

풀이 완료!