1 분 소요

10816번: 숫자 카드2

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.


첫번째 시도 . 이진탐색을 공부하기 이전(2022년 02월 4일)

 N=int(input())
 num=list(map(int,input().split()))
 M=int(input())
 compare=list(map(int,input().split()))
 
 count=0
 count_box=[]
 #단순히 순차탐색으로 구현을함.
 for i in compare:
     for j in num:
         if i==j:
             count+=1
     count_box.append(count)
     count=0
 
 print(' '.join(map(str,count_box)))

»output

 Time error

🌝 Thinking

순차탐색을 이용하여 시간 초과가 나왔다. 그렇다면 어떻게 해결을 해야할 것인가?


두번째 시도 . 자료구조 후 재도전(2022년 02월 15일)

 #이진탐색 알고리즘으로 해결.
 #bisect 모듈을 활용하여 숫자를 정렬 후 같은 데이터숫자를 쉽게 구할 수 있다.
 from bisect import bisect_left, bisect_right
 
 N = int(input())
 my_card = list(map(int,input().split()))
 my_card.sort()
 
 M = int(input())
 card = list(map(int,input().split()))
 
 for i in card:
     print(bisect_right(my_card,i) - bisect_left(my_card,i),end=' ')

»input

 10
 6 3 2 10 10 10 -10 -10 7 3
 8
 10 9 -5 2 3 4 5 -10

»output

 3 0 0 1 2 0 0 2

🌝 Thinking

sys모듈을 사용하지 않더라도 충분히 시간 초과없이 통과가 가능했다.

라이브러리를 활용하여 엄청 편하게 구현이 가능 했다.


💡 깨달은 점.

  1. 라이브러리를 활용한 것 또한 좋은 실력이라고 생각한다. 하지만 그 함수의 작동 알고리즘 또한 알고는 있자!

    카드2문제를 풀때도 느꼈지만, 정말 알고리즘을 공부한 뒤로 대부분의 문제들이 쉽게 풀리는 듯 하다. (solved.ac 알고리즘 해당^^)

댓글남기기

참고