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

[Softeer]

Question

Language: Python

해당 문제는 (i,j,k)의 순서쌍에 대해서 a_i < a_j a_j > a_k 을 만족하는 순서쌍의 갯수를 구하는 문제이다.

Failed Solution

처음에는 모든 순서쌍을 고려해서 조건식을 만족하는 순서쌍의 갯수를 구하려고 하였다.

import sys
def solution():
    count=0
    for i in range(n):
        for j in range(i+1,n):
            if numbers[i]<numbers[j]:
                for k in range(j+1,n):
                    if numbers[i] > numbers[k]:
                        count+=1
    print(count)
if __name__ == "__main__":
    n=int(sys.stdin.readline())
    numbers=list(map(int,sys.stdin.readline().split()))

    solution()

하지만 n=5000이므로 O(n³)인 알고리즘에서는 시간초과가 발생할 수 밖에 없다.

구간합 활용

해당 문제의 초점은 버스 번호의 갯수가 고정이라는 점이다. 이것을 통해, i번째 순서쌍에 해당되는 버스의 번호는 1~5000임을 알 수 있고, 이를 통해 i보다 작은 k의 순서쌍의 갯수를 미리 저장해놓으면 시간 복잡도를 O(n³) 에서 O(n²)로 줄일 수 있다.

index k을 기준으로 bus[i] 보다 작은 버스의 갯수가 몇개 인지를 누적합을 통해 구한다.

#뒤에서 부터 조사하면서
for k in range(n-1,-1,-1):
    #bus[i] 보다 작은 k의 갯수를 누적해서 저장한다.
    for i in range(n+1):
        if bus[k] < i:
            lower_nums[i][k]=lower_nums[i][k+1]+1
        else:
            lower_nums[i][k]=lower_nums[i][k+1]

Solution

import sys
def solution():
    lower_nums=[[0] * (n+1) for _ in range(n+1)]

    for k in range(n-1,-1,-1):
        for i in range(n+1):
            if bus[k] < i:
                lower_nums[i][k]=lower_nums[i][k+1]+1
            else:
                lower_nums[i][k]=lower_nums[i][k+1]
    
    count=0
    for i in range(n-1):
        for j in range(i+1,n):
            if bus[i]<bus[j]:
                count+=lower_nums[bus[i]][j]

    print(count)
if __name__ == "__main__":
    n=int(sys.stdin.readline())
    bus=list(map(int,sys.stdin.readline().split()))

    solution()