[백준] 1071_소트 C++
in Study on Coding Test
정렬을 짜보는 문제
정답제출코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
vector<int> Arr;
void Swap(int& a, int& b)
{
int tmp = a;
a = b;
b = tmp;
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for (int i = 0; i < N; ++i)
{
int _input;
cin >> _input;
Arr.push_back(_input);
}
sort(Arr.begin(), Arr.end());
if (N == 1)
{
cout << Arr[0];
return 0;
}
else if (N == 2)
{
if (Arr[0]+1 == Arr[1])
cout << Arr[1] << ' ' << Arr[0];
else
cout << Arr[0] << ' ' << Arr[1];
return 0;
}
for (int i = 0; i < N; ++i)
{
if (Arr[i+1] == Arr[i]+1)
{
int end = i+2;
if (end != N)
{
while (Arr[end] == Arr[i+1])
end++;
}
if (end == N)
{
int start = i-1;
if (start >= 0)
{
while (Arr[start] == Arr[i])
start--;
}
Swap(Arr[i+1], Arr[start+1]);
}
else
Swap(Arr[i+1], Arr[end]);
}
}
for (int i = 0; i < N; ++i)
cout << Arr[i] << ' ';
return 0;
}
원하는 조건에 맞춰서 정렬을 구성해보는 문제였다.
A[i] + 1 != A[i+1]이라는 조건에 맞추는거야 괜찮은데
문제는 사전 순으로 정렬하는 것까지 생각하니 어려워졌다.
sort(Arr.begin(), Arr.end(), cmp);
라는 조건이 있으면 cmp를 구성해야한다고 생각했다.
bool cmp(int a, int b)
{
if (a != b+1)
return true;
return false;
}
그래.. 처음엔 이렇게 생각했었는데..
두 가지 수만 비교하는 게 아니라 여러 수를 고민해야하는 문제도 발생했다.
따라서 두 수만 비교하는 방법을 선택하면 한계에 부딪힐 것이라 생각했다.
실제로 저 방법을 사용해보니
3
1 2 3
// 출력 값 : 3 1 2
이렇게 나왔다. 이러면 안되는 거잖아. 흠..
세 수를 비교해야할까? 곰곰이 생각을 했다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
vector<int> Arr;
void Swap(int& a, int& b)
{
int tmp = a;
a = b;
b = tmp;
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for (int i = 0; i < N; ++i)
{
int _input;
cin >> _input;
Arr.push_back(_input);
}
if (N == 1)
{
cout << Arr[0];
return 0;
}
sort(Arr.begin(), Arr.end());
else if (N == 2)
{
if (Arr[0]+1 == Arr[1])
cout << Arr[1] << ' ' << Arr[0];
else
cout << Arr[0] << ' ' << Arr[1];
return 0;
}
for (int i = 0; i < N-2; ++i)
{
if (Arr[i+1] == Arr[i]+1)
Swap(Arr[i+1], Arr[i+2]);
// 그래도 규칙에 부합하지 못할 경우
if (Arr[i+1] == Arr[i]+1)
Swap(Arr[i], Arr[i+2]);
}
for (int i = 0; i < N; ++i)
cout << Arr[i] << ' ';
return 0;
}
대충 짜놓은 코드는 위와 같았다.
그런데 문제가 발생했다.
아래와 같은 테스트 케이스를 돌렸을 때이다.
9
1 1 1 1 2 2 2 2 2
// 출력 값 : 1 1 1 2 2 2 2 1 2
정답으로 나와있는 테스트케이스랑 다르게 나온다.
허허.. 그렇다면 모든 수에 대해서 고려를 해줘야 한다는 뜻인거네.
이 경우는 떠오르지 않아서 결국 구글링을 해보기로 했다.
참고링크를 참고하였다.
아하! 이분은 스왑을 하기 위한 용도로 투포인터? 비스무리한 방법을 사용하셨다.
우선 사전 순이기 때문에 입력을 받고나서 오름차순 정렬을 해준다.
그리고 start와 end 인덱스를 통해 Swap할 인덱스를 찾는 것이다.
이 분의 글에 따르면
- v[i+1] 값과 v[n-1] 값이 같은 경우, v[i]값을 가지는 원소 중 가장 작은 index를 가지는 값과 v[i+1]를 swap한다.
- v[i+1]값과 다른 값은 가지는 원소중 가장 작은 index를 가지는 값과 v[i+1]를 swap한다.
라고 적혀있다.
v[start+1] ++;
v[i+1] --;
그리고 이 코드의 의미는 차이가 1인 인덱스끼리 swap을 진행하는 것이라 생각하여
난 이부분을 swap 함수를 사용하는 것으로 바꿔주었다.
그래서 나의 정답제출코드는 맨 위에 나온 코드와 같다.
