[BOJ] 10816 숫자카드 2

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

10816번: 숫자 카드 2

숫자를 세기만 하면 되는 문제인 줄 알았는데, 숫자의 범위가 꽤나 크고, 입력의 개수도 꽤 많았다.

 

잘한점:

 

1. 연산량이 많을 것 같아서 해시맵인 dict자료구조를 이용할 생각을 했음.

문제를 못 푼 요인:

1. 처음에는 count연산을 했는데, count를 하면 한 번 count할 때마다
O(N)의 시간 복잡도로 돌기 때문에, N 번 센다면 O(N^2)의 시간 복잡도를 가진다.

2. pop(0)과 pop()의 차이
pop(0)은 첫번째 원소를 빼내면서 다른 원소의 인덱스가 하나씩 줄어들기 때문에 O(N)의 시간복잡도를 가진다.

pop()은 마지막 원소를 빼내기 때문에, 다른 원소의 인덱스에 관여하지 않기 때문에 O(1)의 시간 복잡도를 가진다.

 

문제 코드 

import sys

N = int(sys.stdin.readline().rstrip())
lst1 = list(map(int, sys.stdin.readline().rstrip().split()))

M = int(sys.stdin.readline().rstrip())
lst2 = list(map(int, sys.stdin.readline().rstrip().split()))

set_lst1 = set(lst1)
dict_lst1 = {}

for i in set_lst1:
    dict_lst1[i] = lst1.count(i)

for i in lst2:
    if i not in dict_lst1:
        print(0, end=" ")
        continue
    print(dict_lst1[i], end=" ")

 

해결 코드

import sys

N = int(sys.stdin.readline().rstrip())
lst1 = list(map(int, sys.stdin.readline().rstrip().split()))

M = int(sys.stdin.readline().rstrip())
lst2 = list(map(int, sys.stdin.readline().rstrip().split()))


dict_lst1 = {}

for _ in range(len(lst1)):
    if len(lst1) >= 0:
        if lst1[-1] in dict_lst1.keys():
            dict_lst1[lst1.pop()] += 1
        else:
            dict_lst1[lst1.pop()] = 1

for i in lst2:
    if i in dict_lst1.keys():
        print(dict_lst1[i], end=' ')
    else:
        print(0, end=' ')

 

GoodBye 2023. 

백준에서 개최하는 goodbye2023 대회를 참가하려고 했으나, 신청을 받는다는 것을 몰라서 참가하지 못했다... 

나중에 문제 나오면 시간 재고 풀어라도 봐야지.. 솔브악에 배지 추가하려고 했는데, 몰라서 못 참가했다....

 

다음 대회는 꼭 참가해보도록 하자.. 

 

다들 2024년도 화이팅!!