[백준 2776] 암기왕

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

2776번: 암기왕

• 문제 설명
  먼저 첫 번째 줄에 테스트 케이스의 개수를 입력받는다. 그다음줄에 N을 입력받고 다음 줄에 N개의 정수를 입력받는다. 똑같이 다음 줄에 M을 입력받고 M개의 정수를 입력받는다. 
  M개의 숫자들이 N개의 숫자 안에 존재한다면 M개의 숫자 순서대로 1을 없다면 0을 출력한다.

 

---

• 처음 시간초과 코드

T = int(input())
for i in range(T):
    N = int(input())
    lst1 = list(map(int,input().split()))
    M = int(input())
    lst2 = list(map(int,input().split()))
    for j in lst2:
        if j in lst1:
            print(1)
        else:
            print(0)

 

단순하게 입력 조건대로 모두 입력받고 for문을 M개의 숫자 안에서 돌려 N에 있는지 확인을 했다. 역시나 시간초과가 났으며이 문제는 이분탐색 및 집합을 이용해서 풀어야 한다.

 

• 제출 코드

T = int(input())
for i in range(T):
    N = int(input())
    lst1 = set(map(int,input().split()))
    M = int(input())
    lst2 = list(map(int,input().split()))
    for j in lst2:
        if j in lst1:
            print(1)
        else:
            print(0)

 

위 코드는 집합을 이용해서 풀이한 코드이다. M개의 숫자들이 N개의 숫자에 존재하는 지만 확인하면 되므로 N은 집합으로 구성해도 된다는 점을 인지하면 시간 초과 없이 쉽게 풀 수 있는 문제이다. 다른 어려운 부분은 없었던 것 같다.

 

• 이진 탐색을 이용한 코드

def binary_search(start,end,lst,num):
    while start<=end:
        mid = (start+end)//2

        if lst[mid] == num:
            return 1
        elif lst[mid] < num:
            start = mid + 1
        else:
            end = mid - 1
    return 0

T = int(input())
for i in range(T):
    N = int(input())
    lst1 = list(map(int,input().split()))
    lst1.sort()
    M = int(input())
    lst2 = list(map(int,input().split()))
    for j in lst2:
        print(binary_search(0,N-1,lst1,j))

 

이분 탐색을 하는 함수를 따로 만들어서 문제를 해결할 수 있다.

---

• 마무리
  요즘 자격증 공부도 하고 학교 팀플도 자주 하고 놀기도 노느라 코테문제를 자주 풀지 못했다. 역시 안 하면 안 할수록 알고 있던 것 들고 가물가물하고 점점 까먹는 것 같다. 간단한 문제나 쉬운 문제라도 혹은 답안을 보더라도 매일 적어도 한 문제씩 풀며 감을 계속 길러야 할 것 같다.