Compy's Blog
507 words
3 minutes
[BOJ] 수열 재배열
2025-03-06

수열 재배열

TimeLimitMemoryLimitConditionTAG
2s512MB(3 ≤ N ≤ 2000, 2 ≤ K ≤ N)BruteForce

내가 연속된 구간 k개를 고르고 앞만 이어진다. 뒤만 이어진다. 앞뒤만 이어진다. 아니면 나만 보겠다… 이것만 고려해서 나눠서 풀면 되겠스비다.

이것도 학교에서 풀어서 영상은 없네용

정답 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include<set>
using namespace std;
int inf = 1e9;


int solution(int n, int k, vector<int>& nums){
    
    
    // 그냥 나뒀을 때.. 는 이미 정렬할 대 되는거니까ㅏ상관 x
    // 내가 장렬됨에 따라서 뒤와 앞이 이어지는경우
    // 내가 정렬됨에 따라서 앞에를 버리고 뒤랑만 이어지는 경우
    // 내가 정렬됨에 따라서 뒤를 버리고 앞만 이어지는경우
    
    // 중복된거를 (length - 중복 개수)
    
    vector<int> origin(n), reverse(n);
    
    
    int result = 1;
    
    
    
    origin[0] = 1;
    reverse[n-1] = 1;
    
    for(int i = 1; i < n; i++){
        if(nums[i] <= nums[i-1]){
            
            origin[i] = 1;
        }else{
            origin[i] = origin[i-1]+1;
            result = max(origin[i], result);
        }
    }
    
    
    
    
    for(int i = n-2; i > -1; i--){
        if(nums[i+1] <= nums[i]) reverse[i] = 1;
        else reverse[i] = reverse[i+1]+1;
        
    }
    

    
    
    set<int> current_set;
    
    int start, end;
    for(int i = 0; i <= n-k; i++){
        current_set.clear();
        
        for(int j = 0; j < k; j++) current_set.insert(nums[j+i]);
        
        vector<int> current(current_set.begin(), current_set.end()); // 보통 정렬돼서 나오는 것처럼 보임..
        sort(current.begin(), current.end()); // 그래도 불안해
        
        
        // 앞뒤 이어지는 경우
        if(current.size() == k && i > 0 && i < n-k){
            start = 0;
            end = current.size()-1;
            if(current[start] > nums[i-1] && current[end] < nums[i+k]) result = max(result, end - start + 1 + origin[i-1] + reverse[i+k]);
        }

        // 앞만 이어지는 경우 | 앞 <- current -> 뒤
        if(i > 0){
            start = 0;
            while(start < current.size()-1 && current[start] <= nums[i-1]) start++;
            
            
            if(current[start] > nums[i-1]) result = max(result, origin[i-1] + (int) current.size() - start);
        }

        // 뒤만 이어지는 경우
        if(i < n-k){
            end = current.size()-1;
            while(0 < end && current[end] >= nums[i+k]) end--;
            
            if(current[end] < nums[i+k]) result = max(result, reverse[i+k] + end + 1);
        }

        result = max(result, (int)current_set.size());

        
    }
    
    return result;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int answer;
    int n, k;
    cin >> n >> k;
    
    
    vector<int> nums(n);
    for(int i = 0; i < n; i++) cin >> nums[i];
    
    int result = solution(n, k, nums);
    cout << result;
    /*
     10 3
     1 8 2 4 8 5 1 8 9 3
     5 4
     
     */
    return 0;
}



[BOJ] 수열 재배열
https://compy07.github.io/Blog/posts/boj/27739/
Author
뒹굴뒹굴 이정훈 공부방
Published at
2025-03-06