악곱 == 악성곱슬

부품 찾기

---

해당 문제는 여러 방법으로 풀 수 있다.

우선 탐색문제인데, input이 1000만, 100만 등 매우 큰 숫자이므로 이진 탐색을 의심하여 아래와 같이 풀어볼 수 있다.

import sys

def binary_search(li, target, start, end):
    if start >= end:
        return None
    mid = (start + end) // 2
    if li[mid] == target:
        return mid
    elif target < li[mid]:
        return binary_search(li, target, start, mid - 1)
    else:
        return binary_search(li, target, mid + 1, end)

# O((M + N) * logN) = O(NlogN)[정렬] + O(M * logN)[이진탐색] 
def solution(numbers, targets, n, m):
    # 이진 탐색은 데이터가 정렬된 상태에서 사용
    numbers.sort()           # O(NlogN)
    for target in targets:   # O(M)
        answer = binary_search(numbers, target, 0, n)  # O(M) * O(logN)
        if answer is None:
            print("no", end=' ')
        else:
            print("yes", end=' ')

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    Numbers = list(map(int, sys.stdin.readline().rstrip().split()))
    M = int(sys.stdin.readline().rstrip())
    Targets = list(map(int, sys.stdin.readline().rstrip().split()))
    solution(Numbers, Targets, N, M)

이진 탐색보다 더 쉬운 방법으로 위 문제를 구현할 수 있다.

import sys

def solution(numbers, targets, n, m):
    # 이 문제는 set 을 이용하여 hash 자료형을 이용하여 구현할 수 있다.
    # 오히려 이진탐색보다 코드가 간결해져 편하다. 항상 쉽게 풀 수 있는 여러 방법을 생각해보자.
    number_set = set(numbers)    # O(N)
    for target in targets:       # O(M)
        if target in number_set:   # hash 구조라 in method = O(1)
            print("yes", end=' ')
        else:
            print("no", end=' ')

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    Numbers = list(map(int, sys.stdin.readline().rstrip().split()))
    M = int(sys.stdin.readline().rstrip())
    Targets = list(map(int, sys.stdin.readline().rstrip().split()))
    solution(Numbers, Targets, N, M)

마지막으로 앞서 배운 count sort 개념을 이용해서 구현할 수도 있다.

import sys

def solution(numbers, targets, n, m):
    for target in targets:
        if numbers[target] == 1:
            print("yes", end=' ')
        else:
            print("no", end=' ')

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    Numbers = [0] * 1000000
    for i in sys.stdin.readline().rstrip().split():
        Numbers[int(i)] = 1
    M = int(sys.stdin.readline().rstrip())
    Targets = list(map(int, sys.stdin.readline().rstrip().split()))
    solution(Numbers, Targets, N, M)

떡볶이 떡 만들기

---

해당 문제는 이진 탐색의 전형적인 문제이다.

파라메트릭 서치 문제이고, input이 매우 크기 때문에 이진 탐색을 떠올려야 한다.

떡을 자르는 높이를 이진 탐색을 통해 조정하며 구현하면 된다.

import sys

def solution(heights, n, m):
    start = 0
    end = max(heights)      # 처음, 끝 구함
    answer = 0
    while start <= end:
        mid = (start + end) // 2

        # heights 순회하며 탐색
        total = 0
        for height in heights:
            tmp = height - mid
            if tmp > 0:
                total += tmp

        # 총합이 더 크다면
        if total > m:
            start = mid + 1
        else:
            answer = mid
            end = mid - 1
    return answer

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().rstrip().split())
    Heights = list(map(int, sys.stdin.readline().rstrip().split()))
    print(solution(Heights, N, M))