[Python] 최장 연속 부분 수열

1. 숫자가 동일한 연속 부분 수열

- 연속 부분 수열이란 어떤 수열에서 특정 구간에 속하는 수들을 모두 뽑았을 때 나오는 부분 수열이다.

- 연속해서 나오는 같은 숫자를 한 묶음이라 할 때, 총 몇 개의 묶음이 나오는지 구하라.

 

- 수열은 다음과 같다.

 

- 수열에서 [1,1,1], [2,2], [3,3,3,3], [2] 총 4개의 묶음이 있다는 것을 알 수 있다.

 

 

- 그림에서 빨간색 테두리는 새로운 묶음이 시작되는 index이다.

- 따라서 새로운 묶음이 시작되는 index 개수가 답이 되는 것을 알 수 있다.

- 새로운 묶음의 특징은 2가지가 있다.

- 첫 번째, 직전에 나온 숫자와 다른 숫자가 나왔다.

- 두 번째, index가 0일 때 시작된다.

- 2가지 조건에 만족하면 개수를 증가시킨다.

 

arr = list(map(int, input().split()))
cnt = 0
for i in range(len(arr)):
    if i == 0 or arr[i-1] != arr[i]:
        cnt += 1
print(cnt)

 

>> 1 1 1 2 2 3 3 3 3 2
4

 

 

Q) 연속하는 수의 최대 횟수

- n개의 숫자들이 주어질 때, 연속하여 동일한 숫자가 나오는 최대 횟수를 구하라.

- 최대 횟수에 대한 배열도 출력하라.

 

n = int(input())
arr = list(map(int, input().split()))
max_cnt = 0
max_arr = []
for i in range(n):
    if i == 0 or arr[i] != arr[i-1]:
        cnt = 1
        temp_arr = [arr[i]]
    else:
        cnt += 1
        temp_arr.append(arr[i])
    max_cnt = max(cnt, max_cnt)
    if len(temp_arr) > len(max_arr):
        max_arr = temp_arr
print(max_cnt)
print(max_arr)

 

>> 10
>> 1 1 1 2 2 3 3 3 3 2
4
[3, 3, 3, 3]

 

 

- 연속한 두 숫자가 일치하는 경우 cnt에 1을 더해준다.

- 연속한 두 숫자가 일치하지 않는 경우 cnt는 1이 되며 초기화한다.

- 또한 index가 0이면 시작점이기 때문에 cnt는 1이 되어야 한다.

- index가 1 이상이면 연속한 두 숫자의 일치, 불일치 조건에 따라 cnt를 결정한다.

- cnt가 최대가 되면 max_cnt를 갱신한다.

 

- 최대 횟수에 대한 배열을 출력하기 위해서는 조건이 일치하지 않는 경우 temp_arr을 만들어 arr [i]를 삽입한다.

- 조건이 일치하는 경우 만들어진 temp_arr에 arr [i]를 삽입한다.

 

 

Q) 동일한 부호의 최대 길이

- n개의 숫자들 중 부호가 동일한 숫자로만 이루어진 연속 부분 수열 중 최대 길이를 구하라.

- 최대 길이에 해당하는 배열도 출력하라.

 

n = int(input())
arr = list(map(int, input().split()))
max_cnt = 0
max_arr = []
for i in range(n):
    if i == 0 or arr[i] * arr[i-1] < 0:
        cnt = 1
        temp_arr = [arr[i]]
    else:
        cnt += 1
        temp_arr.append(arr[i])
    max_cnt = max(cnt, max_cnt)
    if len(temp_arr) > len(max_arr):
        max_arr = temp_arr
print(max_cnt)
print(max_arr)

 

>> 10
>> 1 2 3 4 -1 -2 -3 1 2 3
4
[1, 2, 3, 4]

 

 

- 동일한 부호인지 확인하려면 연속한 두 수를 곱해 양수가 나오면 된다.

- 두 수를 곱해 음수가 나오면 서로 다른 부호라는 것을 알 수 있다.

 

 

Q) 연속 증가하는 부분 수열

- n개의 숫자들이 주어졌을 때, 증가하는 연속 부분 수열 중 최대 길이를 구하라.

- 최대 길이일 때 연속 부분 수열을 구하라.

 

n = int(input())
arr = list(map(int, input().split()))
max_cnt = 0
max_arr = []
for i in range(n):
    if i == 0 or arr[i-1] >= arr[i]:
        cnt = 1
        temp_arr = [arr[i]]
    else:
        cnt += 1
        temp_arr.append(arr[i])
    max_cnt = max(cnt, max_cnt)
    if len(temp_arr) > len(max_arr):
        max_arr = temp_arr
print(max_cnt)
print(max_arr)

 

 

>> 10
>> 1 2 3 4 3 2 1 4 6 8
4
[1, 2, 3, 4]

 

 

- 연속한 두 숫자가 증가하는 경우는 현재 숫자가 이전 숫자보다 커야 한다.

- 증가하는 경우는 cnt에 1을 더해준다.

- 현재 숫자가 이전 숫자보다 작거나 같으면 증가하는 경우가 아니다.

- 이러한 경우는 cnt를 1로 초기화한다.

- 또한 index가 0이면 cnt를 1로 초기화하고 1부터는 증가하는지 증가하지 않는지에 따라 cnt를 결정한다.

 

 

Q) 숫자를 기준으로 하는 연속 부분 수열

- n개의 숫자들로 이루어져 있을 때, m과 sign의 조건으로 연속 부분 수열 중 최대 길이를 구하라.

- 최대 길이에 해당하는 수열도 구하라.

- sign이 +이면 m보다 큰 수로만 이루어진 연속 부분 수열이다.

- sign이 -이면 m보다 작은 수로만 이루어진 연속 부분 수열이다.

- sign이 =이면 m과 같은 수로만 이루어진 연속 부분 수열이다.

 

n, m, sign = input().split()
n, m = int(n), int(m)
arr = list(map(int, input().split()))
cnt, max_cnt = 0, 0
max_arr, temp_arr = [], []

for i in range(n):
    if (sign == '+' and arr[i] > m) or (sign == '-' and arr[i] < m) or (sign == '=' and arr[i] == m):
        cnt += 1
        temp_arr.append(arr[i])
    else:
        cnt = 0
        temp_arr = []
    max_cnt = max(max_cnt, cnt)
    if len(temp_arr) > len(max_arr):
        max_arr = temp_arr

print(max_cnt)
print(max_arr)

 

 

>> 10 5 +
>> 1 3 5 7 7 6 4 2 8 9
3
[7, 7, 6]


>> 10 6 -
>> 1 3 5 7 7 6 4 2 8 9
3
[1, 3, 5]

>> 10 7 =
>> 1 3 5 7 7 6 4 2 8 9
2
[7, 7]

 

 

- sign이 +이면 리스트에 있는 숫자가 m보다 커야 하므로 arr [i] > m이 만족해야 한다.

- sign이 -이면 리스트에 있는 숫자가 m보다 작아야 하므로 arr [i] < m이 만족해야 한다.

- sign이 =이면 리스트에 있는 숫자가 m과 같아야 하므로 arr [i] == m이 만족해야 한다.

- 3가지 경우에는 cnt를 1 증가하고 임시 리스트인 temp_arr에 값을 삽입한다.

- 3가지 경우가 아니면 cnt를 0으로 초기화하고 temp_arr를 비워 놓는다.