[★python_파이썬_복습]백준_10815번_숫자 카드_풀이

공부하는허딩크 : https://www.youtube.com/live/g4Jrq889Aoc?feature=shared

글이 길다. 자세히 읽어보면 그렇게 어렵지 않게 풀 수 있을 듯 하다.

 

<첫번째 시도 : 시간초과>

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

for i in M_nums:

    if i in N_nums:

        print(1, end = ' ')

    else:

        print(0, end = ' ')

 

한번에 코드를 작성 후 기대를 하고 결과를 기다렸으나 시간 초과....

 

점점 코드의 시간 복잡도가 중요한 것 같다.

숫자카드의 범위는 -10,000,000 <= X <= 10,000,000이라서 해당 숫자가 나오면 시간 복잡도를 꼭 생각해야한다.

 

근데 단순히 for문과 if문을 사용했는데 시간 복잡도가 그렇게 높나 ;;;;

 

<두번째 시도 : 시간초과>

좌표 압축 dict활용 : https://heodinkcodingdiary.tistory.com/38

[python_파이썬]백준_18870번_좌표 압축_풀이

좌표압축 문제에서 시간초과로 고생을 해서 dict를 활용해서 코드를 작성했다.

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

answer = {}

for i in M_nums:

    if i in N_nums:

        answer[i] = 1

    else:

        answer[i] = 0

for i in M_nums:

    print(answer[i], end = ' ')

 

역시나 시간초과네.

다른 방법을 고민해야 겠다.

 

<세번째 시도 : 시간초과>

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

answer = {N_nums[i] : 1 for i in range(len(N_nums))}

for i in M_nums:

    if i not in N_nums:

        print(0, end = ' ')

    else:    

        print(answer[i], end = ' ')

 

첫번째~세번째까지 거의 유사한 방법으로 코드가 작성되어 있어 시간초과가 발생했다.

 

아예 다른 방향 전환이 필요하다. 다른 풀이 참고해보자.

 

<네번째 시도 : 통과>

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

answer = {N_nums[i] : 1 for i in range(len(N_nums))}

for i in range(M):

    if M_nums[i] not in answer:

        print(0, end = ' ')

    else:

        print(1, end = ' ')

 

뭐지.... 기존꺼랑 거의 동일한데 왜 이건 통과가 되지;;;

 

2가지 코드의 차이점은 확인하는 범위의 차이이다.

통과된 코드는 M_nums의 요소들을 answer의 딕셔너리에서 확인하는 것이고 ==> O(M * N)

시간초과가 발생한 코드들은 N_nums의 리스트에서 확인하는 것이다. ==> O(N + M)

 

아직 시간 복잡도를 잘 모르겠다.... 이것까지 신경쓰려면 코드 자체가 너무 어려워 진다.

 

<다른사람 풀이 : 이진탐색 : 이게 잘 이해가 안되네. 복습필요>

import sys

N = int(sys.stdin.readline())

cards = sorted(list(map(int, sys.stdin.readline().split())))

M = int(sys.stdin.readline())

checks = list(map(int, sys.stdin.readline().split()))

for check in checks:

    low, high = 0, N-1  # cards의 이진 탐색 index

    exist = False

    while low <= high:

        mid = (low + high) // 2

        if cards[mid] > check:  # 중간 값보다 작다면

            high = mid - 1  # 중간보다 왼쪽 한 칸 옆까지 탐색

        elif cards[mid] < check:  # 중간 값보다 크다면

            low = mid + 1  # 중간보다 오른쪽 한 칸 옆부터 탐색

        else:

            exist = True

            break

    print(1 if exist else 0, end=' ')

 

 

<딕셔너리의 올바른 사용법>

1. answer.get(m)을 사용 : get은 key값이 없을 경우 None을 반환 => for문에서는 false임 or get(m, '디폴트값')

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

answer = {N_nums[i] : 1 for i in range(len(N_nums))}

# for i in range(M):

#     if M_nums[i] not in answer:

#         print(0, end = ' ')

#     else:

#         print(1, end = ' ')

for m in M_nums:

    if answer.get(m):

        print(1, end = ' ')

    else:

        print(0, end = ' ')

2. answer[m]에서 keyerror가 나옴 ==> 그래서 try / except로 error방지

import sys

input = sys.stdin.readline

N = int(input())

N_nums = list(map(int, input().split()))

M = int(input())

M_nums = list(map(int, input().split()))

answer = {N_nums[i] : 1 for i in range(len(N_nums))}

# for i in range(M):

#     if M_nums[i] not in answer:

#         print(0, end = ' ')

#     else:

#         print(1, end = ' ')

for m in M_nums:

    try:

        if answer[m]:

            print(1, end = ' ')

    except:

        print(0, end = ' ')