[BAEKJOON] 백준 29615: 알파빌과 베타빌 (C#)

문제 링크

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

 

 

문제

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

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

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

 

 

입력

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

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

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

 

 

출력

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

 

 

 

통과한 답안

namespace _29615
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            int N = int.Parse(inputs[0]);
            int M = int.Parse(inputs[1]);
            int[] arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int[] friends = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int[] firstArr = new int[M];
            Array.Copy(arr, firstArr, M);
            Array.Sort(friends);

            int cnt = 0;
            for (int i = 0; i < friends.Length; i++)
            {
                if (!firstArr.Contains(friends[i]))
                {
                    cnt++;
                }
            }

            Console.WriteLine(cnt);
        }
    }
}

 

길이가 N인 전체 대기 명단과 길이가 M인 친구 대기 명단이 있을 때,

이들이 모두 앞으로 오도록 교환하는 횟수를 계산하는 문제이다.

 

다시 말해서 인덱스가 0부터 M - 1까지는 친구의 번호가 들어가야 된다는 문제인데

이를 해결하기 위해서 전체 대기 명단을 길이가 M인 새로운 대기 명단으로 자르고,

이 대기 명단과 친구 대기 명단을 비교하여 없는 친구의 번호 수를 구했다.

이 번호의 수가 교환해야되는 횟수가 된다.