[Baekjoon/C++] 29615번 - 알파빌과 베타빌

[백준] Baekjoon Online Judge

문제로 이동

 

문제

민규와 친구들은 바로 옆에 붙어있는 두 빌라, 알파빌과 베타빌에 살고 있다. 이 두 빌라 중 알파빌은 싼값에 좋은 빌라라서 너무 인기가 많아 입주하려는 사람들이 줄을 선다. 민규의 친구들 역시 대기 번호를 받아 알파빌의 대기 명단에 적혀있다. 알파빌 입주에 실패한 친구들은 어쩔 수 없이 조금 더 비싼 베타빌에 들어가게 될 것이다. 이를 안타까워한 민규는 더 많은 친구를 알파빌에 입주시키기 위해 집주인 몰래 대기 명단을 바꾸려고 한다.

대기 명단에는 입주하려는 사람들의 대기 번호가 입주하는 순서대로 왼쪽에서 오른쪽으로 적혀 있으며, 대기 번호는 1번부터 N번까지의 서로 다른 정수이다.

민규는 한 번 명단을 바꿀 때 번호 두 개를 선택해서 서로 위치를 교환할 수 있다. 대기 명단을 너무 많이 바꾸면 집주인이 눈치를 챌 수 있기 때문에, 민규는 가능한 한 최소한으로 명단을 바꾸려고 한다. 민규의 모든 친구가 친구가 아닌 사람들보다 먼저 입주하도록 명단을 바꿀 때, 최소 교환 횟수를 출력하자.

 

입력

첫 번째 줄에 대기 명단에 적힌 수의 개수 N과 민규 친구의 수 M이 공백으로 구분되어 주어진다. (1 ≤ M ≤ N ≤ 1000)

두 번째 줄에 대기 명단에 적힌 N개의 정수가 주어진다.

세 번째 줄에 민규 친구의 대기 번호를 나타내는 M개의 정수가 주어진다.

 

출력

모든 친구들이 먼저 입주할 수 있도록 명단을 바꾸는 최소 횟수를 출력한다.

 

---

풀이

#include <iostream>
using namespace std;

int N, M;
int arr[1001];
int frd[1001];
bool check[1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> arr[i];

    for (int i = 0; i < M; i++) {
        cin >> frd[i];

        // 친구의 대기 순서 찾기
        for (int j = 0; j < N; j++) {
            if (arr[j] == frd[i]) {
                // 다른 사람보다 먼저 들어갈 수 있는 범위에 속했을 때
                if (j < M) {
                    frd[i] = -1;
                    check[j] = true;
                }

                break;
            }
        }
    }

    int cnt = 0;

    for (int i = 0; i < M; i++) {
        // 순서를 바꿀 필요가 없을 때
        if (frd[i] == -1) continue;

        // 순서 바꾸기
        for (int j = 0; j < N; j++) {
            if (!check[j]) {
                check[j] = true;
                cnt++;

                break;
            }
        }
    }

    // 출력
    cout << cnt << '\n';

    return 0;
}

 

    for (int i = 0; i < M; i++) {
        cin >> frd[i];

        // 친구의 대기 순서 찾기
        for (int j = 0; j < N; j++) {
            if (arr[j] == frd[i]) {
                // 다른 사람보다 먼저 들어갈 수 있는 범위에 속했을 때
                if (j < M) {
                    frd[i] = -1;
                    check[j] = true;
                }

                break;
            }
        }
    }

 친구의 대기 번호를 입력 받는 부분의 코드이다. 만약 모든 친구를 앞으로 보낸다면 0부터 M - 1까지의 칸에는 친구의 번호가 위치하게 된다. 즉, 배열에서 M보다 작은 인덱스에 위치하는 친구의 번호의 순서를 바꾸지 않아야 명단을 바꾸는 최소 횟수를 구할 수 있다. 이때 바꿀 필요가 없는 번호를 표시하기 위해 해당하는 친구의 번호를 -1로 초기화하고, check[]에 위치가 확정되었음을 표시하도록 했다.

 

    for (int i = 0; i < M; i++) {
        // 순서를 바꿀 필요가 없을 때
        if (frd[i] == -1) continue;

        // 순서 바꾸기
        for (int j = 0; j < N; j++) {
            if (!check[j]) {
                check[j] = true;
                cnt++;

                break;
            }
        }
    }

 모든 친구들이 먼저 입주할 수 있도록 명단을 바꾸는 부분의 함수이다.

 frd[i]가 -1이라면 순서를 바꿀 필요가 없는 친구이므로 continue를 하도록 했다.

 for문으로 명단의 앞부터 탐색하여 친구가 아닌 사람이 위치한 칸을 발견하면 순서를 바꾸고, check[j]를 true로 바꾼다.

 

++++++++

#include <iostream>
using namespace std;

int N, M;
int arr[1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> arr[i];

    int cnt = 0;
    for (int i = 0; i < M; i++) {
        int n;
        cin >> n;

        for (int j = 0; j < N; j++) {
            if (arr[j] == n) {
                if (j < M) cnt++;

                break;
            }
        }
    }

    cout << M - cnt << '\n';

    return 0;
}

 글을 작성하며 생각해보니 순서를 바꾸는 횟수만 구하면 되므로 배열에서 직접 순서를 바꿀 필요 없다는 것을 깨달았다. 0 ~ M - 1 사이의 인덱스에 위치하지 않은 친구의 수만 구하면 되므로 위와 같이 코드를 고쳤다.