[코테/백준] Python 숫자 카드 2 - 10816번

실패 | 시도 -번

 

🔗 [백준] 10816번 : 숫자 카드 2

 10816 : [이진 탐색] 숫자카드 2 (py)

---

문제 

---

내 소스

n = int(input())
n_lst = list(map(int, input().split()))
m = int(input())
m_lst = list(map(int, input().split()))

dic = {}

for i in n_lst:
    if i not in dic:
        dic[i] = 1
    else:
        dic[i] += 1
        
for i in m_lst:
  if i in dic:
    print(dic[i], end=' ')
  else:
    print(0, end=' ')

 

소스 설명

for i in n_lst:
    if i not in dic:
        dic[i] = 1
    else:
        dic[i] += 1

[8 - 12] : dic에 i가 없으면 i를 키로 두고 1로 값을 설정한다. 반면에 dic에 키(i)가 있는 경우 1을 더해서 저장한다. 

→ dic는 각 숫자카드가 몇 장씩 있는지를 저장한다.

 

for i in m_lst:
  if i in dic:
    print(dic[i], end=' ')
  else:
    print(0, end=' ')

[14 - 18] : m_lst에 있는 숫자카드가 dic에 있는지 확인한다. 있으면 값을 출력하고 없으면 0을 출력한다.

---

다른 코드 분석

bisect 모듈 사용하기

🔗 bisect 모듈

from bisect import bisect_left, bisect_right

n = int(input())
n_lst = list(map(int, input().split()))
m = int(input())
m_lst = list(map(int, input().split()))
n_lst.sort()

for i in m_lst:
    result = bisect_right(n_lst, i) - bisect_left(n_lst, i)
    print(result, end=' ')

• bisect_left()와 bisect_right()는 리스트의 어느 인덱스에 값을 넣을지 알려주는데 이를 통해 그 값이 몇 개인지 유추할 수 있다.

 

Counter 모듈 이용하기

from collections import Counter

n = int(input())
n_lst = list(map(int, input().split()))
m = int(input())
m_lst = list(map(int, input().split()))
n_lst.sort()

counter = Counter(n_lst)
for i in m_lst:
    if i in counter:
        print(counter[i], end=' ')
    else:
        print(0, end=' ')

---

회고

• 해당 문제가 이진 탐색으로 분류되어 있어 최대한 이진 탐색으로 풀려고 노력했다. 그런데 무슨 문제인지 예제 케이스는 잘 통과되는데 계속 '틀렸습니다' 문구를 찍다가 제쳐두기로 했다...

계속 오류 나는 코드 ↓↓↓

- 혹시 원인을 아시는 분은 댓글 달아주세요 😥

import sys

def binary_search(arr, target):
    start = 0
    end = len(arr)-1
    count = 0
    while start <= end:
        mid = (start+end)//2
        if arr[mid] > target:
            end = mid - 1
        elif arr[mid] == target:
            count+= 1
            del arr[mid]
            end = len(arr)-1
        else:
            start = mid+1
    return count

n = int(sys.stdin.readline())
n_lst = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
m_lst = list(map(int, sys.stdin.readline().split()))

n_lst.sort()
for i in m_lst:
    print(binary_search(n_lst, i), end=' ')

 

 

---

Ref. 

1. 문제 풀이 / https://hongcoding.tistory.com/12

2. 문제 풀이 / https://aigong.tistory.com/396

3. 문제 풀이 / https://velog.io/@ledcost/%EB%B0%B1%EC%A4%80-10816-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%88%AB%EC%9E%90-%EC%B9%B4%EB%93%9C-2-%EC%8B%A4%EB%B2%844-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89

4. 이진 탐색 / https://programming119.tistory.com/196

---

* 잘못된 부분에 대해 댓글 남겨주시면 감사하겠습니다! 😀