JUNGOL 실력키우기 1459 : 숫자고르기

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.

 

 

이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이 때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로 밑에는 정수 3과 1이 있으므로 두 집합이 일치한다. 그러나, 이 경우에 뽑힌 정수의 개수는 최대가 아니므로 답이 될수 없다.

 

입력의 첫째 줄에는 N(1≤N≤100)을 나타내는 정수 하나가 주어진다.
그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

첫째 줄에 뽑힌 정수들의 개수를 출력하고 그 다음 줄부터는 뽑힌 정수들을 작은 수부터 큰 수의 순서로 한 줄에 하나씩 출력한다.

7 3 1 1 5 5 4 6

3 1 3 5

---

이전 문제가 상당히 쉬웠는데 갑자기 어렵게 느껴지는 문제가 등장했습니다.

우선 처음부터 재귀적으로 생각하는 건 어려우니 반복문으로 해결할 수 있는 방안이 있는지 찾아보죠.

우선 문제에서 주어진 예제를 분석하면 첫째 줄 기준으로 둘째 줄의 함수를 만들면 (1, 3), (2, 1), (3, 1), (4, 5), (5, 5), (6, 4), (7, 6)이 나오고 두번째 줄 기준으로 첫번 째 줄의 함수를 만들면(3, 1), (1, 2), (1, 3), (5, 4), (5, 5), (4, 6), (6, 7)이 됩니다.

이때, (1, 3), (3, 1), (5, 5)는 두 함수에 공통적으로 존재하게 됩니다. 즉, 1, 3, 5가 결과가 되게 됩니다.

이것을 바탕으로 2개의 for문을 중복하면 될 것 같습니다.

#include <iostream>
#include <set> 
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    // 두 개의 배열을 준비한다.
    int arr1[100], arr2[100];
    for (int i = 0; i < n; ++i)
    {
        arr1[i] = i + 1;
        cin >> arr2[i];
    }
 
    // 결과를 저장할 집합을 준비한다.
    // 중복 없이, 정렬된 결과를 얻을 수 있다.
    set<int> result;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            // 1번 배열의 값에서 2번 배열의 값이 있을 때
            // 2번 배열에서 1번 배열로 동일한 값이 있다면
            // 해당 값은 유효하다고 판단한다.
            if (arr1[i] == arr2[j] &&
                arr2[i] == arr1[j])
            {
                result.insert(arr1[i]);
            }
        }
    }
 
    // 개수 출력
    cout << result.size() << endl;
    // 순서대로 출력한다.
    for (int d : result)
    {
        cout << d << endl;
    }
}

우선 결과에 나온 데이터와 제가 생각한 부분의 차이를 확인해야 할 것 같습니다.

첫째 줄 -> 둘째 줄: (1, 7), (2, 2), (3, 7), (4, 6), (5, 4), (6, 3), (7, 6)

둘째 줄 -> 첫째 줄: (7, 1), (2, 2), (7, 3), (6, 4), (4, 5), (3, 6), (6, 7)

제 이론상으로는 결과는 1개, 2가 나오게됩니다. 그런데 요구하는 정답은 4개, 2, 3, 6, 7이네요.

단순히 재귀를 통해 위 과정을 반복한다고 했을 때 요구하는 답을 찾을 수가 없군요. 약간 다르게 생각해봐야 할 것 같습니다.

실패한 패턴을 다시 파악해보면 첫번째 입력에서나온 두번째 값을 다시 첫번째의 입력으로 하는 것을 반복하며 집합을 만들 때 두 집합이 동일하면 결과에 추가하면 될 것 같습니다.

집합 A와 B가 있을 때, 첫째줄의 입력을 A에 넣고 그때의 둘째줄 값을 B에 넣는다고 하고 B의 입력값을 다시 A의 입력으로 넣는 것을 반복하다 A와 B가 동일해지는 시점에 결과 집합에 A집합의 값을 추가합니다.

입력 : 1, 7, 6, 3, 7 ...

  A  : 1, 7, 6, 3, 7 ... 

  B  : 7, 6, 3, 7, 6 ...

위와 같이 진행되게 됩니다. 여기에서 A와 B가 중복되지 않는 Set을 사용할 경우 A{1, 3, 6, 7}, B{3, 6, 7}로 A와 B는 같지 않게 됩니다.

이후 다시 입력을 2부터 시작하면

입력 : 2 2 2 ...

  A  : 2 2 2 ...

  B  : 2 2 2 ...

위의 경우에도 동일하게 중복되지 않는 Set을 사용하면 A{2}, B{2}로 A와 B가 같게 되므로 결과 집합에 2를 추가하면 됩니다.

그런데 여기에서 정상적인 프로그램으로 만드려면 종료 조건을 생각해야하며 최대 입력의 개수만큼만 처리하면 될 것입니다.

만약 잘 모르겠다면 사이클을 만들지 않으면서 최대한 긴 연결 고리를 생성한다고 생각하시면 됩니다.

추가적으로 입력 전에는 두 집합이 동일했으나 추가 입력이후 두 집합이 달라질 수 있으므로 매 입력시마다 집합을 비교해야할 것 같습니다.

#include <iostream>
#include <set> 
 
using namespace std;
 
void FindDupleSet(set<int> firstSet, set<int> secondSet,
    int from = 0, int stage = 0);
 
// 결과를 저장할 집합을 준비한다.
// 중복 없이, 정렬된 결과를 얻을 수 있다.
set<int> result;
 
int n;
// 두 개의 배열을 준비한다.
int arr1[100], arr2[100];
 
int main()
{
    cin >> n;
    
    for (int i = 0; i < n; ++i)
    {
        arr1[i] = i + 1;
        cin >> arr2[i];
    }
    
    for (int i = 0; i < n; ++i)
    {
        FindDupleSet(set<int>(), set<int>(), i);
    }
 
    // 개수 출력
    cout << result.size() << endl;
    // 순서대로 출력한다.
    for (int d : result)
    {
        cout << d << endl;
    }
}
 
// 두 집합에 중복되는 값의 집합을 찾는다.
void FindDupleSet(set<int> firstSet, set<int> secondSet,
    int from, int stage)
{
    // 최대 입력단계 만큼만 유효할 것.
    if (stage == n) return;
 
    // 임시 집합에 데이터를 삽입한다.
    firstSet.insert(arr1[from]);
    // arr1이 가진 값 - 1이 arr2의 위치가 된다.
    secondSet.insert(arr2[arr1[from] - 1]);
 
    // 두 집합이 같으면 결과 집합에 데이터를 넣는다.
    if (firstSet == secondSet)
    {
        for (int d : firstSet)
        {
            result.insert(d);
        }
    }
 
    // arr2의 값을 arr1의 인덱스로 바꿔 반복 진행한다.
    FindDupleSet(firstSet, secondSet, arr2[arr1[from] - 1] - 1, stage + 1);
}

JUNGOL) 문제은행) 실력키우기) 숫자고르기