240321 - 2024 카카오 윈터 인턴십

[robert-min]

문제

1. 가장 많이 받은 선물 링크
2. 도넛과 막대 그래프 링크
3. 주사위 고르기 링크
4. n+1 카드 게임 링크
5. 산모양 타일링 링크

[robert-min]

가장 많이 받은 선물

def solution(friends, gifts):
    """
    Return : 선물을 가장 많이 받은 친구가 받은 선물의 수
    - 선물 주고 받은 기록 O : 선물을 더 많이 준 사람이 받음
    - 선물 주고 받은 기록 X or 주고 받은 수가 같으면, 선물지수가 큰 사람이 받음
    - 선물지수가 같으면 주고받지 않음

    이번달
    선물 주고 받은 내역 chart
    선물 지수 저장 points
    인덱스 idx_record
    값 value_record
    """
    from collections import defaultdict
    N = len(friends)

    points = defaultdict(int)
    chart = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if i == j:
                chart[i][j] = -1

    idx_record, value_record = dict(), dict()
    for idx, value in enumerate(friends):
        idx_record[value] = idx
        value_record[idx] = value
    # print(idx_record)

    for gift in gifts:
        giver, receiver = gift.split()

        # 선물 지수 계산
        points[giver] += 1
        points[receiver] -= 1

        # chart 계산
        idx_giver = idx_record[giver]
        idx_receiver = idx_record[receiver]

        chart[idx_giver][idx_receiver] += 1
        chart[idx_receiver][idx_giver] -= 1

    answer = [0 for _ in range(N)]
    for c in range(N):
        for i in range(N):
            if chart[c][i] > 0:
                answer[c] += 1
            if chart[c][i] == 0:
                a = value_record[c]
                b = value_record[i]
                if points[a] > points[b]:
                    answer[c] += 1

    return max(answer)

[robert-min]

도넛과 막대 그래프

• 진입 차수와 진출차수를 활용한 문제

def solution(edges):
    """
    Return : 정점번호, 도넛, 막대, 8자 모양 그래프 수
    - edges

    indegree
    - 정점 번호 : 진입차수X, 진출 차수 2 이상
    - 막대 : 진입차수, 진출차수 X
    - 8자 : 진입차수, 진출차수 각각 2개 이상
    - 도넛 그 외 나머지
    """
    answer = [0, 0, 0, 0]
    indegree = {}
    for a, b in edges:
        if not indegree.get(a):
            indegree[a] = [0, 0]
        if not indegree.get(b):
            indegree[b] = [0, 0]

        indegree[a][0] += 1 # 진출차수
        indegree[b][1] += 1 # 진입차수

    for key, value in indegree.items():
        # 정점 번호
        if value[0] >= 2 and value[1] == 0:
            answer[0] = key

        # 막대
        elif value[0] == 0 and value[1] > 0:
            answer[2] += 1

        # 8자
        elif value[0] >= 2 and value[1] >= 2:
            answer[3] += 1

    answer[1] = indegree[answer[0]][0] - answer[2] - answer[3]
    return answer

[robert-min]

주사위 고르기

from itertools import combinations, product

def solution(dice):
    """
    Return : A가 승리할 확률이 높아지는 주사위 번호 오름차순
    - n / 2 , n / 2
    - 주사위에 나온 수를 모두 합해서 더 큰 쪽이 승리

    주사위를 선택하는 모든 경우의 수
    각 선택된 주사위에서 나올 수 있는 모든 경우의 수 A , B 비교 승리 수 저장
    """
    dp = {}
    N = len(dice)
    for A_index_comb in combinations(range(N), N // 2):
        B_index_comb = [i for i in range(N) if i not in A_index_comb]

        A, B = [], []
        for order_product in product(range(6), repeat= N//2):
            # print(order_product)
            A.append(sum(dice[i][j] for i, j in zip(A_index_comb, order_product)))
            B.append(sum(dice[i][j] for i, j in zip(B_index_comb, order_product)))
        B.sort()

        wins = 0
        for num in A:
            left, right = 0, len(B) - 1
            while left <= right:
                mid = (left + right) // 2
                if num <= B[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            wins += left
        dp[wins] = list(A_index_comb)

    max_key = max(dp.keys())

    return [x+1 for x in dp[max_key]]