[Advanced] 3. 탐욕 알고리즘 - 문제편 (삼성 sw expert 5201 5202 5203)

*SW Expert Academy - Advanced Course를 공부한 내용입니다.

이론편 : 2021.07.22 - [Coding Test/SW expert (삼성)] - [Advanced] 3. 탐욕 알고리즘 - 이론편

---

# 5201. 컨테이너 운반

문제 : 화물 N개의 개수와 트럭 M개의 적재용량이 주어진다. 트럭은 하나의 화물만 실을 수 있으며, 편도로만 이동한다.
이때, 최대로 옮길 수 있는 화물의 무게는?

풀이 : 탐욕 알고리즘을 이용해서, 용량이 가장 큰 트럭에 무게가 가장 큰 화물을 실어보는 방식으로 풀이

        N, M = map(int, input().split())
        W_set = list(map(int, input().split())) # 화물 N개의 무게
        T_set = list(map(int, input().split())) # 트럭 M개의 용량

        T_set.sort(reverse=1) # 내림차순 정렬
        W_set.sort(reverse=1) # 내림차순 정렬

        sum_load = 0 # 총 적재 무게
        for i in range(M):
            while W_set:
                load = W_set.pop(0) # 남은 화물 중 가장 무거운 화물
                if load <= T_set[i]: # 적재 가능?
                    sum_load += load
                    break

        print(f'#{test_case} {sum_load}')

# 5202. 화물 도크 - 활동 선택 문제

문제 : 물류센터에 화물을 싣고 내리는 도크가 있다. 이것을 사용하기 위해 사용 신청을 넣은 목록이 주어질 때, 최대한 많이 사용되는 횟수를 구하라.

풀이 : 이론편에서 공부한 활동 선택 문제 이용. 종료시간 순서대로 정렬하여 탐욕 알고리즘으로 선택.

        N = int(input()) # 작업 개수

        work_list = []
        for i in range(N):
            schedule = list(map(int, input().split()))
            work_list.append(schedule)

        work_list.sort(key=lambda x: x[1]) # x가 work_list의 각 요소인 것, 종료시간 빠른 순으로 정렬

        cnt = 0
        a = work_list[0]
        while 1:
            workable = []
            for j in range(1, len(work_list)):
                if work_list[j][0] >= a[1]:  # 시작시간이 이전 작업의 종료시간 이후인지 확인하고 workable에 넣음
                    workable.append(work_list[j])

            cnt += 1 # 작업회수 증가
            if len(workable) == 0: # 더 이상 작업가능한 것이 없으면 종료
                break
            a = workable[0] # 0번재 작업이 종료시간이 제일 빠른 작업
            work_list = workable

        print(f'#{test_case} {cnt}')

# 5203. 베이비진 게임

문제 : 1과 2가 서로 돌아가며 카드를 뽑고, 먼저 run이나 triplet이 나오는 사람이 승자

풀이 : 갖고 있는 숫자카드 0~9의 개수를 표시하는 counts 배열을 생성하고, run과 triplet을 순서대로 검증

def CheckBabyGin(cards_list):
    counts = [0 for i in range(10)]
    for card in cards_list:
        counts[card] += 1

    # run 검사 : 연속 세개가 1이상 인지
    for i in range(len(counts)-2):
        if counts[i] >= 1:
            if counts[i+1] >= 1 and counts[i+2] >= 1:
                return 1

    # triplet 검사 : 3인거 있는지 검사
    for elem in counts:
        if elem == 3:
            return 1

    return 0

----------------------------------------------------------------------------

        cards = list(map(int, input().split()))
        player_a = cards[::2] # 카드를 교대로 가져감
        player_b = cards[1::2]

        result = 0 # 결과값 0으로 초기화
        for i in range(2, 6):
            cards_a = player_a[:i+1] # 현재 단계에서 뽑힌 카드만 추출
            cards_b = player_b[:i+1]
            if CheckBabyGin(cards_a)==1:
                result = 1 # A만 베이비진되면 결과값 1
                break
            elif CheckBabyGin(cards_b)==1:
                result = 2 # B만 베이비진되면 결과값 1
                break

        print(f'#{test_case} {result}')