[2491] 수열

문제 출처 : https://www.acmicpc.net/problem/2491

분류 : 구현

백준 2491 수열

가장 긴 단조증가 혹은 단조감소 수열의 길이를 찾아라

---

구현 포인트

1) 증가하는 것만 고려해서 찾고, 감소하는 것만 고려해서 최대 길이를 찾는다.

2) 너무 복잡하게 생각하지 말 것(입력이 최대 100,000개이다.)

이 문제에 대한 리뷰가 필요했던 이유는 너무 복잡하게 생각했다는 것이였다.

증가인 상태와 감소인 상태, 감소에서 증가로 가는 상태 등등 여러 상태들을 표현하려고 했다.

그러다 보니 코드가 길어지고 복잡해 졌다.

우선 처음에 구현된 코드는 아래와 같다...

매우 가독성이 떨어지는..;; 반성해야 할 것 같다..

참고로 여기서는 flag로 상태 전이를 이용하여 구현하였다..너무 어렵게 생각했다..

#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N, prev, cur, len = 1, tmp_len = 0;
    int flag = 0; //+1, -1, +2, -2
    cin >> N;
    vector<int> len_list;
    for (int i = 0; i < N; i++) {
        cin >> cur;
        if (i) {
            if (prev == cur) {
                switch (flag) {
                case -2://감소
                    flag = -1;
                    tmp_len = 2;
                    break;
                case 2://증가
                    flag = 1;
                    tmp_len = 2;
                    break;
                default:
                    tmp_len++;
                    break;
                }
                len++;
            }
            else {
                if (prev < cur) {
                    switch (flag) {
                    case 0: case 1:
                        flag = 2;
                        break;
                    case -1:
                        len_list.push_back(len);
                        len = tmp_len;
                        flag = 2;
                        break;
                    case -2:
                        len_list.push_back(len);
                        len = 1;
                        flag = 2;
                        break;
                    case 2:
                        break;
                    }
                    len++;
                }
                else {
                    switch (flag) {
                    case 0: case -1:
                        flag = -2;
                        break;
                    case 1:
                        len_list.push_back(len);
                        len = tmp_len;
                        flag = -2;
                        break;
                    case 2:
                        len_list.push_back(len);
                        len = 1;
                        flag = -2;
                        break;
                    case -2:
                        break;
                    }
                    len++;
                }
            }
        }
        prev = cur;
    }
    len_list.push_back(len);
    if (DEBUG) cout<<"len : " << len << ", " << tmp_len << '\n';
    cout << *max_element(len_list.begin(), len_list.end()) << '\n';
}

아무리 생각해도 이건 뭔가 다른 방법이 있을 것이라 생각하고 다른 사람들의 코드를 살펴보았다..

생각이 너무 막혀있었다라는 것을 다시 한번 깨닫게 되었다.

그냥 10만개 2번 loop돌아도 충분히 1초 이내에 수행이 될텐데 왜 어렵게만 생각하려고 했었을까..

그냥 증가하는것 구하고, 감소하는것 구해서 길이 최대만 구하면 된다.

#include<cstdio>
 
int main() {
    int N, len=1, max=1; 
    scanf("%d", &N);
    int* arr = new int[N];
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
    for (int i = 1; i < N; i++) {
        if (arr[i - 1] <= arr[i]) len++;
        else len = 1;
        if (len > max)
            max = len;
    }
    len = 1;
    for (int i = 1; i < N; i++) {
        if (arr[i - 1] >= arr[i]) len++;
        else len = 1;
        if (len > max)
            max = len;
    }
    printf("%d\n", max);
}