문제 링크
https://www.acmicpc.net/problem/10816
풀이 전 계획과 생각
이 문제는 대략적으로 이렇게 구성되어 있다.
- 우선 첫번째 입력 세트에서 입력할 정수의 개수와 그 수만큼의 정수들을 입력한다.
5
1 4 3 2 1
이런 식으로. - 두 번째 입력 세트에서 다시 입력할 정수의 개수와 그 수만큼의 정수들을 입력한다.
6
1 2 3 4 5 6
이런 식으로. - 마지막으로 두 번째 세트의 정수값들이 위의 첫 번째 세트에 몇 개씩 있는지 출력한다.
예를 들어 1은 위에 2개 있고, 2는 1개, 3은 1개, 4는 1개, 5는 0개, 6은 0개 있으니까
2 1 1 1 0 0
이렇게 출력하는 것이다.
이것을 일반적인 배열과 반복문으로 했더니 당연하게도(...) 시간 초과가 떴다.
어떻게 해야 하는지 알아보니 이 문제의 분류명은 '이진 탐색(binary search)'이었는데, 이진 탐색은 정렬된 배열에서 찾으려는 값보다 확인한 값이 작으면 앞부분은 버리고 나머지 뒷부분(더 큰 값들의 배열)만 찾는 방식으로 절반씩을 계속 버리는 방법 아닌가? 특정 값이 여러 개 있고 그게 몇 개인지 다 찾으려면 버리지 못하는 거 아냐? -_-+
솔직히 '여러 개 있을 수 있는 값을 다 세어 보는 데 이진탐색을 사용하는 방법'을 이번 주 안에 공부해서 스스로 이해할 자신이 없었다. 아마 결국은 남이 쓴 문제풀이를 그냥 보고 따라하는 걸로 끝날 것 같은데 그게 무슨 소용인가 싶었기 때문에 이진탐색으로 푸는 건 다음에 해보기로 했다.
검색을 해보니 배열로 하는 것보다 조금 더 시간복잡도가 줄어드는 방법으로는 딕셔너리와 카운터가 있다고 해서 일단 그걸로 해보기로 했다.
즉 첫번째 세트에서 입력된 값들이 몇 개씩 있는지 항목별로 저장한 딕셔너리나 카운터를 만들어 놓고 두번째 세트의 값들에 대해서는 일일이 처음부터 세어보지 않고 앞의 딕셔너리나 카운터에 있는 값을 그대로 출력하면 된다는 것이었다.
참고자료(이해는 안 됐다 ㅠㅠ)
이진탐색으로 풀기 https://chancoding.tistory.com/45
내장함수 sort 사용법 https://inma.tistory.com/137
딕셔너리/카운터 활용 힌트
https://edelweiss-ever.tistory.com/86
한 줄 for문 정리
https://leedakyeong.tistory.com/entry/python-for%EB%AC%B8-if%EB%AC%B8-%ED%95%9C-%EC%A4%84%EB%A1%9C-%EC%BD%94%EB%94%A9%ED%95%98%EA%B8%B0
풀이 (코드 블록 첨부)
from collections import Counter
import sys
#import math
counter1=int(input(""))
table1=[]
table1=Counter(list(map(int,sys.stdin.readline().split())))
counter2=int(input(""))
table2=[]
table2=list(map(int,sys.stdin.readline().split()))
print(" ".join(str(table1[unit]) if unit in table1 else "0" for unit in table2 ))
#for unit in table2:
# if unit in table1:
# print(table1[unit],end=" ")
# else:
# print(0,end=" ")풀이하면서 막혔던 점과 고민
물론 저걸 이진 탐색으로 어떻게 푼다는 것인지 여러 설명들을 보아도 아직 이해가 안 간다는 점이 가장 답답했다. 다음에 더 쉬운 문제들부터 풀어봐야지. ㅋㅋㅋ
풀이 후 알게된 개념과 소감
카운터와 딕셔너리로 값을 세어보는 건 예전에 딥러닝 기초 독학할 때에도 봐뒀었는데 다 잊어버리고 있다가 다시 공부해서 보람이 있었다.
위는 고전적인 반복문, 아래는 '한 줄 for문'으로 제출한 결과. 생각보다 시간이 많이 차이가 나니까 앞으로도 한 줄 for문을 많이 이용해서 숙달해야겠다.
