백준 15594번 Out of Place

문제 링크입니다: https://www.acmicpc.net/problem/15594

저는 복잡하게 풀었지만 같은 학교 학우이신 Greent55님(https://blog.naver.com/pasdfq/221368719157)은 간단하게 푸셨으니 참고하시는 것을 추천드립니다!

알고리즘은 아래와 같습니다.

1. 이상적인 배치를 구한 다음에 현재 배치와 다르게 서 있는 소들을 표시합니다.

2. 이상적인 배치와 동일한 위치에 있는 소들은 움직일 필요가 없습니다.

3. 현재 옮길 소 이전의 소들은 이상적인 위치에 있으므로 옮길 소 오른쪽에 있는 소들만 비교해보면 됩니다.

-> 그리디하게 접근할 수 있었던 이유

4. 오른쪽에 배치된 소들 중 옮길 소가 위치한 곳에 배치해야하는 소를 찾고 서로 위치를 바꿔줍니다.

5. 정렬이 완료되면 swap한 횟수를 출력해줍니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        vector<int> v(N);

        for (int i = 0; i < N; i++)

                 cin >> v[i];

 

        //이상적인 배치

        vector<int> sorted(N);

        for (int i = 0; i < N; i++)

                 sorted[i] = v[i];

        sort(sorted.begin(), sorted.end());

 

        //제자리에 있는 소들 확인

        vector<bool> inPlace(N);

        for (int i = 0; i < N; i++)

                 if (v[i] != sorted[i])

                         inPlace[i] = false;

                 else

                         inPlace[i] = true;

 

        int idx = 0;

        long long result = 0;

        while (1)

        {

                 if (inPlace[idx])

                 {

                         idx++;

                         continue;

                 }

                

                 int swapIdx = idx + 1;

                 while (1)

                 {

                         //정렬이 완료되었거나

                         //바꿀 위치를 확인

                         if (swapIdx >= N || (!inPlace[swapIdx] && sorted[swapIdx] == v[idx]))

                                 break;

                         swapIdx++;

                 }

                 //정렬 완료

                 if (idx >= N || swapIdx >= N)

                         break;

 

                 inPlace[swapIdx] = true;

                 swap(v[idx], v[swapIdx]);

                 result++;

        }

 

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~