[Baekjoon][Python/파이썬] 18114번 블랙프라이데이

Kim Tae Won·2022년 5월 27일

baekjoon

18114번 블랙프라이데이

문제

풀이

1) 처음 접근 방법 + 문제점

- 풀이

처음 접근한 방식은 고른 물건의 수가 1개, 2개, 3개일 때를 구분해서 구현했었다.
1. 먼저 오름차순으로 정렬한다.
2. 각 case에 따라 나누어 binary search를 통해 확인한다.

1개 : 입력 받은 무게 C가 weights 리스트에 있는지 binarySearch를 통해 확인 한다.
2개 : 1중 for문을 통해 diff = C - weight[i]가 있는지 binarySearch로 확인한다.
3개 : 2중 for문을 통해 diff = C - (weight[i] + weight[j])가 있는지 binarySearch로 확인한다.

이를 구현한 코드는 아래와 같다.

#18114번 블랙프라이데이
import sys

def binarySearch(start, end, c, weights):
    while start <= end:
        mid = (start + end) // 2
        if weights[mid] == c:
            return mid
        if weights[mid] < c:
            start = mid + 1
        else:
            end = mid - 1
    return -1

def event(n, c, weights):
    if binarySearch(0, n - 1, c, weights) >= 0:# 고른 물건 1개
        return True 
    for i in range(n): # 고른 물건 2개
        diff = c - weights[i]
        if diff > 0 :
            if binarySearch(i + 1, n - 1, diff, weights) >= 0:
                return True
    for i in range(n): # 고른 물건 3개
        for j in range(i + 1, n):
            diff = c - (weights[i] + weights[j])
            if diff > 0:
                if binarySearch(j + 1, n - 1, diff, weights) >= 0:
                    return True
    return False

# N : 물건 개수, C : 무게
N, C = map(int, sys.stdin.readline().split())

# N개의 물건의 무게들
weights = list(map(int, sys.stdin.readline().split()))
weights.sort()

if event(N, C, weights):
    print(1)
else:
    print(0)

- 문제점

정답은 맞지만, 시간이 매우 오래 걸리게 된다.
특히 3개인 경우가 심하다.
- 이중 for문 이므로 시간 복잡도가 $O(n) = n^2\log_2n$ 까지 올라가게 된다.
  binary search조차 안하게 된다면 $O(n) = n^3$ 이므로, 매우 비효율적인 알고리즘이다.
- 특히 N의 범위가 $1 \leq N \leq 5000$ 이므로 최악의 경우 $5000^2\log_25000$ 이 된다.
- 이렇기 때문에 문제에서 정한 시간을 가뿐히 넘어버리게 된다.

2) 해결책

다른 문제에서 썼었던 two pointer를 조금 응용해보았다. 이 역시 개수에 따라 case를 나누었지만, 위와는 다르게 1개인 경우와 2개 or 3개인 경우로 나누었다. 이를 살펴보면,

먼저 오름차순으로 정렬한다.
각 case에 따라 나누어 binary search를 통해 확인한다.

1개 : 입력 받은 무게 C가 weights 리스트에 있는지 binarySearch를 통해 확인 한다.
2개 or 3개 :
- i : 제일 작은 값(0), j : 제일 큰 값(N - 1),
- weightSum = weights[i] + weights[j] 일 때,
- 2개인 경우는 weightSum이 C인 경우 True를 반환하면 된다.
  - weightSum이 C보다 크다면 i를 1씩 증가시킨다.
    - weightSum이 커지게 된다
  - weightSum이 C보다 작으면 j를 1씩 감소시킨다.
    - weightSum이 작아지게 된다
- 그리고 이제 3개인 경우는 이를 조금 응용해서 생각하면 된다.
  - 같은 weight인 상품은 고르지 못하므로 i번째와 j번째 weight는 제외하고,
  - diff = c - weightSum가 weights 리스트에 있는지만 확인하면 된다.

말로 설명하면 꽤 복잡하지만, 아래 코드를 보면서 따라가보면 충분히 이해가 될 것이다.

#18114번 블랙프라이데이
import sys

def binarySearch(start, end, c, weights):
    while start <= end:
        mid = (start + end) // 2
        if weights[mid] == c:
            return mid
        if weights[mid] < c:
            start = mid + 1
        else:
            end = mid - 1
    return -1

def event(n, c, weights):
    if binarySearch(0, n - 1, c, weights) >= 0:# 고른 물건 1개
        return True
    i = 0
    j = n - 1
    while(i < j): # 고른 물건 2개 or 3개
        weightSum = weights[i] + weights[j]
        if weightSum > c:
            j -= 1
        elif weightSum == c: # 고른 물건 2개
            return True
        else:
            diff = c- weightSum
            if diff != weights[i] and diff != weights[j] and binarySearch(0, n - 1, diff, weights) >= 0:
                return True # 고른 물건 3개
            i += 1
    return False

# N : 물건 개수, C : 무게
N, C = map(int, sys.stdin.readline().split())

# N개의 물건의 무게들
weights = list(map(int, sys.stdin.readline().split()))
weights.sort()

if event(N, C, weights):
    print(1)
else:
    print(0)

결론

- 결과

- 느낀 점

문제의 답은 어떻게든 구할 수 있지만, 코딩테스트나 일반적인 개발에서도 중요한 것이 바로 시간복잡도이다. N이 조금씩만 커져도 전체 프로그램의 시간복잡도가 걷잡을 수 없이 커지기 때문에, 이를 주의해서 생각해야 함을 깨달았다. 예전부터 풀어왔던 문제인데, 시간 복잡도 때문에 막혀서 방치해두었다가, 최근에 two poiner문제를 풀게 되면서, 이를 응용하면 되겠다고 생각했다. 배운 것을 응용해서 문제를 해결하는 것도 매우 중요하다고 생각이 들었다!

앞으로도 화이팅 하자!!!