https://softeer.ai/practice/info.do?idx=1&eid=654&sw_prbl_sbms_sn=139534

난이도: ⭐️⭐️⭐️

과정 설계

[조합] 가져다 쓰기 (시간 초과)

1. 최초 인풋 int_list
2. itertools의 조합 메소드를 사용하여 int_list에서 3개 뽑을 수 있는 조합 구함
3. 문제 조건을 이용하여 조건에 해당할 때만 num_ijk 증가

조합의 시간복잡도가 O(N^3)으로 계산되므로 시간초과 발생

구현

참고 링크

조합을 사용하지 않고 문제를 풀기가 너무 까다로웠다. 결국, 타인의 풀이 참고

원리는 아래와 같다.

1.0번부터 n-3번까지 기준점을 변경한다. (n-3번까지인 이유는 3개 단위로 문제 조건을 만족하는지 검사해야 하므로)
2. 기준점 다음부터 대소비교를 한다. 기준점보다 크면 O, 작으면 X
3. X가 나올때마다 앞의 O 총 개수를 누적합
4. 기준점을 끝까지 다 돌았을 때의 O의 총 개수가 곧 정답

코드

[조합] 코드 (시간 초과)

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

def check(arr):
    if arr[0] < arr[1] and arr[0] > arr[2]:
        return True
    return False

num_ijk = 0
n = int(input())
int_list = list(map(int,input().split()))
three_list = list(comb(int_list,3))
for i in range(len(three_list)):
    if check(three_list[i]):
        num_ijk += 1
print(num_ijk)

[구현] 코드

import sys
input = sys.stdin.readline

num_ijk = 0
n = int(input())
int_list = list(map(int,input().split()))
ox_matrix = [['O']*n for _ in range(n)]

for i in range(n):
    for j in range(i,n):
        if int_list[i] > int_list[j]:
            ox_matrix[i][j] = 'X'
for i in range(n-2):
    circle = 0
    for j in range(i+1,n):
        if ox_matrix[i][j] == 'O':
            circle += 1
        else:
            num_ijk += circle
print(num_ijk)