[Python]백준 BaekJoon.AC 10816 : 숫자 카드2(Counter, 이진탐색X)

 

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

10816번: 숫자 카드 2

 

 

 

다양한 방법을 시도했던 문제다...

이건 틀리고 이건 시간초과고, 떠오르는 방법을 다 적용해봤는데 이렇다 할 해결방법이 없었다.

분명 하라는대로, 이진탐색으로 풀었는데...

리스트로도 해보고 딕셔너리도 사용해보고.

처음엔 딕셔너리도 이진탐색엔 어울리지 않는 것 같아 리스트로만 해보다, 다들 딕셔너리를 당연하듯 쓰길래.

그리고 이진탐색 아닌 방법으로도 해봐도 안되길래!!

 

 

 

시간에 대해 알아보기 했다..

정렬은 반드시 필요하다고 가정했고, 가장 빠르게 정렬할 수 있는 건 set과 dictionary.

가지고 있는 카드도 언젠간 세어야했다.

앞서 count 함수를 썼다가 시간초과로 좌절했기에, 다른 방법을 찾아야 했다.

그러다 Counter를 떠올린 거다.

 

 

NL = map(int, sys.stdin.readline().split())
nums = Counter(NL)
print(nums)

#6 3 2 10 10 10 -10 -10 7 3 입력하고
#print(nums) 명령한다면
#Counter({10: 3, 3: 2, -10: 2, 6: 1, 2: 1, 7: 1}) 가 출력된다.

 

 

「Counter는 주어진 리스트를 탐색하며 리스트 요소들의 개수를 세어 딕셔너리로 정리해준다.

나에게 딱 맞는 조건이었다. 심지어 소요시간이 O(N)...

 

딕셔너리는 원소접근시 O(1)의 시간만 필요하기에, 작업을 모두 완료해도 리스트를 한번 훑는 것과 같은 O(N)의 시간복잡도를 갖는다.

counter만 하더라도 O(N제곱)이 필요한데... 괜찮은 방법이겠다 싶었다.」

 

 

 

생각해보니 굳이 이진탐색이 필요하지 않게 됐다.

get 함수로 값만 부르면 되니까. 심지어 시간도 별로 안걸린다. 이것도 O(1)...

아, 그리고 일부러 get을 사용해줬다. in을 사용할까 했는데, in은 O(N)의 시간이 소요되더라.

get 함수가 더 적합하다고 생각했다.

그래도 이진탐색을 사용해주고 싶었는데, 무척 아쉬웠다...^^

 

모범답안에 너무 국한되는 것도 좋지 않으니까..ㅎ 다른 사람들 코드를 읽고 분석하는 것으로 대신하기로 했다.

그리고 다음부턴 함수를 사용해보도록 해야겠다.

 

 

 

import sys
from collections import Counter

N = int(input())
NL = map(int, sys.stdin.readline().split())
M = int(input())
ML = map(int, sys.stdin.readline().split())

nums = Counter(NL)

for nn in ML:
    if nums.get(nn) != None:
        print(nums[nn], end=" ")
    else:
        print(0, end=" ")

 

 

위 방법은 NL 리스트 각 요소의 개수를 세어 nums 딕셔너리에 넣어주고, ML 각각의 요소를 확인해주는 방법이다.

 

 

다른 한 가지 방법을 올리자면

 

 

import sys

N = int(input())
NL = list(map(int, sys.stdin.readline().split()))
NL.sort()

M = int(input())
ML = list(map(int, sys.stdin.readline().split()))

dic = {}

for n in NL:
    if n in dic:
        dic[n] = dic[n] + 1
    else:
        dic[n] = 1

for m in range(M):
    if ML[m] in dic:
        print(dic[ML[m]], end=' ')
    else:
        print(0, end=' ')

 

 

위 방법은 가지고 있는 카드의 개수를 직접 세어 딕셔너리에 카운트해주고,

조건 카드마다 딕셔너리에 존재하는지 확인 후 저장한 개수를 불러오는 방식이다.

 

 

이렇게 짧고 간결한데... 내가 지금껏 짠 코드가 무색해졌다. 다음부턴 여러 방법들을 모색해봐야지.

 

 

 

<틀린코드>

import sys

N = int(input())
nums = {}

for n in map(int, sys.stdin.readline().split()):
    if n in nums:
        nums[n] = nums[n] + 1
    else:
        nums[n] = 1

nums = sorted(nums.items())

M = int(input())
for nn in map(int, sys.stdin.readline().split()):
    sta = 0
    fin = len(nums) - 1
    target = len(nums) // 2
    while True:
        target = (sta + fin) // 2
        if nums[target][0] == nn:
            print(nums[target][1], end=" ")
            break
        elif nums[target][0] < nn:
            sta = target + 1
        elif nums[target][0] > nn:
            fin = target - 1

        if sta > fin:
            print(0, end=" ")
            break

 

import sys

N = int(input())
nums = list(map(int, sys.stdin.readline().split()))
nums.sort()

M = int(input())


for n in map(int, sys.stdin.readline().split()):
    sta = 0
    fin = N-1
    target = N // 2
    count = 0
    keep = True
    while keep:
        target = (sta+fin) // 2
        if nums[target] == n:
            count = count + 1
            temp = target
            while True:
                if temp != 0 and temp != N-1:
                    temp = temp + 1
                    if nums[temp] == n:
                        count = count + 1
                        continue
                keep = False
                break
            temp = target
            while True:
                if temp != 0 and temp != N-1:
                    temp = temp - 1
                    if nums[temp] == n:
                        count = count + 1
                        continue
                keep = False
                break

        elif nums[target] < n:
            sta = target + 1
        elif nums[target] > n:
            fin = target - 1

        if sta > fin:
            keep = False

    print(count, end=" ")

이외에도 많다!!ㅋㅋ 다 시간초과였던 듯..?

나중에 시간이 되면 이 코드들을 바탕으로 수정·보완 해보기로 했다.

 

 

 

+)

 

 

이진탐색으로 구현해봤지만 시간은 더 걸린다. 4배 넘게..

그래도 정답처리 됐고, 의의를 둔다!

import sys

N = int(input())
NL = list(map(int, sys.stdin.readline().split()))
NL.sort()
nums = {}

for n in NL:
    if n not in nums:
        nums[n] = 1
    else:
        nums[n] = nums[n] + 1

M = int(input())
ML = map(int, sys.stdin.readline().split())

for nn in ML:
    sta = 0
    fin = N-1

    while sta <= fin:
        mid = (sta+fin) // 2
        if NL[mid] == nn:
            print(nums[nn], end=" ")
            break
        elif NL[mid] < nn:
            sta = mid + 1
        elif NL[mid] > nn:
            fin = mid - 1

    if sta > fin:
        print(0, end=" ")