백준_18114_블랙 프라이데이 (python)

★ 접근

처음에는 C가 최대 1억까지라서 1억 길이의 배열을 만들고 5000c2 조합을 통해 C와 무게가 같아질 수 있는지를 맞추려고 했다. 시간초과가 났다. 그 다음에 생각한 방법이 무게 w가 일렬로 주어지고 C라는 무게에  합을 맞추면서 최대 3개까지 조합해야 되기 때문에 투 포인터를 생각했다. 

 

★ 풀이

1. 입력받은 데이터를 오름차순으로 정렬한다.

2. 처음에 c가 data(입력받은 리스트)에 있는지 체크한다.

3. 없다면 left, right = 0, n-1로 초기화 하고 두개의 합을 구해 total에 저장한 후에 c보다 크다면 j를 줄이고

4. 같다면 두 개의 조합만으로도 바로 만들 수 있다는 거니 return해서 끝낸다.

5. total이 c보다 작다면 diff = c - total을 통해서 diff를 구하고 diff가 data[i], data[j]와 다르면서 data에 들어있는지 체크한다.

6. data에 들어있는지를 체크하는 것은 binary_search를 사용해 구해준다. binary_search를 사용하지 않으면 data의 최대 길이는 오천이기 때문에 최악의 경우 5000 * 5000인 경우가 날 수 있다. 

 

- 코드

import sys
input = sys.stdin.readline
n,c = map(int,input().split())
data = list(map(int,input().split()))
data.sort()

def binary_search(left,right,diff):
    while left <= right:
        mid = (left + right) // 2
        if data[mid] == diff:
            return 1
        elif data[mid] > diff:
            right = mid - 1
        else:
            left = mid + 1
    return 0

def check(n,c):
    if c in data:
        return 1
    i, j = 0, n-1
    while i < j:
        total = data[i] + data[j]
        if total > c:
            j -= 1
        elif total == c:
            return True
        else:
            diff = c - total
            if data[i] != diff and data[j] != diff and binary_search(i,j,diff):
                return True
            i += 1
          
if check(n,c):
    print(1)
else:
    print(0)

- 회고

 첫 번째 방법으로 1억짜리 배열을 만들어 문제를 풀려고 했다. 같은 방법으로 c++언어를 사용한 친구는 빠른 속도로 통과를 했고 시간초과가 나는 모습을 보고 이건 python으로 풀 수 없는 것인가를 생각했다. 포기하지 않고 투 포인터를 떠올렸다. 그러나 처음에 left, right = 0,1로 초기화 한다는 생각에 사로잡혀 left, right를 움직일 수 없는 지경에 이르렀다. total이 c보다 크다면 j를 줄여야하는데 j를 줄일 방법이 없게된다. 여기까지 왔을 때 j를 n-1로 초기화 할 생각을 했어야 됐는데 이미 첫번째에서 시간도 많이 쏟고 python은 왜 안돼!!!하면서 멘탈이 털린 상태라(구차한 변명이지만...) 떠오르지 않았다.