[백준] 2491 수열

2491번: 수열

 

www.acmicpc.net

풀이

가장 긴 길이의 연속해서 커지거나 작아지는 수열을 찾는 문제이다. 연속해서 커지는 수열의 길이를 찾을 수 있으면, 입력 받은 숫자 배열을 뒤집어서 연속해서 작아지는 수열의 길이를 찾을 수 있다. 해당 문제에서 실제 연속해서 커지는 수열의 값이 필요한 것이 아니라 길이만 알면 되기 때문에 투 포인터 알고리즘을 사용해 해결했다.

코드

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> num;

int two_pointer() {
    int left = 0;
    int right = 0;
    int last_value = 0; // 수열의 마지막 값을 저장할 변수
    int ret = 0; // 수열의 최대 길이를 저장할 변수

    while (true) {
        // 두 인덱스가 같은 경우
        if (left == right) { 
            last_value = num[right]; // 수열의 마지막 값 저장
            right++;
            ret = max(ret, right - left); // 수열의 길이가 변경되었으므로 최댓값 비교
        }
        else if (right == n) break; // 끝 인덱스가 범위를 벗어난 경우 종료
        // 수열의 마지막 값보다 큰 수가 나온 경우
        else if (num[right] >= last_value) {
            last_value = num[right]; // 수열의 마지막 값 갱신
            right++;
            ret= max(ret, right - left); // 수열의 길이가 변경되었으므로 최댓값 비교
        }
        else left++;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    num = vector<int>(n);
    for (int i = 0; i < n; i++)
        cin >> num[i];
    int answer = two_pointer();
    reverse(num.begin(), num.end());
    answer = max(answer, two_pointer());
    cout << answer << '\n';
    return 0;
}

Python3

import sys
from bisect import bisect_left

n = int(sys.stdin.readline().rstrip())
num = list(map(int, sys.stdin.readline().rstrip().split()))


def two_pointer():
    left = 0
    right = 0
    last_value = 0 # 수열의 마지막 값을 저장할 변수
    ret = 0 # 수열의 최대 길이를 저장할 변수
    while True:
        # 두 인덱스가 같은 경우
        if left == right:
            last_value = num[right] # 수열의 마지막 값 변경
            right += 1
            ret = max(ret, right - left) # 수열의 길이가 변경되었으므로 최댓값 비교
        # 끝 인덱스가 범위를 벗어난 경우 종료
        elif right == n:
            break
        # 수열의 마지막 값보다 큰 수가 나온 경우
        elif num[right] >= last_value:
            last_value = num[right] # 수열의 마지막 값 갱신
            right += 1
            ret = max(ret, right - left) # 수열의 길이가 변경되었으므로 최댓값 비교
        else:
            left += 1
    return ret


answer = two_pointer()
num.reverse()
answer = max(answer, two_pointer())
print(answer)