백준 16471번 Python / Greedy

문제풀이 GitHub

https://github.com/Seokii/baekjoon

GitHub - Seokii/baekjoon: Daily Commit for Baekjoon

문제링크

https://www.acmicpc.net/problem/16471

16471번: 작은 수 내기

 

풀이

n = int(input())
j = list(map(int, input().split()))
s = list(map(int, input().split()))

j.sort(reverse=True)
s.sort()
cnt = 0

for i in j:
    if i >= s[-1]:
        pass
    else:
        cnt += 1
        s.pop()

if cnt >= (n+1)/2:
    print("YES")
else:
    print("NO")

카드의 수(n)와 주언이와 사장님이 받은 카드 리스트를 각각 j, s로 입력 받습니다.

주언이의 리스트는 내림차순으로, 사장님의 리스트는 오름차순으로 정렬합니다.

그 후, 주언이의 리스트의 원소들을 for문을 통해 사장님의 가장 큰 값과 비교해 같거나 더 크다면 pass합니다. (사장님의 가장 큰 값보다 같거나 더 크다면 어떤 카드를 내던 무조건 승부에서 지기 때문에)

그렇지 않다면, 카운트 후 사장님의 리스트에서 .pop()을 해줍니다.

예제 입력 1)

주언 : 2 1 3 5 6 -> 6 5 3 2 1

사장 : 1 1 3 2 5 -> 1 1 2 3 5

6, 5의 경우는 사장님의 마지막 원소 5보다 같거나 크기 때문에 pass 실행

3의 경우는 5와 매칭이 되면서 5를 pop() & cnt += 1

2의 경우는 3과 매칭이 되면서 3을 pop() & cnt += 1

1의 경우는 2와 매칭이 되면서 2를 pop() & cnt += 1

조건문과 같이 cnt의 수가 승부 횟수의 절반보다 크기 때문에 "YES" 출력