[정렬/탐색] 백준 10816 숫자 카드 2 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

10816번: 숫자 카드 2

 

 

 

2. 문제 풀이

 숫자카드 N개 중에 정수 M개를 찾는 문제입니다. 

 

2022.02.10 - [Algorithm] - [정렬/탐색] 백준 1920 수 찾기 - Python

[정렬/탐색] 백준 1920 수 찾기 - Python

 위 문제와 매우 비슷하지만, 이 문제는 '중복'이 있습니다. 단순히 이진탐색만 해서는 풀 수 없고, 찾는 수가 몇 개나 있는지도 구해야 합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

N = int(input())
numlist = list(map(int, input().split()))
M = int(input())
findlist = list(map(int, input().split()))

#이진 탐색(자료, 찾는 값)
def binarySearch(lst, x):
    start = 0
    end = len(lst)-1

    while start <= end:
        mid = (start + end)//2 # 중앙위치
        if x == lst[mid]: # 중앙값이 찾는 값
            cnt = 1 # 찾은 개수

            left = 1 # 왼쪽에 동일한 값 찾기
            while mid-left >= 0 and x == lst[mid-left]:
                cnt += 1
                left += 1

            right = 1 # 오른쪽에 동일한 값 찾기
            while mid + right < len(lst) and x == lst[mid + right]:
                cnt += 1
                right += 1
            return cnt

        elif x > lst[mid]: # 중앙값보다 큰 경우
            start = mid + 1
        else:
            end = mid - 1 # 중앙값보다 작은 경우
    return 0 # 찾지 못한 경우

# 정렬
numlist.sort()
for i in findlist:
    print(binarySearch(numlist, i), end=" ")

 맨 처음에는 이진탐색으로 찾고, 찾은 값의 양 옆을 탐색해서 개수를 구했습니다. 구현은 됐지만, 22%대에서 시간초과가 났습니다. . .

 

화란아, 나도 순정이 있다. 니가 이런식으로 내 순정을 짓밟으면은 마 그때는 깡패가 되는거야!

 이러쿵 저러쿵하다가 결국 파이썬 라이브러리로 풀었습니다. 왠만하면 파이썬 라이브러리를 안 쓰려고 했지만, 잘 만들어진 라이브러리들을 안 쓸 이유도 없죠. 내장 라이브러리가 잘 되어있는 게 파이썬의 장점이니까요.

(라이브러리 못 쓰는 코딩테스트는....)

 

import sys
from collections import Counter
input = sys.stdin.readline

N = int(input())
numlist = list(map(int, input().split()))
M = int(input())
findlist = list(map(int, input().split()))

count = Counter(numlist)
for i in range(len(findlist)):
    print(count[findlist[i]], end=' ')

 counter 라이브러리는 dictionary 구조로 리스트 내 원소의 개수를 세어줍니다.

 

from collections import Counter
count = Counter(numlist)
count[num]

 다음과 같이 counter 객체를 만들어서 사용하며, count[num]을 하면 num이 numlist에 몇 개가 있는지 반환해줍니다.