0. 기본 정보

0-A. 개요

백준 - 10815번 문제가 어려워서 이리저리 해결법을 탐색해봄.

0-B. 문제 정보

백준 - 10815번: 숫자 카드

---

1. 내 제출

• 정말 단순히 list와 in 연산자를 통해 전부다 탐색하는 방식
  다만 이게 왜 느린지가 궁금했음.

n = int(input())
l = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))

answer = ['1' if x in l else '0' for x in t]
print(' '.join(answer))

1-A. 결과: 오답

---

2. 인터넷에서 찾은 정답

n = int(input())
l = list(map(int, input().split()))

_dict = dict()

for i in range(n):
    _dict[l[i]] = 0


m = int(input())
t = list(map(int, input().split()))

for j in range(m):
    if t[j] not in _dict:
        print(0, end=' ')
    else:
        print(1, end=' ')

---

3. 두 코드가 얼마나 다를까?

import random
from datetime import datetime

def your_code(n, l, m, t):
    start = datetime.now()
    _dict = dict()

    for i in range(n):
        _dict[l[i]] = 0


    for j in range(m):
        if t[j] not in _dict:
            # print(0, end=' ')
            pass
        else:
            # print(1, end=' ')
            pass
    end = datetime.now()
    return end-start

def my_code(n, l, m, t):
    start = datetime.now()
    
    answer = ['1' if x in l else '0' for x in t]
    # print(' '.join(answer))
    
    end = datetime.now()
    return end-start




if __name__=="__main__":
    n = random.randint(1,5000)
    l = [random.choice(range(-10000000,10000000+1)) for _ in range(n)]
    m = random.randint(1,5000)
    t = [random.choice(range(-10000000,10000000+1)) for _ in range(m)]

    compare = []
    for _ in range(1000):
        if your_code(n, l, m, t) > my_code(n, l, m, t):
            compare.append(1)
        else:
            compare.append(0)

    print(sum(compare))

• 둘 다 내놓는 답이 정답이라 가정한채 서로의 시간만 비교.
• n과 m의 범위가 (1,500000) 이지만 시간이 너무 오래 걸리는 관계로 (1,5000)으로 범위를 축소함.
• 정답 코드가 더 큰 값일 경우(= 더 오래 걸렸을 경우) comapre list에 1을 더하는것이기 때문에
  sum(compare)가 크면 클수록 정답 코드가 더 오래 걸린것!

3-A .결과

=> 1,000번 시행 중 약 20번 정도만 정답 코드가 느렸음.
내 코드는 거의 99% 비율로 느렸음!!

---

4. 왜 그런걸까??

4-A. chat-gpt의 답변

주어진 두 개의 코드 모두 같은 목표를 달성하는 코드로 보입니다.
하지만 두 코드의 성능 차이는 입력 데이터의 크기와 조건에 따라 다를 수 있습니다.

첫 번째 코드(정답 코드)에서 사용된 방식은 딕셔너리를 사용하여
_dict라는 데이터 구조에 l 리스트에 있는 값들을 저장하고,
두 번째 for 루프에서 해당 값이 _dict의 key에 있는지를 확인합니다.

이는 평균적으로 O(1)의 시간복잡도로 검색할 수 있습니다.

반면에 두 번째 코드는 in 연산을 사용하여 l 리스트에 값이 있는지를 확인합니다.
이 경우 l 리스트의 모든 원소를 순차적으로 확인하며 검색하므로
최악의 경우 O(n)의 시간복잡도가 소요됩니다.

따라서 입력 데이터의 크기와 형태에 따라 어떤 코드가 더 효율적인지는 상황에 따라 다를 수 있습니다. 보통은 딕셔너리를 사용한 첫 번째 코드가 입력 데이터가 많을 때 더 효율적일 가능성이 높습니다.

그렇다!! 시간복잡도 O(1)과 O(n) 수준으로 엄청난 차이를 보였던것!!

5. 마무리

정답 제출시 '시간 초과'로 오답이 됨.
=> python의 가장 기본적인 코드인데 왜 느린지 왜 다른게 더 빠른지 이유를 정확히 모르겠음.
=> 정답 코드와 내 코드를 비교
=> 어떤 부분에서 느린지 어떤 부분에서 얼마나 더 빠른지 확인

사실 해당 문제는 '이진 탐색' 문제였으나 딕셔너리로 푸는 방법도 있다는게 신기했다.

---

ref

• https://wlstyql.tistory.com/154