[백준 2776] 암기왕

06-07

알고리즘 분류 

• 자료구조 
• 정렬 
• 이분탐색 
• 해시를 사용한 집합과 맵 

풀이 

문제를 보고 쉽게 풀이과정을 떠올렸다. 알고리즘 분류를 보면 이렇게 단순한 구현문제는 아닐것같은데 

딕셔너리(해시)로 이용해서 풀어야할거 같은 느낌. 

첫 시도 list로 풀었다. 

내코드 1 

'''
try1. 너무 basic -> 시간초과 
1) input - testcase 
2) n
    2-1) note1  = []   
3) m 
    3-1) note2 = []
    3-2) for note2 돌면서 if~ 
'''
testcase = int(input()) 
for _ in range (testcase): 
    n = int(input()) 
    note1 = list(map(int,input().split()))

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

    for i in range(m): 
        if note2[i] in note1: 
            print(1) 
        else: 
            print(0)

시간초과가 났다. 테스트케이스가 1,000,000 이므로 일반적인 탐색방법으로는 시간초과가 날 것 같다는 생각은 했다. 

 

답코드를 보니 list를 set로만 바꾸면 된다고 해서 고쳐서 제출했더니 맞았다. 

답 코드 

testcase = int(input()) 
for _ in range (testcase): 
    n = int(input()) 
    note1 = set(map(int,input().split()))

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

    for i in range(m): 
        if note2[i] in note1: 
            print(1) 
        else: 
            print(0)

이것은 위에 코드에서 input 받을 때 시간 줄이기 위한 import sys 한것 (다른 사람 코드) 

import sys
t = int(sys.stdin.readline())
for i in range(t):
  n = int(sys.stdin.readline())
  memo1 = set(map(int,sys.stdin.readline().split()))
  m = int(sys.stdin.readline())
  memo2 = list(map(int,sys.stdin.readline().split()))
  for m2 in memo2:
    if m2 in memo1:
      print(1)
    else:
      print(0)

시간초과가 날 때 해봐야 하는 방법 

1. import sys 로 input 받는다. 

2. list를 set으로 바꾼다 

 

일단 이렇게만 

 

+++ 추가로 알고리즘 분류에서 이분탐색, 정렬.. 적혀있는게 걸려서 그 방법으로 푼 코드를 찾아보았다. 

이제 이분탐색 문제를 공략해봐야겠다. 

https://ddingmin00.tistory.com/28

[BOJ/python] 2776번 암기왕