[ Softeer ] 통근버스 출발 순서 검증하기

첫 제출에서 테케가 다 맞는 것도 어쩌면 행운이 아니라 불행이더라. 신나서 검토 과정 없이 제출하게 됨 ;

 

from itertools import combinations
import sys
input = sys.stdin.readline
n = int(input())
buses = list(map(int, input().split()))
count = 0
dict = {}
for i in range(len(buses)):
    dict[i] = buses[i]
comb = list(combinations(range(len(buses)),3))
for c in comb:
    if dict[c[0]] < dict[c[1]] and dict[c[0]] > dict[c[2]]:
        count += 1
print(count)

첫 제출. 1/5 만 맞았는데 이정도면 그냥 틀렸다고 보면 된다.

 

보니까 60%는 맞고 40%는 시간제한으로 터졌다.

어떻게 시간복잡도 개선이 가능하게 만들까.. 음..