[99클럽 코테 스터디 1일차 TIL] 집합과 이분 탐색

 

 

문제 : https://www.acmicpc.net/problem/2776

백준 2776번 문제

 

풀이

1. set 함수를 사용하는 방법

 set 함수는 순서가 없는 자료형입니다. 따라서 set을 사용하면 중복된 값이 제거가 됩니다.

 set을 사용함으로써 시간 복잡도가 O(N)이 됩니다.

t = int(input())
for _ in range(t):
    n = int(input())
    note1 = set(map(int,input().split()))
    
    m = int(input())
    note2 = list(map(int,input().split()))
    
    for num in note2:
        if num in note1:
            print(1)
        else:
            print(0)

 

 

2. 이분 탐색을 활용하는 방법

이진 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 입니다. 따라서 sort() 메서드를 사용하여 정렬을 우선 해줘야 합니다. 그리고 보통 변수 3개 (start, mid, end)를 사용하여 탐색하게 됩니다.

이분 탐색을 사용할 경우 시간 복잡도는 O(logN)입니다. 단계마다 탐색 범위를 반으로 나누는 것과 동일하므로 O(logN)이라는 시간 복잡도를 가지게 됩니다. 

def binary_search(target, data):
    start = 0
    end = len(target) -1

    while True:
        if start > end:
            return -1
        
        mid = (start + end) //2
        if target[mid] < data:
            start = mid + 1
        elif target[mid] > data:
            end = mid - 1
        else:
            return mid

T =int(input())

for i in range(T):
    N = int(input())
    note1 = list(map(int,input().split()))
    M = int(input())
    note2 = list(map(int,input().split()))
    note1.sort()
    
    for num in note2:
        if binary_search(note1, num) >= 0:
            print(1)
        else:
            print(0)

 

TIL

처음에는 아무생각 없이 둘 다 list 타입으로 입력을 받은 후 2중 for 문을 사용해서 구현을 했었습니다. 결과는 당연히 실패... 원인은 시간 초과...

그 이후에 알고리즘을 어떻게 최적화를 해야 할까 고민을 하게 되었고, 처음 생각났던 방법은 set 집합을 사용하는 방법이 이었습니다. 통과를 한 후, 다른 사람들은 어떻게 풀었을까 찾아보니 이진 탐색으로 푸는게 정석이라는 것을 알게 되었고 이진 탐색으로도 풀어본 후 통과를 했습니다.

구현에만 목적을 두지말고, 처음 부터 알고리즘 최적화에 신경을 쓰면서 작성을 해야겠습니다.

 

이 외에도 다른 방법이 있다면 정보를 공유해주시면 감사하겠습니다.