[99클럽] 이분탐색 활용

백준 32978번

 

---

 

☄️ 문제 풀이 전 내 생각

2개의 배열을 비교해서 없는 하나를 찾아내는 문제로 순열탐색으로 실행할 경우 재료의 종류가 최대 1000개이므로상당히 오래걸릴 것 같다.
비교를할 때 어떻게 해야 최소화를 할 수 있는지 생각해보자문제에서 한 번씩만 주어진다는 표현을 보니 set()을 사용하진 않을 것 같다.
map을 사용해서 value의 값이 1인 것을 찾아내는 건 어떨까?
아니면 리스트에 sort()를 이용해서 이분탐색을 사용하는 방식은?
이분탐색에 대한 개념이 좀 부족하니 이 방식으로 문제를 구현해보자. 또한  앞선 map을 이용한 방식보다 시간복잡도가 상당히 줄어들 것 같은 예감이 든다.

소요시간: 45분

 

---

 

🌈 파이썬 코드

def 이분탐색(lst1, lst2):
    start = 0
    end = len(lst1) - 1
    while start <= end:
        half = (end + start) // 2
        if half >= len(lst2) or lst1[half] != lst2[half]:
            end = half - 1
        else:
            start = half + 1
    return start


def solution1():
    N = int(input())
    total = sorted(input().split(" "))
    use = sorted(input().split(" "))
    index = 이분탐색(total, use)
    return total[index]
print(solution1())

• 이분탐색에 대해서 아직도 오류가 나는 코드로 짜여서 GPT에게 도움을 좀 받았다. 많은 부분이 다르지만 특히나 end와 start에 -1, + 1을 하는 부분에서 왜 이렇게 해야하는지 잘 몰랐었는데 중복된 값을 피하기 위해서 현재 검사한 값인 half값을 범위에서 제외하는 과정이란 것을 알게 되었다.
• 심지어 다른사람의 풀이를 보고 좀 충격을 받아서 머리가 띵했다.

다른사람 풀이

# 풀이 1
n = int(input())
d = input().split()
r = input().split() 

for i in range(n-1):
    d.remove(r[i])

print(d[0])

# 풀이 2
N = int(input())
A = input().split()
U = input().split()

all_set = set(A)
used_set = set(U)

miss = all_set - used_set

print(miss.pop())

• 특히나 set()을 이용해서 해결하는 방식이 더욱 머리를 띵하게 하였다.