[Python] 백준 31395. 정렬된 연속한 부분수열의 개수

문제

길이가 N$N$인 수열 A1,⋯,AN이 주어집니다. 수열의 모든 수는 서로 다른 1 이상 N 이하의 수입니다. 아래 조건을 모두 만족시키는 (i,j)정수쌍의 개수를 구하세요.

•  1≤i≤j≤N
•  A의 i번째 수부터 j번째 수까지가 오름차순으로 배열되어있다. 즉, i≤k<j를 만족하는 모든 정수 k에 대해 Ak<Ak+1

입력

첫 줄에 수열의 길이 N이 주어집니다. (1≤N≤200000)

다음 줄에는 수열의 각 원소 A1,A2,⋯,AN이 공백으로 구분되어 주어집니다. (1≤Ai≤N; A1,A2,⋯,AN은 서로 다른 정수)

출력

문제의 조건을 만족시키는 (i,j) 정수쌍의 개수를 출력하세요.

---

풀이

처음에는 생각을 잘못해서 조금 돌아가는 바람에... 시간초과를 봤지만... 반복문을 한번만 쓰는 방향으로 어떻게 풀어야할까 고민하다가 친구한테 힌트를 얻어 후다닥 해결했다!

 

이전에 증가하고 있던 수보다 그 다음 수가 더 큰거라면 이전에 더해진 경우의 수에 +1를 해주면 되는 문제. 아니라면 그냥 더해주지 않으면 된다! 이렇게 글로만 설명하면 이해가 잘 안될 것 같아서 그림을 그려오자면...

1. 하나씩은 다 하나의 개수로 포함되기 때문에 1을 res배열에 넣어주고

2. 증가할때는 이전 값에 +1씩해서 res배열에 저장해주고 / 감소할때는 아무것도 하지 않는다.

3. 그렇게 모든 과정을 거친 res배열에 저장된 값들을 총 합해서 출력해준다.

 

import sys
input = sys.stdin.readline

n = int(input().strip())
nums = list(map(int, input().split()))
res = [1] * n #1번 과정
result = 0

for i in range(1,n): #2번 과정
    if nums[i] > nums[i-1]: #증가할때
        res[i] = res[i-1]+1

for i in range(n): #3번 과정
    result += res[i] #res 배열에 저장된 값들을 모두 더해준다.

print(result) #출력!

 

이러면 답이 구해진다~

 

시간복잡도

for문이 n번 돌기 때문에 O(n)이다.