[CodingTest] 백준 #10816 숫자 카드 2

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

10816번: 숫자 카드 2

 

내 풀이

import sys
n=int(sys.stdin.readline())
arr_n = list(map(int,sys.stdin.readline().split()))
m=int(sys.stdin.readline())

#이 알고리즘은 arr_n을 차례로 순회하여 arr_m에 있는지 체크하는 알고리즘이다.

#출력 시 처음 인덱스들의 순서 알기 위해 tmp로 받고
tmp = list(map(int,sys.stdin.readline().split()))
#효율적인 이진 탐색을 위해 중복 제거, 정렬한다
arr_m = sorted(set(tmp))

dic = {arr_m[i]:0 for i in range(len(arr_m))}


for i in range(n):
    left = 0
    right = len(arr_m)-1
    #right가 left보다 큰 동안
    while left<=right:
        #중앙값을 구한다
        mid = (left+right)//2
        #arr_m의 중앙값과 arr_n의 i번째 수가 같다면
        if arr_m[mid]==arr_n[i]:
            #딕셔너리의 해당 키의 값을 1 더하고 break한다
            dic[arr_m[mid]]+=1
            break
        #중앙값이 더 크다면 right를 mid-1로 조정 
        elif arr_m[mid]>arr_n[i]:
            right = mid-1
        #중앙값보다 arr_n[i]값이 더 크다면 left를 mid+1로 조정
        else:
            left = mid+1
#처음 들어온 값 [10 0 -5 2 3 4 5 -10]의 순서에 따라 dic에서 출력 
for i in range(m):
    if i!=m-1:
        print(dic[tmp[i]],end=' ')
    else:
        print(dic[tmp[i]])

 

이 문제는 이분 탐색 연관 문제였다. 그래서 이분 탐색으로 풀어보고 싶었는데 시간초과가 떴다 ㅠ 

나는 arr_m을 순화하며 arr_n에 있다면 count하는 다른 분들과 다르게 arr_n을 순회하며 arr_m에 해당 카드가 있는지 확인하고 arr_m에 이분법을(mid) 적용했다.

하지만 이 방법은 python3에서는 시간 초과가 발생했다.

 

 

주석이 있지만 간략하게 예시로 설명을 해보자면, 아래와 같이 입력되었을 떄,

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

 

n = 10, arr_n = [6, 3, 10, 10, 10, -10, -10, 7, 3]

m = 8,  arr_m = [10, 9, -5, 2 3 4 5 -10] 이고, 

arr_m을 중복 제거 정렬한다. (위 예시에서는 중복이 없지만, 10, 10, 9 ... 등과 같이 입력받아지는 경우도 있으므로 이러한 경우를 생각한다.)

따라서 arr_m은 [ -10, -5, 2, 3, 4, 5, 9, 10 ] 이 된다.

 

초기 dic은 { -10 : 0, -5 : 0, 2 : 0, 3 : 0, 4 : 0, 4 : 0, 9 : 0, 10 : 0 }이다.

초기 left = 0, right = 7이다.

 

left가 right보다 작으므로 while문에 들어간다. 

mid는 (0+7)//2 = 3이다.

i는 0이므로, arr_n[0]과 arr_m[mid]의 비교는 6과 3의 비교이다. 

arr_n[0]이 더 크므로, left는 mid+1 즉 4가된다.

 

아직 left가 right보다 작으므로 while문을 계속 돌 수 있다.

위와 같은 방법으로 계속하면 mid는 (4+7)//2 = 5이다.

i는 아직 0이므로 6과 arr_m[mid], 즉 5를 다시 비교하면 6이 5보다 크므로 right는 mid-1 = 4가 된다. 

그러면 left는 4, right는 4이므로 while문 조건을 충족하여 다시 돌 수 있다.

 

이번엔 mid가 (4+4)//2 =4이므로 arr_m[4]와 6을 비교하면, 4와 6의 비교이므로 left는 mid +1 = 5가 된다.

이제 left의 값이 right보다 크므로 while 문을 빠져 나온다.

i는 1이 되고 위와같은 과정을 반복하여, 만약 값이 있다면 break 해주고 딕셔너리에서 해당 키의 값을 +1 해준다.

 

마지막으로, 출력 시에는 정렬 이전의 즉, 10, 9, -5, 2, 3, 4, 5, -10의 순서에 맞는 갯수가 출력이 되어야 한다.

