TIL 23-04-29 백준 알고리즘 - 숫자 카드

https://github.com/sdoram/Algorithm

https://github.com/sdoram/algorithm_solving_process

GitHub - sdoram/algorithm_solving_process: 알고리즘 풀이 과정 python 파일

 

1. 백준 알고리즘 - 숫자 카드

 문제점

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

# 입력

# N = 내 숫자 카드 N개

# N개의 숫자

# M = 비교할 숫자 M개

# M개의 숫자

# 출력 M개의 숫자가 각각 내 숫자 카드에 속하는지 확인하고 1 or 0 출력

 시도해 본 것들

입력받는 코드 작성 

N = int(input())
N_list = list(map(int, input().split()))
M = int(input())
M_list = list(map(int, input().split()))

 

정답 출력 코드 작성

answer_list = [m for m in M_list]
print(answer_list)

List Comprehension이 M_list를 제대로 출력하는지 확인

 

answer_list = [1 if m in N_list else 0 for m in M_list]
print(answer_list)

List Comprehension에 N_list 안에 m이 존재하면 1 아니면 0인 삼항 연산자 추가

아직 리스트 형태로 출력됨

 

answer_list = [1 if m in N_list else 0 for m in M_list]
print(*answer_list)

*을 통해서 언패킹으로 풀어서 출력 후 제출

 

N = int(input())
N_list = list(map(int, input().split()))
M = int(input())
M_list = list(map(int, input().split()))

answer_list = [1 if m in N_list else 0 for m in M_list]
print(*answer_list)

1%진행 후 시간 초과 발생 조건을 다시 읽어보니

N(1 ≤ N ≤ 500,000)
숫자는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다
M(1 ≤ M ≤ 500,000)
숫자는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

 이런 조건이 붙어있었다. 

 

시간 복잡도 개선 시도 

answer_list = [1 if M_list[m] in N_list else 0 for m in range(M)]
print(*answer_list)

for문을 리스트 대신 range로 하고 if문에서 M_list[m]으로 바꿔 봤지만 큰 개선은 없었다.

 

import sys
N = int(sys.stdin.readline())
N_list = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
M_list = list(map(int, sys.stdin.readline().split()))

입력받는 쪽이 문제일까 싶어서 sys.stdin.readline()으로 입력 변경

하지만 이 문제는 4줄만 입력 받기 때문인지 1%가 2%로 바뀌긴 했지만 근본적인 해결방법은 아니었다. 

 

set() 활용해보기 

set()을 사용하면 in으로 찾는 지금 코드가 개선 될 수 있다는 정보를 찾았다.

set()으로 중복값을 제거하는 정도로 지금의 문제가 해결 될 것 같지는 않았지만, 중복값이 없어도 되는 N_list를 set()으로 바꿔서 테스트 해봤다. 

 

기존 방식의 시간

N = 0
N_list = [0] * 10000 + [1] * 10000
M = 20000
M_list = [1] * 20000

answer_list = [1 if m in N_list else 0 for m in M_list]
print(*answer_list) # N_list time: 1.434967041015625

 

set으로 형변환시 시간 

N = 0
N_list = [0] * 10000 + [1] * 10000
M = 20000
M_list = [1] * 20000
set(N_list)

answer_list = [1 if m in N_list else 0 for m in M_list]
print(*answer_list) # set(N_list) time: 0.6827452182769775

이 테스트는 set()을 하는 순간 N_list의 길이가 2가 되기 때문에 극단적인 예시가 되겠지만, 개선 되는 걸 확인할 수 있었다.

 해결 방법

import sys
N = int(sys.stdin.readline())
N_list = set(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
M_list = list(map(int, sys.stdin.readline().split()))

answer_list = [1 if m in N_list else 0 for m in M_list]
print(*answer_list)

 알게 된 점

list의 in은 O(n)의 시간복잡도, set의 in은 O(1)의 시간복잡도를 가진다.
set의 O(1)인 이유는 입력 순서대로 index를 가지는 게 아닌 입력 값에 따라서 해시 테이블(hash table) 로 인덱스를 만든다. 그래서 해시 값으로 index가 정해지므로 in함수가 1개만 확인하고 존재 여부를 판단할 수 있다.
아마 이전에 알고리즘을 풀면서 set으로 중복값을 제거 했을 때 다시 list로 변환하는 과정에서 기존 list index가 아닌 가끔씩 튀는 숫자가 있던게 오늘 알게된 해시 테이블로 index 순서가 바뀌는 과정이 있던 것 같다.