[Softeer / Level3][HSAT 7회 정기 코딩 인증평가 기출] 자동차 테스트

https://softeer.ai/practice/info.do?idx=1&eid=1717 

Softeer

---

문제를 보고 itertools 에서 만들 수 있는 가능한 경우의 수를 만든다음, 중앙값을 찾는식으로 진행했었다. (시간초과 엔딩..)

다른 방법이 도저히 떠오르지 않아 해설을 참고했다. 해설에서의 문제해결전략은 3가지였다.

1. 정렬된 리스트에서 피벗을 잡고, 피벗 기준으로 앞의 숫자 갯수와 뒤의 숫자 갯수를 곱해주어서 가능한 경우의 수를 구하기
2. 리스트는 중복이 허용되기 때문에 O(n)의 찾는 시간이 걸림, 따라서 set 으로 정리해서 피벗을 찾아주기
3. 피벗을 찾기위해 bisect(내장함수) 를 사용하기

참고로, bisect_left(array, value) 는 array의 가장 왼쪽 value 의 index, bisect_right(array, value)는 가장 오른쪽 value의 index를 찾는다. 주로 이미 sorted 되어있는 array에서 자주 쓰인다.

 

<내 코드 / 시간초과>

import sys
from itertools import combinations

n, q = map(int, sys.stdin.readline().split())
S = list(map(int, sys.stdin.readline().split()))
K = []

S.sort()
for i in combinations(S, 3):
    K.append(i[1])

for j in range(q):
    print(K.count(int(sys.stdin.readline())))

 

<정답 코드>

import sys
import bisect

n, q = map(int, sys.stdin.readline().split())
S = list(map(int, sys.stdin.readline().split()))
S.sort()
SetS = set(S)
for _ in range(q):
    m = int(input())
    if m not in SetS: # 있는지 없는지 체크하기 위해 리스트 전체를 뒤져봐야 함 1. set을 이용하기 2. 처음에 이진탐색으로 인덱싱하기        
        print(0)
    else:
        idx = bisect.bisect_left(S, m)
        print(idx * (n-idx-1)) # (작은쪽갯수 * 큰쪽갯수)

처음 받아온 m 값을 이진탐색으로 찾아서 출력하는 방법도 있다.

 

 

https://talentwilshowitself.tistory.com/entry/Python-bisect-%ED%99%9C%EC%9A%A9-%EC%98%88%EC%8B%9C

[Python] bisect 활용 예시