출처:https://www.acmicpc.net/problem/5648
문제
- 모든 원소가 양의 정수인 집합이 있을 때, 원소를 거꾸로 뒤집고 그 원소를 오름차순으로 정렬하는 프로그램을 작성하세요. 단, 원소를 뒤집었을 때 0이 앞에 선행되는 경우는 0을 생략해야합니다.
조건
- 첫 번째로 입력되는 건 n (1 ≤ n ≤ 10^6)으로 사용자가 뒤이어 입력할 원소값을 결정합니다. 입력하는 줄에는 하나의 원소값 뿐만 아니라 여러 원소값도 들어갈 수 있습니다. 단, 입력하는 정수는 10^12을 넘어선 안 됩니다.
풀이
간단한 문제이지만 , 예외조건들을 충분히 생각을 해봐야 쉽게 풀 수 있는 문제였다.
이 문제는 배열을 뒤집고, 배열을 정렬하면 되는 문제인데 배열을 뒤집는게 reverse함수를 간단하게 쓰면 되지만, 직접구현하려고 하다보니 꽤 생각을 했던 문제이다. (STL이 가능하다면, 바로 망설임 없이 reverse함수를 쓰도록하자. 시간아깝다.)
배열을 뒤집는 방법은 많이 있을 수 있다.
- 빈 배열을 만들어서 자기자신을 뒤에서 부터 넣는 방법
- 임시변수 한개를 둬서 배열의 양끝을 바꾸는 방법이 있다. (좀 신기했음)
string은 STL이다.
처음 구현할 때는, 빈 배열을 만들어서 ,자기자신을 뒤에서 부터 넣는방법으로 구현했다.근데, 오류가 터져서 이 과정에서 String에 대해 조금 더 자세하게 알게 되었다. 아래의 코드가 왜 공백이 출력되는지 생각해보자.
#include <bits/stdc++.h>
using namespace std;
string revese_string(string a)
{
string tmp = "";
int len = a.size() - 1;
for (int i = 0; i < a.size(); i++)
{
cout << "a[len-i]" << a[len - i] << '\n';
tmp[i] = a[len - i];
}
return tmp;
}
int main()
{
string a = "hello";
string b = "NNNNN";
string c = revese_string(a);
cout << c << '\n';
return 0;
}string을 출력해보면, 공백이 출력된다. 왜냐하면, string의 크기 값을 정해주지 않았기 때문이다. string은STL이고, 현재 코드에서는 tmp[i]값에 바로 할당을 하게된다. tmp의 메모리 주소 다음에 할당을 하지만, 이건 iterator가 인식할 수 있는 범위를 벗어났기 때문에, cout<<c를 실행하였을 때, 공백이 그대로 출력되는 것이었다.
해결방법은 2가지가 있다. string tmp의 크기를 string a의 크기와 맞춰주던지, string tmp의 연산을 할당이 아닌, +=누적으로 바꿔주면 된다.
문제의 정답코드는 다음과 같다.
#include <bits/stdc++.h>
#define ll long long
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int N;
vector<long long> arr;
string revese_arr(string a)
{
char tmp;
int len = a.size() - 1;
for (int i = 0; i < a.size() / 2; i++)
{
tmp = a[i];
a[i] = a[len - i];
a[len - i] = tmp;
}
int cnt = 0;
while (a[cnt] == '0')
a.erase(cnt, 1);
return a;
}
int main()
{
fastio;
cin >> N;
string s;
for (int i = 0; i < N; i++)
{
cin >> s;
arr.push_back(stoll(revese_arr(s)));
}
sort(arr.begin(), arr.end());
for (int i = 0; i < N; i++)
{
cout << arr[i] << '\n';
}
return 0;
}