[C++] 프로그래머스 혼자 놀기의 달인

프로그래머스 혼자 놀기의 달인 문제 바로가기

사용 알고리즘

• 구현

 

풀이

문제를 짧게 세 줄로 요약하자면 이렇다.

1. 숫자는 이동할 배열 원소의 순번이다.

2. 계속 숫자를 재귀처럼 이동하는데, 끝날 때까지의 이동한 횟수를 센다.

3. 한번 쭉 이동한 것을 그룹이라고 한다. 모든 그룹 중에서 가장 횟수가 큰 2개의 곱이 정답이다. 

 

문제에서 주어진 테스트 케이스를 예시로 살펴보자.

배열의 원소 [8, 6, 3, 7, 2, 5, 1, 4]  

 

여기서 8을 시작으로 그룹을 지어보면,

1. 배열의 8번째 인덱스는 4이다.

2. 배열의 4번째 인덱스는 7이다.

3. 배열의 7번째 인덱스는 1이다.

4. 배열의 1번째 인덱스는 8이다. (되돌아옴)

이렇게 꼬리 물기를 하면 된다. 첫번째 그룹은 [8, 4, 7, 1]이 된다.

 

운이 좋게 다음에 있는 6은 사용하지 않았으므로 두번째로 그룹을 지을 수 있다.

1. 배열의 6번째 인덱스는 5이다.

2. 배열의 5번째 인덱스는 2이다.

3. 배열의 2번째 인덱스는 6이다. (되돌아옴)

두번째 그룹은 [6, 5, 2]이다.

 

다음에 있는 3은 자기 자신을 가리키므로 혼자 그룹을 짓는다.

세번째 그룹은 [3]이다.

 

자 그럼 정리하자면 그룹은 3개이다.

이 중에 첫번째 그룹의 인원수 4와 두번째 그룹의 인원수 3이 가장 크므로 둘의 곱인 12가 답이 된다.

 

※ 추가로 예외 처리해야 할 사항이 몇 가지 있다.

 

1. 중복을 처리해야 한다.

만약 위의 예시에서 8을 시작으로 한 그룹을 만들고, 4를 시작으로 한 그룹을 만드는 건 똑같은 그룹을 만드는 것이다.

이유는 그룹은 무조건 순환되기 때문이다.

그러니 그룹의 내용이 같을 수밖에 없다.

 

2. 모든 원소끼리 순환된다면 결과는 0으로 처리해야 한다.

이것은 문제 설명에 1번 그룹을 제외하고 남는 상자가 없으면 0으로 처리하라고 쓰여있는 부분을 말한다.

 

 3. 문제에 1번 그룹, 2번 그룹의 곱이라지만 사실은 가장 큰 그룹끼리의 곱이다.

 

풀이 코드

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> cards) {
    int answer = 0;
    
    vector<int> res;
    vector<int> card(cards.size()+1, 0);
    bool visited[101] = {0,}; 
    
    // 1부터 시작이라 편의상 전처리
    for(int i = 1; i <= cards.size(); i++)
        card[i] = cards[i-1];
    
    for(int i = 1; i < card.size(); i++) {
    	// 중복 제거
        if(visited[card[i]])
            continue;
        
        int cnt = 0;
        int num = card[i];
        
        // 그룹 카운팅
        while(!visited[num]) {
            visited[num] = true;
            num = card[num];
            cnt++;
        }
        
        res.push_back(cnt);
    }
    
    sort(res.begin(), res.end(), greater<>());
    
    if(res.size() == 1) 
        return 0;
    
    answer = res[0] * res[1];
    
    return answer;
}

 

후기

문제 설명이 조금 이해하기 어렵게 쓰여있는 것 같다.

실제로 문제 내용은 레벨 2 치곤 정말 별 거 없었고 설명을 이해하는데 시간이 더 오래 걸렸다.