Baekjoon 문제 풀기 (10816번 : 숫자 카드 2) Python

10816번 : 숫자 카드 2

1. 문제읽기

---

count 하는 문제

입력되는 카드 하나씩 몇개를 가지고 있는지 출력하면 된다.
아무것도 가지고 있지 않다면 0을 출력한다.

2. 제출 코드

---

처음에는 count함수를 썼었는데, 시간초과로 실패했다.
입력값이 엄청나게 많았기 때문에 이진탐색을 쓰는 건가 싶었지만 Counter 클래스를 사용하면 쉬울 것 같아서 사용해보았는데 다행히 정답이었다.

처음 시간초과 코드

n = int(input())
arr = list(map(int, input().split()))
m = int(input())
tgt_arr = list(map(int, input().split()))

for i in tgt_arr:
    print(arr.count(i), end=' ')

Counter 클래스 사용

for문에서 O(n), if문에서 O(n)인줄 알았는데, dic에서 in을 사용하면 시간복잡도는 O(1)이다.
그래서 시간초과가 나지 않은 것 같다.
근데 내가 사용한 if i in cnt_dict.keys()는 좋은 코드는 아니다.
애초에 dictionary에서의 in은 key에 한해서 동작하기 때문에 .keys()를 붙일 필요가 없다.
.keys()는 리스트 혹은 제네레이터를 반환하기 때문에 시간복잡도만 늘이는 꼴이 됐다.

Counter클래스에 리스트를 담으면 각 요소를 count해서 해쉬 형태를 가진다.
입력 리스트를 for문을 돌려서 dic 안에 요소가 있다면 value값을 출력하고, 없다면 0을 출력한다.

from collections import Counter

n = int(input())
arr = list(map(int, input().split()))
m = int(input())
tgt_arr = list(map(int, input().split()))

cnt_dict = Counter(arr)

for i in tgt_arr:
    if i in cnt_dict.keys():  # .keys() 는 없애야 함.
        print(cnt_dict[i], end=' ')
    else:
        print(0, end=' ')

3. 공부할 것

---

다른 코드를 보니 이진탐색의 발전된 버전을 사용해야 시간초과가 나지 않는다고 한다.
즉, 같은 값이 여러개 있을 경우에 lower bound와 upper bound의 개념을 이용하여 같은 값의 인덱스가 몇부터 몇인지를 알아내는 것이다.

• Lower bound : 타겟 이상의 값이 처음으로 나오는 인덱스 값을 반환
• Upper bound : 타겟보다 큰 값이 처음으로 나오는 인덱스 값을 반환
• upper bound - lower bound : 타겟과 동일한 숫자의 개수

기존 이진탐색이랑은 다른점이 많다.

1. while start < end:
2. end = len(arr)
3. target < arr[mid]일 경우
4. target > arr[mid]일 경우
5. target = arr[mid]일 경우

1번은 start 와 end 가 같을 경우 정답이 된다.
2번은 len(arr)-1을 해주면 답이 없는 경우에 0을 만들어주기 위해서이다.
3번은 왼쪽 부분을 다시 탐색해야하기 때문에 end를 줄여주지만, mid값도 정답이 될 수 있으므로 범위에 mid를 포함시켜주기 위해 end=mid 를 해준다.
4번은 오른쪽 부분을 다시 탐색해야하기 때문에 start를 늘려주는데 mid값은 정답일 수 없기 때문에 +1을 해줘서 mid를 제외한다.
5번이 생각을 많이 해야하는 부분이다.
lower와 upper의 경우가 다르다.
lower일 때는 mid도 답이 될 수 있기 때문에 3번과 같이 동작해야 하지만, upper일 때는 mid가 답이 될 수 없기 때문에 4번과 같이 동작해야한다.

몇시간에 걸쳐서 이해하고 이 방식으로 문제를 풀긴 했는데, Counter 클래스를 쓴 코드보다 시간이 훨씬 오래 걸렸다..
그래도 나중에 써먹을 일이 있겠지!

n = int(input())
arr = list(map(int, input().split()))

m = int(input())
tgt_arr = list(map(int, input().split()))

arr.sort()
def lowerBound(target):
    start = 0
    end = len(arr)
    while start < end:  
        mid = (start+end)//2
        if target <= arr[mid]:
            end = mid
        else:
            start = mid+1
    return end


def upperBound(target):
    start = 0
    end = len(arr)
    while start < end:
        mid = (start+end)//2
        if target < arr[mid]:
            end = mid
        else:
            start = mid+1
    return end


for i in tgt_arr:
    print(upperBound(i)-lowerBound(i), end=' ')