글 읽기 - 시간의 지배자님들께 질문드립니다.

allgoodlife 7년 전 0

요새 푸는 문제마다 시간이 발목을 잡네요.

이 문제를 O(n²)으로 풀었는데 채점시 45%에서 시간초과가 뜨네요...

혹시 더 빠른 방법으로 접근 가능한가요?

이 문제는 LIS와 다른 것 같은데, 참고할만한 알고리즘 또한 알려주시면 감사하겠습니다.

시간초과 너무나 어렵네요ㅜㅜ

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


int main(void){
	int n;
	scanf("%d", &n);
	vector<int> nums(n);
	vector<int> max(n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &nums[i]);
	}
	
	for (int i = 0; i < n; i++)
	{
		int tmp = 1;
		int status = 0;
		for (int j = i; j < n-1; j++)
		{
			if (status == 0){
				if (nums[j] < nums[j + 1]){
					status = 1;
					tmp++;
				}
				else if (nums[j] > nums[j + 1]){
					status = -1;
					tmp++;
				}
				else{
					tmp++;
				}
			}
			else if (status == 1){
				if (nums[j] <= nums[j + 1]){
					tmp++;
				}
				else{
					status = -7;
				}
			}
			//status ==-1
			else if(status == -1){
				if (nums[j] >= nums[j + 1])
					tmp++;
				else
					status = -7;
			}
			else{
				max[i] = tmp;
				break;
			}
			max[i] = tmp;
		}
	}
	max[n - 1] = 1;
	sort(max.begin(), max.end());
	printf("%d", max[n-1]);
	return 0;
}

kesakiyo 7년 전 1

참고할만한 알고리즘은 없는것 같습니다.

수가 감소하거나 증가하는 순간 새로운 순서가 시작된다고 생각하시면

O(N)에 해결할 수 있습니다.

allgoodlife 7년 전 0

kesakiyo 님의 답변 감사드립니다.

O(n)에 해결하고자 짠 코드는 다음과 같습니다.

여기서 문제는 다음과 같은 테스트케이스 에서 발생합니다.

4 1 3 3 2 2 9 2 3

즉, 1 3 3 에서 증가로 인식하고(status=1) 증가가 끝나는 2부터 다시 세고있는데

정답은 3 3 2 2일 때 4입니다.

3이 증가하는 수열의 일부인 지, 아니면 감소하는 수열의 시작점 인지 어떻게 찾을 수 있을까요?

#include <iostream>
#include <vector>
using namespace std;
 
 
int main(void){
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }
    int tmp = 1;
    int max = 1;
    int status = 0;
    for (int i = 0; i < n-1; i++)
    {
        if (status == 0){
            if (nums[i] > nums[i + 1]){
                status = -1;
                tmp++;
            }
            else if (nums[i] < nums[i + 1]){
                status = 1;
                tmp++;
            }
            else{
                tmp++;
            }
        }
        else if (status == 1){
            if (nums[i] <= nums[i + 1]){
                tmp++;
            }
            else{
                if (tmp > max)
                    max = tmp;
                status = -1;
                tmp = 2;
            }
        }
        //status ==-1
        else{
            if (nums[i] >= nums[i + 1]){
                tmp++;
            }
            else{
                if (tmp > max)
                    max = tmp;
                status = 1;
                tmp = 2;
            }
        }
    }
    if (tmp > max)
        max = tmp;
 
    cout << max << endl;
    return 0;
}