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

 

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

 

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

프로그래머스

---

 

해결전략

 

구현

 

풀이보다 문제를 해석하기가 더 힘든 문제다..

 

---

 

정답코드

 

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> cards) {
    
    int n = cards.size(); // 전체 카드수

    if (n < 1) return 0; // 카드가 한 개만 있는 경우

    vector<int> scores; // 상자에 담긴 카드 수(=점수)를 기록하는 배열
    int i = 0;
    while(n > 0)
    {
        set<int> mySet; // 상자 그룹
        while (true)
        {
            if (cards[i] == -1){
                i++;
                break;
            }

        	if (mySet.find(cards[i]) == mySet.end()) { // 상자 그룹에 이미 넣은 수인지 확인
                mySet.insert(cards[i]);
                
                int tmp = i;
                i = cards[tmp] - 1; // 다음 카드를 찾도록 i 업데이트
                cards[tmp] = -1;    // 상자에 넣은 수를 -1로 바꾸어 다음번에 안 넣도록 함 
                n--;                // 카드수-- 
            }
            else {
                break;
            }
        }
        
        scores.push_back(mySet.size()); // mySet의 크기는 상자에 담긴 카드 수. 이것은 점수이고 이것을 배열에 담음.
    }

    if (scores.size() == 1) return 0; // 첫 시도에 모든 상자를 연 경우

    sort(scores.rbegin(), scores.rend()); // 내림차순으로 정렬

    return scores[0] * scores[1];
}

int main()
{
    vector<int> testcase1 = { 8,6,3,7,2,5,1,4 }; // 12
    vector<int> testcase2 = { 10, 5, 6, 7, 8, 9, 1, 2, 3, 4 }; // 12

    cout << solution(testcase1) << "\n";
    cout << solution(testcase2) << "\n";

    return 0;
}

 

---

 

 

정답코드 다른 풀이

 

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

int solution(vector<int> cards)
{
    int n = cards.size();

    vector<bool> ch(n + 1, false); // 카드를 골랐는지 체크하는 bool 배열
    vector<int> scores;                      // 상자에 담긴 카드 수(=점수)를 기록하는 배열

    for (int i = 0; i < n; i++)
    {
        int now = cards[i];
    	int cnt = 0;
        while (false == ch[now]) // 아직 고른 카드가 아니라면
        {
            ch[now] = true;        // 선택한걸 체크
            now = cards[now - 1];  // 현재 카드 업데이트
            cnt++;                 // 개수++
        }

        if (cnt > 0) {
            scores.push_back(cnt); // 점수 추가
        }
    }

    if (scores.size() == 1) return 0; // 첫 시도에 모든 상자를 연 경우


    sort(scores.rbegin(), scores.rend()); // 내림차순 정렬

	return scores[0] * scores[1];
}

 

---