따라서 dic[tmp[i]]는 i가 1일 때, dic[10]을 출력하는 것이므로 이러한 방법을 사용하여 출력한다.

 

이제 다른 사람들의 코드를 살펴보자. (내 코드의 주석 없는 클린 버전도 아래에서 확인 가능!)

---

다른 사람 코드 1 - 딕셔너리와 in 사용(1등 풀이)

from sys import stdin
_ = int(input())
n = [int(i) for i in stdin.readline().split()]
_ = int(input())
m = [int(i) for i in stdin.readline().split()]

hashmap = {}
for i in n:
    if i in hashmap:
        hashmap[i] += 1
    else:
        hashmap[i] = 1

print(' '.join(str(hashmap[i]) if i in hashmap else '0' for i in m))

이 풀이방법은 이진탐색 풀이는 아니다.

n의 원소를 순회하며 딕셔너리에 있다면 +1을 해주고, 없다면 1로 세팅한다. 

m을 순회하며 딕셔너리에 키로 하는 값이 있다면 해당 값을 출력하고, 딕셔너리에 없다면 0을 출력한다.

---

다른 사람 코드 2 - bisect 내장 모듈

from bisect import bisect_left, bisect_right
from sys import stdin

n = stdin.readline().rstrip()
card = list(map(int,stdin.readline().split()))
m = stdin.readline().rstrip()
test = list(map(int,stdin.readline().split()))
card.sort()

def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index


for i in range(len(test)):
    print(count_by_range(card, test[i], test[i]), end=' ')

bisect는 파이썬에 내장된 이진탐색 모듈인데, bisect_left(list,value)는 list에서 value가 들어갈 가장 왼쪽 인덱스를, bisect_right(list,value)는 list에서 value가 들어갈 가장 오른쪽 인덱스를 알려준다고 한다.

위 풀이는 count_by_range 함수를 만들어 left_value와 right_value에 같은 값을 넣어주고, bisect_left, bisect_right를 하여 left_index와 right_index에 값을 넣어주었다. 

right_index - left_index는 숫자의 갯수가 되므로 해당 값을 출력하는 프로그램이다. 

이 풀이방법에서 card는 arr_n이고 test는 arr_m인데, card를 오름차순 정렬하고, 나와 반대로 arr_m을 순회하면서 arr_n에 대해 이분탐색을 하는 경우이다. 

---

다른 사람 풀이 3 - Counter 내장 모듈 이용

from collections import Counter
from sys import stdin

n = stdin.readline().rstrip()
card = list(map(int,stdin.readline().split()))
m = stdin.readline().rstrip()
test = list(map(int,stdin.readline().split()))

count = Counter(card)

for i in range(len(test)):
    if test[i] in count:
        print(count[test[i]], end=' ')
    else:
        print(0, end=' ')

리스트에 대해 Counter 함수를 사용하면, 해당 원소가 몇 번 등장했는지 세어 딕셔너리로 반환한다고 한다.

arr_n, 즉 card에 대해 Counter를 하여 딕셔너리를 만들고, arr_m 즉 test를 순회하며 해당 원소가 딕셔너리에 있다면 그 값을 출력하고, 없다면 0을  출력하는 방법이다.

 

---

이렇게 다른 사람들의 코드까지 모두 살펴보았는데 bisect와 Counter 모듈을 새롭게 알게 되었다.

앞으로 다른 이진 탐색 문제에서 bisect를 활용해봐야 겠다.

---

마지막으로 주석없는 클린 버전!

import sys
n=int(sys.stdin.readline())
arr_n = list(map(int,sys.stdin.readline().split()))
m=int(sys.stdin.readline())
tmp = list(map(int,sys.stdin.readline().split()))
arr_m = sorted(set(tmp))
dic = {arr_m[i]:0 for i in range(len(arr_m))}

for i in range(n):
    left = 0
    right = len(arr_m)-1
    while left<=right:
        mid = (left+right)//2
        if arr_m[mid]==arr_n[i]:
            dic[arr_m[mid]]+=1
            break
        elif arr_m[mid]>arr_n[i]:
            right = mid-1
        else:
            left = mid+1
            
for i in range(m):
    if i!=m-1:
        print(dic[tmp[i]],end=' ')
    else:
        print(dic[tmp[i]])

 

---

출처 : https://hongcoding.tistory.com/12