[python] 백준 18114 블랙프라이데이

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

1. 문제와의 교감

1) input도 쉽고 출력도 0,1만 확인해도 돼서 오 할만한데? 했다.
2) 조합으로 풀면 쉽게 풀릴까 생각해서 해봤다 => 실패
3) 이진탐색으로도 시도했으나 실패
4) 파이썬 풀이도 거의 없어서 어려웠다.
5) 시간초과해결이 진~~~짜 어려웠다.

2. 문제 풀이

1) 입력받고 정렬하기
2) 1개찾기(그냥 찾아도 되는데 이진탐색 활용)
3) 2개 찾기(sum값을 3개찾을때도 재활용해야 한다)
4) 3개 찾을때의 조건들까지 확인

[1]2개를 찾으면서 동시에 진행해야 한다.
[2]이미 찾은 것을 사용하면 안 된다.

3. 내 풀이

import sys
input=sys.stdin.readline
N,target=map(int,input().split())
data=list(map(int,input().split()))
data.sort() #정렬

#일반적인 이진탐색
def binary_search(arr, left, right, target):
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return 0

def find():
    #1개 찾기
    if binary_search(data,0,N-1,target):
        return 1

    left,right=0,N-1
    while left<right:
        summ=data[left]+data[right]
        if summ==target: #2개 검사하기
            return 1
        elif summ>target:
            right-=1
#2개도 아니다? 바로 3개로 넘어가기
        else:
            new_target = target-summ
            if data[left]!=new_target and data[right]!=new_target and binary_search(data,left,right,new_target): #조건 유의!
               return 1
            left+=1
    return 0

print(find())

더 최적화 된 방법이 있어 소개 드립니다.
set을 활용하여 2개검색과 3개검색을 한번에 해서 최적화 됐습니다.

import sys
input = sys.stdin.readline

def solution(now):
    N, target = map(int, input().split())
    lst = sorted(list(map(int, input().split())))
    box = set([0] + lst) # set으로 저장 // 0이 있어야
    if target in box: #한개
        return 1
    while now < N-1: #끝까지 탐색
        left, right = lst[now], lst[N-1] #left, right 설정
        new_target = target-left-right
        #set(0)을 추가하여 2개와 3개를 동시에 검색
        if new_target != left and new_target != right and new_target in box:
            return 1
        if new_target < 0:
            N-=1
        else:
            now+=1
    return 0

4. 느낀점

1. 시간복잡도를 먼저 계산해서 문제를 2번 푸는 일을 줄여야 겠다고 생각했다.
2. 이진탐색 감이 아직 부족한데 더 익혀야 겠다.