이것이 취업을 위한 코딩 테스트다 CHAPTER 11 그리디 문제

Q 01. 모험가 길드

'''

    Chapter 11. 모험가 길드

    접근법 1

        공포도가 낮은 모험가부터 그룹을 결성해보기

        그룹을 최대한 많이 만들어야하므로 그룹 내 사람 수 가 적어야 함

        그룹 결성 조건 == (마지막에 그룹에 들어간 사람의 공포도)가 (그룹 사람 수)보다 작을 때

       

'''

import sys
input = sys.stdin.readline

# 모험가의 수
N = int(input())
# 모험가의 공포도
fear = list(map(int,input().split()))
fear.sort()

answer = 0
cnt = 0
for i in fear:
    cnt += 1
    # 그룹이 결성이 되는가? == 방금 그룹에 들어간 사람의 공포도가 그룹사람수보다 작아야 결성
    if cnt >= i:
        answer += 1
        cnt = 0

print(answer)

 

Q 02. 곱하기 혹은 더하기

'''

    Chapter 11. 곱하기 혹은 더하기

    접근법 1

        자연수는 곱할수로 커진다

        0은 곱하면 0이 되니 더하기

        1은 곱하면 그대로 / 더하면 1증가이므로 더하기

        -> 0과 1은 더하고 나머지는 곱하기

'''

import sys
input = sys.stdin.readline

S = sorted(input().rstrip())

answer = 1
for i in S:
    # 0 혹은 1이면 더하기
    if i == '0' or i == '1':
        answer += int(i)
    # 0이 아니면 곱하기
    else:
        answer *= int(i)
print(answer)

 

Q 03. 문자열 뒤집기

'''

    Chapter 11. 문자열 뒤집기

    접근법 1

        (모든 0을 뒤집는 경우 : cnt_zero)와 (모든 1을 뒤집는 경우 : cnt_one) 중 더 적은 경우가 정답

        현재숫자와 다음숫자가 다른 경우 체크!

        01로 바뀌는 경우 -> cnt_one += 1

        10으로 바뀌는 경우 -> cnt_zero += 1

        ex) 110001인경우

            idx가 0일때 cnt_one += 1

            idx가 1일때 cnt_zero += 1

            idx가 4일때 cnt_one += 1

'''

import sys
input = sys.stdin.readline

S = input().rstrip()

# 모든 0을 뒤집을 때 뒤집을 횟수
cnt_zero = 0
# 모든 1을 뒤집을 때 뒤집을 횟수
cnt_one = 0

if S[0] == '0':
    cnt_zero += 1
else:
    cnt_one += 1

for i in range(len(S)-1):
    if S[i] != S[i+1]:
        if S[i+1] == '0':
            cnt_zero += 1
        else:
            cnt_one += 1

print(min(cnt_zero, cnt_one))

 

Q 04. 만들 수 없는 금액

'''

    Chapter 11. 만들 수 없는 금액

    접근법 1

        작은 동전부터 하나씩 추가하면서 확인

        target : 만들 수 있는지 확인해볼 숫자 == 지금까지 나온 수의 합보다 1 큰 수

        다음 동전이 target보다 크면 target과 그 동전 사이에 수는 못 만든다.

'''

import sys
input = sys.stdin.readline

# 동전의 개수
N = int(input())
# 동전
coin = list(map(int,input().split()))
coin.sort()

target = 1
for i in coin:
    # target을 만들고 싶은데 target보다 큰 수가 나오면 target은 못 만든다.
    if i > target:
        break
    target += i
print(target)

 

Q 05. 볼링공 고르기

'''

    Chapter 11. 볼링공 고르기

    접근법 1

        각 무게별로 볼링공이 몇 개씩 있는지 세기 -> Counter

        무게가 i인 볼을 선택할 때 나오는 경우의 수 합하기 (i=1,...,M-1)

        A가 무게가 i인 볼을 선택할 때 나오는 경우의 수 (B는 A보다 무거운 볼을 선택한다고 가정)

        (무게가 i인 볼)*(무게가 i+1인 볼) + ... +(무게가 i인 볼)*(무게가 M인 볼)

        == (무게가 i인 볼)*(무게가 i+1인 볼 + ... + 무게가 M인 볼)

'''

from collections import Counter
import sys
input = sys.stdin.readline

# 볼링공의 개수, 공의 최대 무게
N,M = map(int,input().split())
# 볼링공의 무게
ball = list(map(int,input().split()))

# 각각 무게 개수 세기
cnt = Counter(ball)
answer = 0
# 무게가 M인 볼링공을 고르는 경우 0
for i in range(1,M):
    N -= cnt[i]
    answer += cnt[i]*N

print(answer)

 

Q 06. 무지의 먹방 라이브

https://chaemi720.tistory.com/273

[프로그래머스] 무지의 먹방 라이브 - Python