문제 10816. 숫자 카드 2
1. 나의 코드와 발상 과정
(1) 제출 답안
from bisect import bisect_left, bisect_right
import sys
n = int(input())
num_list = list(map(int, sys.stdin.readline().split()))
m = int(input())
find_list = list(map(int, sys.stdin.readline().split()))
num_list.sort()
def count_by_range(array, left, right):
right_index = bisect_right(array, right)
left_index = bisect_left(array, left)
return right_index - left_index
for i in find_list:
print(count_by_range(num_list, i, i), end=" ")
시간 초과 답안을 내면서 선형시간을 사용하는 경우 시간 초과가 당연히 될 수 있다는 것을 느낀 후,
정렬 중 nlogN 시간을 가지는 이진탐색을 활용해야 된다는 생각을 할 수 있었다.
개념만 살짝 들었지 아직 문제는 풀어보지 않은 상황이었으므로,
고수의 코딩 (2)를 참고했다.
bisect_right, left가 어떤 것인지 알아보았는데,
A. 해당 값이 리스트에 있을 때
bisect_left - 해당 index 반환하는 것.
bisect_right - 해당 index+1 반환하는 것.
B. 해당 값이 리스트에 없을 때
bisect_left - 리스트 오름차순에 들어갈 index 반환하는 것.
bisect_right - 리스트 오름차순에 들어갈 index 반환하는 것.
이라는 결론을 알 수 있었다. bisect_left 또는 right(array, x)의 기본 파라미터를 가지고 있는데,
x가 찾고자 하는 원소라고 할 수 있다.
x가 처음 나오는 인덱스와 제일 마지막에 나오는 인덱스를 가지고 그 안에 가지고 있는 x라는 원소의 개수를 셀 수 있는 것이다.
(2) 시간 초과 답안
import sys
n = int(input())
num_list = list(map(int, sys.stdin.readline().split()))
m = int(input())
find_list = list(map(int, sys.stdin.readline().split()))
i = 0
for fi in find_list:
find_list[i] = num_list.count(fi)
i += 1
for i in find_list:
print(i, end=" ")
2. 고수님의 깔끔한 코딩
(1) 카운터 사용
from sys import stdin
from collections import Counter
n = stdin.readline()
n_number = stdin.readline().split()
n = stdin.readline()
m_number = stdin.readline().split()
c = Counter(n_number)
print(' '.join(f'{c[i]}'if i in c else '0' for i in m_number))
더 좋은 답안을 찾다가 이러한 답안이 나왔다.
collections의 Counter 클래스를 활용하는 것이다.
Counter(array)는 Array 속의 원소를 key로, 존재하는 개수를 value로 하는 딕셔너리로 변환해준다.
key가 중복되는 횟수를 세고 싶을 때, 이 클래스를 사용하면 유용하다.
그래서 print 단에서 join, if, for을 활용해 한줄로
m_number가 있으면 value를 출력하고, 아니면 0을 출력하라고 할 수 있는 간결한 코드가 나온 것이다.
(2) bisect 활용
from bisect import bisect_left, bisect_right
# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(array, left_value, right_value):
right_index = bisect_right(array, right_value)
left_index = bisect_left(array, left_value)
return right_index - left_index
n, x = map(int, input().split()) # 데이터의 개수 N, 찾고자 하는 값 x 입력 받기
array = list(map(int, input().split())) # 전체 데이터 입력 받기
# 값이 [x, x] 범위에 있는 데이터의 개수 계산
count = count_by_range(array, x, x)
# 값이 x인 원소가 존재하지 않는다면
if count == 0:
print(-1)
# 값이 x인 원소가 존재한다면
else:
print(count)
내가 한 방식과 같다.
3. 아쉬운 점
클래스, 메소드 등과 같은 객체 지향 프로그래밍에 대한 지식이 아직 부족한 것 같다.
알고리즘 자체를 공부하는 것도 중요하지만, 이에 상응하는 문법적 스킬이 있어야 구현이 가능하다고 생각된다.
열심히 공부하자..
문제 출처:
'Problem Solving' 카테고리의 다른 글
[Algorithm] 4. 그래프 탐색 알고리즘 (0) | 2022.04.27 |
---|---|
[Algorithm] 3. 구현 (0) | 2022.04.27 |
[백준] 1920 수 찾기 python 알고리즘 문제 (0) | 2022.04.25 |
[백준] 1978 소수 찾기 python 알고리즘 문제 (0) | 2022.04.25 |
[백준] 4949 균형잡힌 세상 python 알고리즘 문제 (0) | 2022.04.25 |
댓글