2668 숫자고르기

문제

세로 두 줄, 가로로 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)을 나타내는 정수 하나가 주어진다. 그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

출력

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

====

문제 풀이

일단 N의 값이 100 이하라 로직 복잡성이 높아도 괜찮다고 판단

인덱스 처음부터 탐색해가면서 해당 인덱스부터 출발하였을 때 끝에 도착하는 지점이 출발 점과 같은지 체크.

이때 출발점과 같은 점으로 도착했다면 그간 탐색헀던 모든 점들에게 성공했다는 것을 부여하여 이후 다음 인덱스 탐색시에는 굳이 또 탐색하지 않도록 해줌

성공했던 요소들은 성공 배열에 담아두어 기록해둔 뒤 최종적으로 그 모든 점들을 순서대로 출력하면 된다.

const n = input[0];
const arr = input.slice(1).map((v) => Number(v) - 1);

const successArr = [];
const record = Array.from({ length: n }, () => 0); // -1:false, 0:pending, 1:success

record에는 각 인덱스별로 -1,0,1 로 실패,대기,성공을 기록해두었다. 

인덱스별로 탐색을 진행할 때 방문 체크와 최종적으로 성공했을 때 탐색한 점들에 성공을 기록하는 용도로 visit라는 Set을 활용함.

현재 인덱스부터 출발하여 다음 요소가 아직 방문하지 않았던 점이라면 visit에 넣고 다음 탐색 => DFS 방식

만약 방문했었던 점인데 이게 출발점과 같다면 성공한 것이므로 성공 배열에 넣어줌과 동시에 record에 방문했던 점들을 1 기록

방문했던 점이 처음과 같지 않다면 -1 기록. 

for (let currentNum = 0; currentNum < n; currentNum++) {
    if (record[currentNum] !== 0) continue;
    const visit = new Set([currentNum]);

    const search = (cur) => {
        const next = arr[cur];
        if (visit.has(next)) {
            if (next === currentNum) {
                const temp = [...visit];
                for (const num of temp) {
                    record[num] = 1;
                }
                successArr.push(temp);
                return;
            } else {
                record[currentNum] = -1;
                return;
            }
        } else {
            visit.add(next);
            search(next);
        }
    };
    
    search(currentNum);
}

이제 성공했던 점들의 모임인 successArr을 flat으로 평평하게 만들어 준 뒤 그것의 길이와 요소들을 정렬하여 출력했다.

그런데 생각해보니 record의 값이 1인 인덱스를 answer에 index+1씩 넣어주고 

unshift로 answer의 길이를 answer 맨 앞에 넣어주면 그것도 또 답이 되어 successArr이 필요가 없긴하다.

정답 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = input[0];
const arr = input.slice(1).map((v) => Number(v) - 1);

const successArr = [];
const record = Array.from({ length: n }, () => 0); // -1:false, 0:pending, 1:success
for (let currentNum = 0; currentNum < n; currentNum++) {
    if (record[currentNum] !== 0) continue;
    const visit = new Set([currentNum]);

    const search = (cur) => {
        const next = arr[cur];
        if (visit.has(next)) {
            if (next === currentNum) {
                const temp = [...visit];
                for (const num of temp) {
                    record[num] = 1;
                }
                successArr.push(temp);
                return;
            } else {
                record[currentNum] = -1;
                return;
            }
        } else {
            visit.add(next);
            search(next);
        }
    };
    
    search(currentNum);
}

const answer = [];
const temp = successArr.flat(1).sort((a, b) => a - b);
answer.push(temp.length);
temp.forEach((v) => answer.push(v + 1));
console.log(answer.join('\n'));