[Python] Softeer 자동차 테스트 - 정렬

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

https://softeer.ai/practice/6247

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

 

문제 해결 과정

- 젠장,, 풀이보니까 엄청 쉬운데 시간복잡도를 계산하지 못 했다

- 소프티어는 항상 시간 복잡도를 고려해야한다..

 

- 처음 접근 풀이 : 3개를 뽑는 모든 경우(combinations 3) 을 구하고, 그것을 정렬해서 가운데 숫자의 개수를 저장하여 확인 -> 시간초과

- 올바른 풀이 : 입력 받은 자동자의 연료를 정렬하고, (해당 숫자 앞 개수) * (해당 숫자 뒤 개수) = 해당 숫자가 중앙값이 될 수 있는 경우

 

 

작성 코드

import sys
input = sys.stdin.readline

# 자동차 개수, 테스트 개수
n, q = map(int, input().split())

# 자동차 연료 정보(정렬)
car_info = list(map(int, input().split()))
car_info.sort()

# 각 자동차 별 중앙값 선정 횟수
dic = {}

# 해당 숫자가 중앙값이 될 수 있는 경우 = (내 앞 개수) * (내 뒤 개수)
for i, car in enumerate(car_info):
	dic[car] = i * (n - i - 1)
    
# q번의 테스트
for i in range(q):
	car = int(input())
    # 확인하고자하는 값이 존재하는지 확인
    if car in dic:
    	print(dic[car])
    else:
    	print(0)

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

 

---

REFERENCE

https://bu119.tistory.com/66