[BOJ #10815] 숫자 카드

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

 

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

 

내가 쓴 코드1

N = int(input())                            # N : 카드 개수
cards = list(map(int, input().split()))     # 카드에 적힌 정수 리스트 (중복 x)
M = int(input())                            # M : 정수 개수
numbers = list(map(int, input().split()))   # M 개의 정수 리스트

ex_lst = []                     # 존재 여부 저장 리스트
for num in numbers:             # numbers 의 정수 모두 접근
    exist = 0                   # cards 존재 여부
    for c in cards:             # cards 의 카드 모두 접근
        if c == num:
            exist = 1
    ex_lst.append(exist)

print(*ex_lst)

 

출력 결과

문제 읽고 20분도 안돼서 짠 코드다. 답도 잘나와서 틀릴거란 생각을 안했는데,, 웬걸 시간초과가 떴다.

구글링 결과, 백준 시간초과가 뜨면, 입출력할 때 쓰는 함수들과 리스트를 선언하고 할당하는 과정에서 append를 쓰는 것도 시간 복잡도가 크다는 것을 알게 되었다. 그것을 수정하여 코드의 함수들을 모두 수정하였다.

 

내가 쓴 코드2

from sys import stdin

N = int(stdin.readline())                            # N : 카드 개수
cards = list(map(int, stdin.readline().split()))     # 카드에 적힌 정수 리스트 (중복 x)
M = int(stdin.readline())                            # M : 정수 개수
numbers = list(map(int, stdin.readline().split()))   # M 개의 정수 리스트

ex_lst = [0]*M                  # 존재 여부 저장 리스트
for num in range(M):            # numbers 의 정수 모두 접근
    exist = 0                   # cards 존재 여부
    for c in cards:             # cards 의 카드 모두 접근
        if c == numbers[num]:
            exist = 1
    ex_lst[num] = exist

print(*ex_lst)

 

출력 결과는 위와 동일하고, 제출 결과도... 동일했다.. (충격) (스트레스,,)

같이 스터디하는 사람들에게 도움을 청했다[!!!sos!!!] 그리고 몇 가지를 수정할 수 있었다. 하나씩 고쳐서 제출해봤는데,, 이것도 몇 번을 고쳐나간지 모르겠다... 이놈의 시간초과,,ㅠㅠ

 

1) 이중 for문 쓰지 않기. (메모리)
2) 변수를 최소한으로.. (시간)
3)  list 보다는 set 쓰기. (시간)

 

내가 쓴 최종 코드1

N = int(input())                            # N : 카드 개수
cards = set(map(int, input().split()))	    # 카드에 적힌 정수 리스트 (중복 x)
M = int(input())                            # M : 정수 개수
numbers = list(map(int, input().split()))   # M 개의 정수 리스트

ex_lst = []                 	# 존재 여부 저장 리스트
for num in range(M):         	# numbers 의 정수 모두 접근
    if numbers[num] in cards:   # cards 의 카드 모두 접근
        ex_lst.append(1)
    else:
        ex_lst.append(0)

print(*ex_lst)

 

제출 결과

 

내가 쓴 최종 코드2

from sys import stdin

N = int(stdin.readline())                            # N : 카드 개수
cards = set(map(int, stdin.readline().split()))      # 카드에 적힌 정수 리스트 (중복 x)
M = int(stdin.readline())                            # M : 정수 개수
numbers = list(map(int, stdin.readline().split()))   # M 개의 정수 리스트

ex_lst = [0]*M                  # 존재 여부 저장 리스트
for num in range(M):            # numbers 의 정수 모두 접근
    if numbers[num] in cards:   # cards 의 카드 모두 접근
        ex_lst[num] = 1         # cards 존재 여부
    else:
        ex_lst[num] = 0

print(*ex_lst)

 

제출 결과

 

내가 시도한 모든 제출들의 결과...

ㅋㅋㅋㅋㅋ 이렇게 많이 시도한 사람이 또 있을까 싶은,,, 

백준에서 시간 초과 안당하려면, 오늘 알게 된 최적화 방법들을 항상 염두에 두고 풀어야겠다.. 시간초과 너무 열받아!!!