[소프티어] [인증평가(7회) 기출] 자동차 테스트 (파이썬)

난이도 : ★★★☆☆

 

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

Softeer

 

📄 문제

• 자동차 제조 과정에서는 다양한 테스트를 통해 해당 자동차가 잘 만들어졌는지를 평가합니다.
• 자동차의 연비가 높을수록 연료 소비가 적고, 더 많은 거리를 주행할 수 있으므로 이는 자동차가 잘 만들어졌는지의 지표로 사용될 수 있습니다.
• 만약 3대의 자동차를 테스트하고, 각각의 연비를 측정한다고 가정해봅시다.
  • 첫 번째 자동차의 연비는 9km/L,
  • 두 번째 자동차의 연비는 15km/L,
  • 세 번째 자동차의 연비는 20km/L이라고 합시다.
  • 이 경우, 중앙값은 15km/L이 됩니다.

• 따라서 이 데이터에서는 중앙값을 이용하여 자동차의 평균적인 연비를 파악할 수 있으며,
• 이는 자동차 제조 과정에서 테스트의 결과를 평가하는 데 활용될 수 있습니다.
• n대의 자동차를 새로 만들었지만 여건상 3대의 자동차에 대해서만 테스트가 가능한 상황입니다.
• 주어지는 자동차의 연비는 서로 다름을 가정해도 좋습니다.

 

n대의 자동차의 실제 연비 값이 주어졌을 때, q개의 질의에 대해 임의로 3대의 자동차를 골라 테스트하여 중앙값이 mi값이 나오는 서로 다른 경우의 수를 구하는 프로그램을 작성해 보세요.

 

---

💡 아이디어

• 3대의 자동차를 골라 연비의 중앙값을 선택하는 것이므로 mi 보다 크고 작은 연비가 각각 1개 이상 존재하면 mi는 중앙값이 될 수 있다.
• 중앙값이 mi가 나오는 서로 다른 경우의 수를 구하는 방법은
  • 뽑는 수 3개 중에 중앙값 mi는 미리 뽑아둔다.
  • mi를 제외한 나머지 값 중 mi보다 작은 값 중에서 1개를 뽑고 mi보다 큰 값 중에서 1개를 뽑으면 된다.
  • mi보다 작은 연비들 중에서 1개를 뽑는 경우의 수 X mi보다 큰 연비들 중에서 1개를 뽑는 경우의 수
• 중앙값보다 크고 작은 연비의 경우의 수를 구하기 위해서는 중앙값 보다 크고 작은 연비의 개수를 파악해야 한다.
• 연비들을 오름차순으로 정렬했을 때, 중앙값이 몇 번째에 위치하는지 알면 중앙값보다 크고 작은 연비의 개수를 파악하기 쉽다.
  • 연비들을 오름차순으로 정렬하면, 각 연비의 인덱스로 해당 연비보다 크고 작은 연비의 개수를 알 수 있다.
• 즉, 오름차순으로 정렬하여, 중앙값 mi의 왼쪽에 위치하는 연비의 개수(작은 연비들)와 오른쪽에 위치하는 연비의 개수(큰 연비들)를 구하면 된다.
• 중앙값 mi의 인덱스가 i라 가정하면
  
  • 인덱스는 0부터 시작하므로 중앙값 mi 보다 작은 연비의 개수는 i개가 된다.
  • 중앙값 mi 보다 큰 연비의 개수는 (전체 개수 - 1 - i) 개가 된다. (전체개수에서 중앙값과 중앙값보다 작은 값 제외)
  • 따라서, 중앙값이 mi가 나오는 서로 다른 경우의 수는 i X (전체 개수 -1 - i) 개다.
• 위에서 구한 각 연비에 해당하는 중앙값이 될 수 있는 경우의 수를 {연비 : 경우의 수}의 형태로 딕셔너리에 저장한다.
• 찾고자 하는 연비가 존재하면 해당 경우의 수를 조회한다.

 

---

아이디어를 정리하자면,

 

1. 문제에서 주어진 연비를 오름차순으로 정렬한다.
2. 오름차순으로 정렬한 연비를 순서대로 탐색하면서 중앙값이 될 수 있는 경우의 수를 딕셔너리에 저장한다. 
   • 인덱스를 이용하여 경우의 수를 구한다.
   • 탐색 인덱스를 i라 하면, 경우의 수는  i X (전체 개수 -1 - i)
   • {연비 : 경우의 수}의 형태로 저장한다. (시간복잡도 O(1))
3. 테스트에서 요구하는 해당 연비가 중앙값이 될 수 있는 경우의 수를 딕셔너리에서 조회한다. (시간복잡도 O(1))
4. 딕셔너리에 존재하지 않으면 0을 출력한다.

 

반응형

 

📝 문제 풀이 (Code)

import sys

n, q = map(int, input().split())
# 연비를 순서대로 정렬
car = sorted(map(int,input().split()))

# 각 연비의 중앙값 경우의 수 저장
dic_car = {}
for i in range(n):
    # 각 연비 중앙 값 경우의 수
    dic_car[car[i]] = (i)*(n-1-i)

for j in range(q):
    # 테스트
    m = int(input())
    
    if dic_car.get(m):
        # 존재하는 연비
        print(dic_car[m])
    else:
        # 존재하지 않는 연비
        print(0)