[백준 / BOJ] C++ 13274 수열

13274번: 수열

 

문제

 

https://www.acmicpc.net/problem/13274

13274번: 수열

 

 

풀이

단순한 구현 문제다. 하지만 정렬을 매번 하게 되면 시간초과가 난다! 따라서 정렬을 최소한으로 해야 한다. 그래서 STL sort 함수의 시간복잡도도 찾아보고,, 최악일 때도 O(N log N)인 머지 소트로 해도 안되더라..

 

결국 찾은 해결법은 L, R, X를 입력받았을 때 이미 수열은 정렬되어 있다. 그리고 L부터 R까지 X를 더했을 때, 이를 제외한 부분은 정렬되어 있는 상태고 L부터 R도 정렬되어 있는 상태다. 그래서 최소한의 필요한 부분만 정렬을 해줬다!

X가 양수인 경우, L 이전은 위치가 변하지 않는다. 따라서 L부터 이후를 정렬해준다.
X가 음수인 경우 R 이후는 위치가 변하지 않는다. 따라서 처음부터 R까지를 정렬해 준다.

위 방법대로 최소한의 구간만 정렬해 줬더니 통과됐다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, k;
  cin >> n >> k;
  vector<ll> v(n);
  for (int i = 0; i < n; i++)
    cin >> v[i];
  sort(v.begin(), v.end());
  while (k--) {
    int l, r, x;
    cin >> l >> r >> x;
    for (int i = l - 1; i < r; i++)
      v[i] += x;
    if (x > 0)
      sort(v.begin() + l - 1, v.end());
    else if (x < 0)
      sort(v.begin(), v.begin() + r);
  }
  for (ll i : v)
    cout << i << ' ';
  return 0;
}