[백준 / BOJ] C++ 1071 소트

1071번: 소트

 

문제

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

1071번: 소트

 

 

풀이

N개의 수를 입력받아 A[i]+1 ≠ A[i+1]를 만족하게 정렬하여 사전순으로 가장 앞서는 것을 출력하는 문제다. 그리디 알고리즘으로 풀면 된다. 두 시간 정도 들여서 AC 받았다.

 

가장 중요한 두가지가 있는데 첫 번째는 사전순으로 가장 앞서는 것이기 때문에 수를 정렬해 주고 시작해야 한다. 둘째는 남아있는 수의 (최댓값 - 최솟값)이 1이면 큰 수를 먼저 모두 출력한 후 작은 수를 모두 출력해야 한다.

 

예를 들면, 예제와 같이 1 1 1 1 2 2 2 2 2 라면 2 - 1 = 1이고 A[i]+1 ≠ A[i+1]를 만족하기 위해선 1이 2보다 앞에 등장할 수 없기 때문에 답은 2 2 2 2 2 1 1 1 1이다. 또 다른 예를 보면, 1 2 3 3 3 4 4인 경우 1보다 크면서 2는 아닌 3이 와야 하고 그다음엔 가장 작은 2가 온다. 그럼 남은 수는 3 3 4 4인데 4 - 3 = 1이기 때문에 4 4 3 3이 추가되어 답은 1 3 2 4 4 3 3이다.

 

사용한 숫자를 제거하는 데는 덱을 사용해 push_back, push_front, pop_back, pop_front 함수들을 사용한 수의 인덱스만큼 사용했다.

 

아직 정답 배열이 비어있는 경우엔 가장 작은 값을 넣어주도록 했고, N=1일 때 덱의 최댓값 - 최솟값은 항상 0이므로 조건을 1이 아니라 1 이하로 해주었다. (이거 때문에 한 번 틀렸다.)

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  vector<int> v(n), ans;
  deque<int> dq;
  for (int i = 0; i < n; i++)
    cin >> v[i];
  // 오름차순 정렬
  sort(v.begin(), v.end());
  for (int i = 0; i < n; i++)
    dq.push_back(v[i]);

  while (!dq.empty()) {
    // 남은 수의 (최댓값 - 최솟값)이 1 이하인 경우
    if (dq.back() - dq.front() <= 1) {
      while (!dq.empty()) {
        ans.push_back(dq.back());
        dq.pop_back();
      }
    } else {
      // 정답 배열이 빈 경우
      if (ans.size() == 0) {
        ans.push_back(dq.front());
        dq.pop_front();
        continue;
      }
      // 정답 배열이 비어있지 않은 경우
      for (int i = 0; i < n; i++) {
        // 정렬 조건을 만족하는 경우
        if (dq[i] - ans.back() != 1) {
          ans.push_back(dq[i]);
          for (int j = 0; j < i; j++) {
            dq.push_back(dq.front());
            dq.pop_front();
          }
          dq.pop_front();
          for (int j = 0; j < i; j++) {
            dq.push_front(dq.back());
            dq.pop_back();
          }
          break;
        }
      }
    }
  }
  for (int i : ans)
    cout << i << ' ';
  cout << '\n';
  return 0;
}