Softeer Level 3 통근버스 출발 순서 검증하기 Python

문제 링크

https://softeer.ai/practice/6257

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

정답 코드

import sys

input = sys.stdin.readline

N = int(input())
busStation = list(map(int, input().split()))

result = 0
for idx in range(N-1):
    valueIdx = busStation[idx]
    isNotPossible = 0
    for jdx in range(idx+1, N):
        valueJdx = busStation[jdx]
        if valueIdx < valueJdx:
            isNotPossible += 1
        else:
            result += isNotPossible
print(result)

풀이 방법

1. isNotPossible은 쉽게 말해 idx에서 jdx까지의 버스 번호 들 중에서 안되는 버스의 경우의 수 개수 이다.
2. valueJdx와 비교해서 valueIdx가 작으면 그 뒤에 어떤 버스가 와도 순서대로 지나갈 수가 없다.
3. 따라서 valueIdx가 큰 경우에만 결과 값에 지금까지 안되는 경우의 수를 더해준다.

느낀점

• N이 5000이하 여서 삼중 for문으로 돌리면 일단 시간 복잡도가 O(N3)이 된다.
• 즉, 반복문을 이중 for문으로 줄여야 하는데 어려웠다.
• 몰라서 보고 풀었고 누적해서 더해준다는 점이 신기했다.