이제... 완전 종강이구나...
오늘은 저녁 약속이 있어서 얼른 얼른 끝내야겠다~!!
무슨 문제를 풀까 고민하다가 골드 문제를 한번 풀어볼까 해서 골라보았다.
문제
https://www.acmicpc.net/problem/1083
1083번: 소트
크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전
www.acmicpc.net
처음에 2개씩 자리를 서로 바꾸라고 하는 줄 알고 잘못구현했었다...
예제는 잘 나와서 "뭐지?" 했는데
다시 보니... 버블 정렬 문제였다 ㅎㅎ
// 문제 잘못읽고 구현한 코드
#include <iostream>
using namespace std;
int n, S, temp;
int A[1000001];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> A[i];
}
cin >> S;
int j = 0;
for (int i = 0; i < S; i++) {
temp = A[j];
A[j] = A[j + 1];
A[j + 1] = temp;
j += 2;
}
for (int i = 0; i < n; i++) {
cout << A[i];
if (i != n - 1) {
cout << " ";
}
}
return 0;
}
음음... 내가 잘못구현한 코드를 다시 고쳐야겠군..
이라고 했지만....
처참....ㅎㅎ
모르겠어... 왜 틀렸는지 모르겠어요...
아...?? swap이 있었던 것을 까먹고 있었다...
결과가 사전 순으로 가장 뒷서도록 하라는 것은 내림차순으로 하라는 뜻이다. 그러니 최대한 앞을 큰 수로 만들어야한다.
이 분의 풀이에 따르면 i번째 자리에서 x칸 떨어져 있는 수는 최소 x번의 swap으로 i번째 자리로 끌어올 수 있다고 한다.
그리고 남은 s번 이내의 swap으로 끌어올 수 있는 가장 큰 수를 찾고 그 수를 현재 위치로 끌어오는 과정을 반복하면 된다고 한다.
#include <iostream>
using namespace std;
int N, S;
int A[51];
int main()
{
cin >> N;
for (int i=0; i<N; i++) cin >> A[i];
cin >> S;
int start = 0;
while (start < N && S > 0) {
// S번 이내의 스왑으로 끌어올 수 있는 가장 큰 값을 A[start]로 끌어오기
int maxIdx = start;
for (int i=start; i<=min(N-1, start+S); i++) {
if (A[maxIdx] < A[i]) maxIdx = i;
}
for (int i=maxIdx; i>start; i--) {
swap(A[i], A[i-1]);
S--;
}
start++;
}
for (int i=0; i<N; i++) cout << A[i] << " ";
return 0;
}
출처: https://please-amend.tistory.com/m/161
그래서 뭔 소리인가 하고 계속 보고 있었는데....
(두둥!!)
어...? 뭔가 나... 또 문제를 잘못 이해한 것 같은데...???
가장 큰 수를 찾고 그 수를 현재 위치로 끌어오는 거라고...??
흠... 잠시만 다른 풀이도 보고 와야겠다...
#include <iostream>
#include <algorithm>
using namespace std;
int N,S,temp, cnt = 0, maxnum,maxidx;
int arr[51];
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N;
for(int i = 0; i < N; i++){
cin >> arr[i];
}
cin >> S;
for(int i = 0; i < N - 1 && S != 0; i++){
cnt = 0;
maxnum = arr[i];
maxidx = i;
for(int j = i + 1; j < N && cnt < S;j++,cnt++){
if(maxnum < arr[j]){
maxnum = arr[j];
maxidx = j;
}
}
int j = maxidx;
if(maxidx > i){
while(j != i){
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j-- ;
}
}
S -= (maxidx - i);
}
for(int i = 0; i < N; i++){
cout << arr[i] << " ";
}
return (0);
}
출처: https://allmymight.tistory.com/109
아!!!!!! 이제야 처음에 찾은 풀이가 무슨 뜻인지 알겠다...
일단... 내가 문제를 또 잘못 이해한 것이 맞았다. 사전 순으로 가장 뒷서는 것 즉, 가장 큰 숫자를 최대한 앞으로 당겨와야한다는 의미라고 한다. 난 그냥 2개씩 비교하여 큰 것을 앞으로 가져오라는 건줄...
그리고 가장 큰 수의 인덱스에서 현재 위치가 될 때까지 1을 감소시켜가며 swap을 해주면 되는 것이다. 그러면 가장 큰 수는 현재 위치로 이동할 수 있다. (아까 앞에서 한 말이 이런 뜻이였구나)
이 분도 말씀하시기를...
아무리 앞에 있는 것을 먼저 바꿔도 뒤에 있는 것 하나를 가져오는 것이 사전 순으로는 뒤에 있는 것이라고 한다.
ㅠㅠ 문제를 이해하기도 힘들다...
아직 나는 많이 부족한 것 같다...
계속 열심히 하자~!!!!!
'백준 > C++' 카테고리의 다른 글
[C++] 백준 2752번 세수정렬 (2) | 2023.12.23 |
---|---|
[C++] 백준 1940번 주몽 (4) | 2023.12.22 |
[C++] 백준 2776번 암기왕 (4) | 2023.12.20 |
[C++] 백준 2693번 N번째 큰 수 (0) | 2023.12.19 |
[C++] 백준 1946번 신입 사원 (2) | 2023.12.18 |