[HSAT 4회 정기 코딩 인증평가 기출] 통근버스 출발 순서 검증하기

[HSAT 4회 정기 코딩 인증평가 기출] 통근버스 출발 순서 검증하기

답

import sys
input = sys.stdin.readline
from itertools import combinations


N = int(input());
bus = tuple(map(int, input().split()));
result = 0;

for i in range(N):
    tmp = 0;
    flag = bus[i];
    for j in range(i+1, N):
        if flag < bus[j]:
            tmp += 1
        elif flag > bus[j]:
            result += tmp;
print(result)

풀이

처음에 생각해본 방법은 combinations 또는 for문을 3번 중첩하는 것이었다.
그러나 combination의 경우 가능한 모든 (a_i, a_j, a_k) 조합을 검사하여 첫 번째 조건 a_i < a_j를 만족하지 않을 때도 여러 개 발생하기 때문에 overhead가 너무 크다.
먼저 for문을 3번 중첩하는 방법을 사용했는데

for i in range(N): # i: 0 ~ 5
    flag = bus[i] # 4
    for j in range(i+1, N):
        if flag < bus[j]:
            for k in range(j+1, N):
                if flag > bus[k]:
                    result += 1;
print(result);

정말 단순하게 a_i < a_j를 만족할 때, 다시 for 문을 통해 a_i > a_k를 만족하는 경우가 있는지 찾는 코드이다. 그러나 시간 복잡도가 O(N^3)이기 때문에 무조건 시간 초과가 뜰 것이라고 생각했다. (역시나)

그래서 for문을 2개만 사용하는 것을 목표로 코드를 작성하였다.
a_i를 반복시키는 곳에서 1번, 그리고 하나의 a_i를 기준으로 조건을 만족하는 a_j, a_k 조합의 존재 여부를 찾는 곳에서 1번 사용했다.

for i in range(N):
    tmp = 0;
    flag = bus[i];
    for j in range(i+1, N):
        if flag < bus[j]:
            tmp += 1
        elif flag > bus[j]:
            result += tmp;
print(result)

tmp를 통해 a_i < a_j를 만족하는 a_j의 갯수를 세고, 그 뒤에 a_i > a_k를 만족하는 a_k가 나오면 그 때 당시의 tmp를 result에 업데이트 했다. 이렇게 한다면 a_k를 기준으로 자기 앞에 존재하던 조건을 만족하는 a_j들의 갯수만큼, 즉 (a_j, a_k) 조합의 갯수만큼 result가 증가하는 것이기 때문에 문제의 조건에 만족한다.