백준 1015번 C++ 수열 정렬

수열 정렬

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

P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.

배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.

코드

#include <iostream>
using namespace std;
int main() {
    int N, arr[51], P[51];
    cin>>N;
    for(int i=0; i<N; i++) {
        cin>>arr[i];
    }
    int minIdx=0;
    for(int i=0; i<N; i++) {
        int min=1001;
        for(int j=0; j<N; j++) {
            if(arr[j]<min) {
                min=arr[j];
                minIdx=j;
            }
        }
        P[minIdx]=i;
        arr[minIdx]=1001;
    }
    for(int i=0; i<N; i++) {
        cout<<P[i]<<" ";
    }
    return 0;
}

최소값을 찾아서 최소값의 위치에 i를 넣어준다

사전순으로 해야하기 때문

그리고 최소값의 위치에 해당하는 원래 배열 원소에 1001 대입

문제에서 주어지는 숫자는 1000 이하의 자연수라고 했으므로 1001로 설정해놓으면

중복이 걸릴 일이 없다

가벼운 마음으로 시작했는데

결론부터 말하자면

4달 전의 나는 알고리즘 처음 시작했을 땐데 ㅋㅋㅋㅋ

12월~1월 이때는 진짜 한 것도 아니었다

저 때는 진짜 ㅋㅋㅋㅋ 런타임 에러 뜬 코드 보니 거의 코미디

#include <iostream>
 
using namespace std;
 
int main() {
    int N = 1;
    int* A = new int[N];
    int* B = new int[N];
    int P[3] = { 0, 1, 2 };
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        B[P[i]] = A[i];
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (A[i] >= A[j]) {
                int temp_a;
                temp_a = A[j];
                A[j] = A[i];
                A[i] = temp_a;
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (A[i] == B[j]) {//i=2, j==1
                P[j] = i;
 
                if (j > 0 && P[j - 1] == P[j])
                    P[j] = ++i;
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        cout << P[i] << " ";
    }
    cout << endl;
 
    return 0;
}

용케 여기까지 왔구나...

난 알고리즘 공부 이번 달부터 시작했다고 봐도 무방할 것 같다...

저때는 다들 알고리즘 스터디 하길래 할 것도 없고 궁금해서 들어가봤던 건데 ㅎㅎ

아무튼 오늘의 틀렸습니다는 사전순으로 하지 않아서 얻은 것이다

왜 틀린 거야ㅡㅡ 하면서 게시판 들어갔는데 사전순으로 정리해야 된다고...

문제를 제대로 읽자