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

문제링크

---

HSAT 7회 정기 코딩 인증평가 기출 | 자동차 테스트

풀이과정

---

처음 문제를 보자마자 생각한건 3개를 뽑아서 조합을 만들고, 거기서 정렬을 해서 가운데 값을 딕셔너리 키 값으로 써서 개수를 전체 케이스에서 개수를 카운트했다.

당연히 .. 시간초과 .. 2개 빼고 전부 다 시간 초과였다.

근데 생각해보니, 진짜 모든 경우의 수를 다 찾아서 중앙값을 찾는 것 자체가 말도 안되는 아이디어라고 생각했다. 그래서 생각한 건 경우의 수를 찾지 않아도 수식으로 계산할 수 있을것 같다는 생각 .. ?

예제 1에서 5 2 3 1 6이 입력되었을 때 이걸 정렬하면 1 2 3 5 6이다.

기준값	작은 수의 개수	큰 수의 개수	결과
1	0	4	0
2	1	3	3
3	2	2	4
5	3	1	3
6	4	0	0

기준 값보다 작은수와 큰수의 개수를 곱하면 문제에서 구하는 서로 다른 경우의 수를 찾을 수 있더라 ...
나자신 기특해 음음 !

코드

---

1. 2개만 통과(시간 초과)

import sys
from itertools import permutations

n, q = map(int, input().split())
oils = list(map(int, input().split()))

result = {}
for i in range(len(oils)):
    result[oils[i]] = []

oils_permu = permutations(oils, 3)
oils_permu = set(oils_permu)

for ele in oils_permu:
    ele = sorted(list(ele))
    if ele not in result[ele[1]]:
        result[ele[1]].append(ele)

# print(result)
for _ in range(q):
    m = int(sys.stdin.readline().rstrip())
    if m in result.keys():
        print(len(result[m]))
    else:
        print(0)

2. 통과 ! (정렬 사용)

import sys
from itertools import permutations

n, q = map(int, input().split())
oils = list(map(int, input().split()))
oils.sort()

result = {}
for i in range(n):
    result[oils[i]] = i * (n - i - 1)

for _ in range(q):
    m = int(sys.stdin.readline().rstrip())
    if m not in result.keys():
        print(0)
    else:
        print(result[m])

결과

---