[Baekjoon] Python 2789번 블랙잭
[Baekjoon] Python 2789번 블랙잭
URL :
https://www.acmicpc.net/problem/2798
블랙잭 변형 문제로 N개의 카드를 받고, 3장의 카드로 M을 넘지않는 합을 찾는 것이 목표입니다.
또 N번의 입력을 받는 것을 잊지말아야합니다.
제출 1 - 29284KB, 100ms, 334B
물론 3장의 카드를 뽑는 전체 방법을 고려해야하기에
의 시간복잡도를 가집니다.
N,M = map(int,input().split())
card=list(map(int, input().split()))
tmp = 0
for i in range(N-2):
for j in range(i+1,N-1):
for k in range(j+1,N):
tmpsum = card[i]+card[j]+card[k]
if tmp < tmpsum <= M:
tmp = tmpsum
print(tmp)
sys를 이용한 입력 방법
import sys
N,M=list(map(int, sys.stdin.readline().split()))
card=list(map(int, sys.stdin.readline().split()))
tmp = 0
for i in range(N-2):
for j in range(i+1,N-1):
for k in range(j+1,N):
tmpsum = card[i]+card[j]+card[k]
if tmp < tmpsum <= M:
tmp = tmpsum
print(tmp)제출 2 - 29284KB, 100ms, 478B
저는 여기에 시간을 줄이고 싶었기에 어떤 방법이 있을지 고민해봤습니다.
N,M = map(int,input().split())
card = sorted(list(map(int, input().split())))
tmp = 0
for i in range(N-2):
for j in range(i+1,N-1):
for k in range(j+1,N):
tmpsum = card[i]+card[j]+card[k]
if tmpsum == M:
tmp = tmpsum
break
elif tmp < tmpsum < M:
tmp = tmpsum
if tmp == M:
break
if tmp == M:
break
print(tmp)
제출 3 - 29284KB, 108ms, 622B
저는 if문을 더 추가해봤습니다.
이 방법은 별루인가 봅니다.
N,M = map(int,input().split())
card = sorted(list(map(int, input().split())))
tmp = 0
for i in range(N-2):
if card[i]>M:
continue
for j in range(i+1,N-1):
if card[i]+card[j]>M:
continue
for k in range(j+1,N):
tmpsum = card[i]+card[j]+card[k]
if tmpsum > M:
continue
if tmpsum == M:
tmp = tmpsum
break
elif tmp < tmpsum:
tmp = tmpsum
if tmp == M:
break
if tmp == M:
break
print(tmp)
제출 4 - 29284KB, 60ms, 543B - Python 1등 s1004101님의 코드
그래서 저는 1등 s1004101 코드를 살펴보았습니다.
저와 제출 2는 비슷했지만 차이점으로는
1. 애초에 카드를 reversed sorted로 큰 수부터 저장하는 list를 생성했다는 점
2. Python set 내장 함수를 통해 중복된 합을 제거하도록 했다는 점
3. Blackjack 즉 3장의 카드 합이 M과 같을 때 bool=True로 변경, 바로 for문을 나오도록 했다는 점입니다.
4. Blackjack이라면 바로 M을 출력하고 그 숫자가 아니라면 set 내장 함수에 저장해놓은 것들 중 max 값을 출력하도록 했습니다.
확실히 저보다 좋은 코드이고 속도 또한 60ms로 뛰어납니다. 제가 2019.12월에 돌려봤는데도 여전히 60ms가 나왔고 1등을 유지하고 계셨습니다.
N, M = map(int, input().split())
cards = list(reversed(sorted(map(int, input().split()))))
sumSet = set()
blackjack = False
for i in range(N-2):
for j in range(i+1, N-1):
for k in range(j+1, N):
sum = cards[i] + cards[j] + cards[k]
if sum == M:
blackjack = True
break
elif sum < M:
sumSet.add(sum)
break
if blackjack:
break
if blackjack:
break
if blackjack:
print(M)
else:
print(max(sumSet))
제출 5 - 29284KB, 108ms, 660B
저는 제출 4의 1등 코드에다 제출 3의 아이디어를 섞으면 더 빠르지 않을까 생각해봤습니다.
1. 3개의 카드의 합이 되기도 전에 1개나 2개의 카드가 M보다 크면 바로 넘겨버리는 if문을 보는 것
2. set 함수를 사용하지 않고 바로 sum과 이전 sum을 비교해서 더 큰 수를 tmpsum에 저장하는 단계
이렇게 두 개는 당연히 빠르게 넘길 수 있으니 좋은 성능이지않을까 생각해봤습니다만 현실은 그렇지 않았습니다.
오히려 if문을 고려하는 그 시간 소모가 더 문제가 됬고 if문들이 많은 상황 자체도 문제일 뿐 아니라 이전 sum과 현재 sum과의 비교 또한 시간에 영향을 주었습니다.
결국 계산하고 list에 집어넣은 다음 max를 구하는 것이 순간순간 if문으로 파악하는 시간보다 더 빠르다는 사실을 알게되었습니다.
N,M = map(int,input().split())
card = list(reversed(sorted(map(int, input().split()))))
tmp = 0
boolean=False
for i in range(N-2):
if card[i]>M:
continue
for j in range(i+1,N-1):
if card[i]+card[j]>M:
continue
for k in range(j+1,N):
tmpsum = card[i]+card[j]+card[k]
if tmpsum > M:
continue
if tmpsum == M:
tmp = tmpsum
boolean = True
break
elif tmp < tmpsum:
tmp = tmpsum
if boolean:
break
if boolean:
break
print(tmp)
제출 6 - 숏코딩 - 29284KB, 84ms, 123B - python 3 1등 sait2000
사실 블랙잭 방법은 Combination 조합으로 구하면 좋겠다는 생각을 해왔습니다.
그러나 방법을 모르던 찰나 itertools에서 Combination이라는 함수가 존재한다는 것을 숏코딩을 하면서 알게되었습니다.
이 방법은 물론 수작업보다 시간이 더 걸리지만 길이적인 측면이나 속도면에서 일반적인 방법보다는 빠르다는 것을 알 수 있었습니다.
역시 범상치않습니다.
[n,m],d=eval('map(int,input().split()),'*2);from itertools import*;print(max(v for v in map(sum,combinations(d,3))if v<=m))
결론
저도 돌려봤지만 쉽게 속도가 변하지 않았습니다. 채점하는 문제들에 따라 변동이 있겠지만 지금 백준 코드의 채점 예들로는 위 두 분의 코드에서 배울점이 많았습니다.
결론 : 제출 4에 해당하는 Python 1등 s1004101님의 코드, 제출 6에 해당하는 숏코딩 1등 sait2000 것이 제일 좋다
