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

https://school.programmers.co.kr/learn/courses/30/lessons/131130

풀이

재귀를 생각했으나 구현도 어렵고 size가 100이라 어림없다.

 

while문으로 dfs를 구현해 해결할 수 있는 풀이가 있어 참고했다. 

while문을 사용해 현재 위치 cur이 아직 방문하지 않은 상태라면 현재 위치를 계속 업데이트 하는 로직이다. 

고른 카드는 vis 벡터에서 true 처리 해주고 cnt++ 로 고른 카드를 카운트해준다.

 

while 문 종료 후에 res 벡터에 push_back 하는데, 이때 cnt가 0이라면 이미 고른 카드에서 시작한 것이므로 무시한다.

 

for문 종료 후 sort(res.begin(), res.end(), greater<int>()) 로 내림차순 정렬 후 res에 2개 이상의 값이 존재한다면 0, 1인덱스 값을 곱해 리턴한다. 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> cards)
{
    int n = cards.size();
    vector<bool> vis(n+1, false);
    vector<int> res;
    for(int i=0;i<n;i++)
    {
        int cur = cards[i], cnt = 0;
        while (!vis[cur]) {   
            //아직 고른 카드가 아니라면
            vis[cur] = true; //골랐음 체크
            cur = cards[cur-1]; //현재카드 갱신
            cnt++; //개수++
        }
        if (cnt) res.push_back(cnt); //묶음이면 추가
    }
    sort(res.begin(), res.end(), greater<int>()); //내림차순 정렬
    if (res.size() > 1) return res[0]*res[1]; //묶음이 2개이상이면
    return 0;
}