[백준] 10816. 숫자 카드 2

 

📌문제

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

 

🎖️난이도

 

✔️풀이

# sol1) dict(해시), 리스트내포, 삼항연산자 => 652ms

n = int(input())
cards = list(input().split())
m = int(input())
nums = list(input().split())

result = [0] * m
nCards_dict = {}
for card in cards:
    nCards_dict[card] = nCards_dict[card] + 1 if card in nCards_dict else 1

result = [nCards_dict[nums[i]] if nums[i] in nCards_dict else 0 for i in range(m)]

print(' '.join(map(str, result))) # str끼리만 join으로 결합 가능!

 

# sol2) 이분탐색 (bisect_left,bisect_right) => 1636ms

from sys import stdin
from bisect import bisect_left, bisect_right

n = int(stdin.readline())
cards = sorted(list(map(int, stdin.readline().split()))) # sort 안하면 오답! bisect idx 차이로 count 불가
cards_set = set(cards)
m = int(stdin.readline())
nums = list(map(int, stdin.readline().split()))

result = [0] * m
for i in range(m):
    if nums[i] in cards_set:
        result[i] = bisect_right(cards, nums[i]) - bisect_left(cards, nums[i])
            
print(' '.join(map(str, result)))

 

# sol3) 카운터 (collections - Counter) => 580ms!!

from collections import Counter

_ = input()
cards = list(input().split())
_ = input()
nums = list(input().split())

cards_counter = Counter(cards)
print(c)

print(' '.join(str(cards_counter[num]) if num in cards_counter else '0' for num in nums))

 

---

🌞참고

[리스트내포 + 삼항연산자]

리스트내포에서 for문과 if문을 함께 사용할 때,

• for문을 앞에, if~else문을 뒤에 => else문까지 사용 시 error! (if절까지만 가능)
• if~else문을 앞에, for문을 뒤에 => else문까지 사용 가능

# correct
result = [nCards_dict[nums[i]] if nums[i] in nCards_dict else 0 for i in range(m)]

   #error!
    result = [nCards_dict[nums[i]] for i in range(m) if nums[i] in nCards_dict else 0]
                                                                               ^
SyntaxError: invalid syntax

 

[list, tuple, dict, set의 시간복잡도]

iteration 등의 연산 시, 무조건 list, tuple보다 set, dict 쓰자!

 

1. list / tuple

• in / not in : O(N)
• pop(i) : O(N)
• popitem() : O(1)

2. dict

• in / not in : O(1)
• pop(i) : O(1)
• popitem() : O(1) (random)cf. collections의 Counter도 dict로 반환하므로, 검색 속도 빠름!

3. set

• in / not in : O(1)
• pop() : O(1) (random)

 

[index() 함수]

• 찾을 아이템의 인덱스를 찾아줌
• 찾을 범위 지정 가능(start, end)
  • 단, end + 1까지 해줘야 end에 해당하는 인덱스까지 포함해서 검색

test = [1,4,1]
print(test.index(1, 1, 3)) # list.index(find_num, start, end(+1)

2

[dict에서 특정 key가 있는지 탐색]

• in 만 써주면 value가 아닌 key들 중에서만 검색

a = {'name':'pey', 'phone':'0119993323', 'birth': '1118'}
print('name' in a)
print('pey' in a)

True
False

 

[bisect_left, bisect_right]

이진탐색(정렬 포함) 을 통해, 특정 아이템이 왼쪽 및 오른쪽에 삽입될 때 어느 위치에 들어갈지 index return

• 미리 정렬 후 사용 시, 특정 아이템의 count 구할 수 있음
  • 이진탐색이므로, 그냥 count()에 비해 시간복잡도 낮음!

from bisect import bisect_left, bisect_right
test = [1,2,3,3,3]
print(bisect_left(test, 3))
print(bisect_right(test, 3))

2
5

 

 

from bisect import bisect_left, bisect_right
test = [1,2,3,3,3,6]
print(bisect_left(test, -1))
print(bisect_right(test, -1))
print(bisect_right(test, 4))
print(bisect_left(test, 3))
print(bisect_right(test, 3))
print(test)

0
0
5
2
5
[1, 2, 3, 3, 3, 6]