[ SWEA 8191 ] 만화책 정렬하기 (C++)

SWExpertAcademy 의 만화책 정렬하기(8191 /  D5) 문제이다.

[ 문제풀이 ]

실제로 구현한 코드의 내용에 비해서 오랫동안 생각을 했던 문제이다.

정말 간단한 예시를 통해서 어떻게 계산하는게 좋을지 생각을 해보자..

예를 들어서 2권의 책이 [ 1, 2 ] 의 순서대로 꽂혀있다. 몇 번 훑어야 할까 ?? 한 번만 훑어서 책을 정리할 수 있다.

그렇다면 [ 2, 1 ] 의 순서대로 꽂혀있다면 ?? 두 번을 훑어야 한다.

위의 2개의 예시는 너무나도 간단하고 쉬운 예시라서 딱 보면 답을 알 수 있지만, 지금부터는 왜 답이 그렇게 되는지 생각을

해보자.

먼저, [ 1 , 2 ] 의 경우를 생각해보자.

그럼 1번 책을 정리하면서 2번 책의 위치를 계산을 해보자. 1번 책은 1번칸에 꽂혀있는 상태인데, 2번 책은 2번 칸에 꽂혀있는 상태이다. 쉽게 이야기하면 "2번 책의 위치가, 1번 책의 위치보다 더 크기 때문에 한 번에 정리가 가능" 하다는 것이다.

[ 1 , 3 , 4 , 2 ] 의 경우를 생각해보자.

1번 책은 1번 위치에 있고, 2번 책은 4번 위치에 있다. 이 경우에도, 2번 책의 위치가, 1번 책의 위치보다 더 크기 때문에 한 번에

정리가 가능하다. 물론, 3, 4 번 책 까지 정리를 하려면 한번 더 정리를 해줘야 하지만, 1번책과 2번책만 비교했을 때는 그렇다.

그럼 반대로 [ 2 , 1 ] 의 경우를 생각해보자.

이 경우 2번책은 1번에 위치, 1번책은 2번에 위치한다. 즉, 2번책의 위치가 1번책의 위치보다 더 작기 때문에 한 번에 정리를

할 수 없다. 즉 ! 이 경우에 정리해야 할 횟수가 ++ 되는 것이다.

이런식으로 모든 값을 비교할 필요 없이, 나와 인접한 값 하나만 비교를 하면서 답을 구해나갈 수가 있다.

위에서 말했던 [ 1, 3, 4, 2 ] 로 한번 해보자.

1번책 = 1번위치

2번책 = 4번위치

3번책 = 2번위치

4번책 = 3번위치

1번 책과 2번책을 비교해보자. 1번책의 위치 < 2번책의 위치 이므로 한번에 정리가 가능하다.

2번 책과 3번책을 비교해보자. 2번책의 위치 > 3번책의 위치 이므로 한번에 정리가 되지 않는다. 즉, 여기서 한 번 훑어줘야 한다.

3번 책과 4번책을 비교해보자. 3번책의 위치 < 4번책의 위치 이므로 한번에 정리가 가능하다.

즉, 위의 경우는 한번만 훑어주면 된다 ! 라고 하기에는 딱 봐도 한번만에 정리가 되지 않는다. 정확하게는 2번을 훑어줘야

정리가 가능하다. 위에서 계산한 것과 실제 정답이 다른 이유는 무조건 한 번은 훑어줘야 하기 때문이다.

책이 [ 1 , 2 , 3, 4 ] 로 있다고 가정했을 경우, 0번 훑어서 정리를 할 수 있을까?? 아니다 ! 무조건 한 번은 훑고 시작해줘야 한다.

따라서 처음에 훑는 과정 1번 + 중간에 2번책과 3번책을 비교하면서 얻어낸 훑는 과정 1번으로 총 2번을 훑어야 한다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<algorithm>
 
#define endl "\n"
#define MAX 200010
using namespace std;
 
int N, Answer;
int Arr[MAX];
 
void Initialize()
{
    Answer = 1;
    memset(Arr, 0, sizeof(Arr));
}
 
void Input()
{
    cin >> N;
    for(int i = 1; i <= N; i++)
    {
        int a; cin >> a;
        Arr[a] = i;
    }
}
 
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        if (Arr[i + 1] != 0 && Arr[i] > Arr[i + 1]) Answer++;
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}