[파이썬] 백준 2798번 블랙잭

백준 2987번 블랙잭

• 브루트포스 문제

처음 내 접근 방법은

1. 리스트 내 요소를 3개씩 뽑고 새로운 리스트에 담기.
2. 그 과정에서 목표숫자가 나오면 즉시 return하며 종료
3. 나오지 않을 경우 새롭게 만들어진 리스트에서 이진탐색으로 값 출력하는 방법으로 풀었었다.

코드로하면 아래와 같다.

import sys
# 이진탐색을 위한 bisect
from bisect import bisect_left, bisect_right

cards, goal = map(int, sys.stdin.readline().split())
numbers = list(map(int, sys.stdin.readline().split()))
# 더해진 값들을 담아줄 리스트
sum_list = []

def blackjack(goal, numbers):
    global sum_list
    # 리스트 내 포인터역할
    first = 0
    second = first+1
    third = first+2
    while True:
        # 최소 3개의 조합이 나와야하므로 마지막 3개의 합이 마지막 경우의 수
        # first 포인터가 인덱스 [-3]에 위치하면 마지막 합계 더하고 종료
        if first == len(numbers)-3:
            sum_value = numbers[first] + numbers[second] + numbers[third]
            sum_list.append(sum_value)
            break
        # third 인덱스가 리스트 마지막 값까지 가도록
        if third < len(numbers):
            sum_value = numbers[first] + numbers[second] + numbers[third]
            sum_list.append(sum_value)
            third += 1
        else:
            # third가 길이를 초과할 경우 second 증가
            if second < len(numbers)-1:
                second += 1
                third = second + 1
            else:
                # second도 초과할 경우 first 증가
                first += 1
                second = first+1
                third = first+2
    # 목표값이 sum_list에 있다면 바로 출력
    if goal in sum_list:
        print(goal)
    else:
        # 없을 경우 이진탐색으로 찾아주기
        sum_list = sorted(sum_list)
        try:
            target = bisect_left(sum_list, goal)-1
            left = sum_list[target]
            right = sum_list[target+1]
            print(left if target-left < right-target else right)
        except:
            print(sum_list[-1])


blackjack(goal, numbers)

이 문제 풀려고 이진탐색까지 쓰는 풀이는 나밖에 없지않을까..

보다 효율적인 방법이 있을것같아, 다른 사람의 풀이를 참고했다.

간단하게 3중 for문과 max()를 통해 해결할 수 있었다.

import sys

numbers, N = map(int, sys.stdin.readline().split())
cards = list(map(int, sys.stdin.readline().split()))
length = len(cards)

def blackjack():
    bigger = 0
    for i in range(length-2):
        for j in range(i+1, length-1):
            # 여기서 k 값을 i+2로 시작하게 될 경우, 같은 요소로 더하는 경우가 발생해 실패한다.
            for k in range(j+1, length):
                total = cards[i]+cards[j]+cards[k]
                if total > N:
                    continue
                else:
                    bigger = max(total, bigger)
    print(bigger)


blackjack()

두 풀이 중 위는 메모리: 40300 KB, 시간: 160 ms

아래는 메모리: 30840 KB, 시간: 120 ms 만큼 소요된다.

보기도 좋고 풀이하기도 편하고 성능도 좋다. 위의 풀이를 사용할 이유가 없다.

하노이탑 쌓기 문제에 스택을 사용하려했던 것도 그렇고, 필요 이상의 리스트 사용을 줄여야겠다.