[백준] 10816 숫자 카드 2 python 알고리즘 문제

문제 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. 아쉬운 점

클래스, 메소드 등과 같은 객체 지향 프로그래밍에 대한 지식이 아직 부족한 것 같다.

알고리즘 자체를 공부하는 것도 중요하지만, 이에 상응하는 문법적 스킬이 있어야 구현이 가능하다고 생각된다.

열심히 공부하자..

 

 

 

 

문제 출처:

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