99클럽 코테스터디 38일차 TIL 프로그래머스- 혼자 놀기의 달인

혼자 놀기의 달인

프로그래머스 Level 2 Greedy
문제 링크

프로그래머스

 

문제 설명

주어진 카드를 순서대로 탐색하여 각 그룹으로 묶고, 전체 그룹이 하나라면 0,
그룹이 두개 이상일 때는 그룹 중 크기가 가장 큰 두개의 그룹의 곱을 찾는 문제.

 

문제 풀이

cards 의 맨 앞부터 순차적으로 탐색하여 그룹별 갯수를 세는 방식으로 진행했다.
cards[0] == 8 이면 다음은 cards[8-1] 로 가는 식.

탐색을 마친 후엔, 그룹을 크기가 큰 순서대로, 내림차순으로 정렬해준 뒤, 첫번째, 두번째를 곱해주고,
그룹의 크기가 1 일 경우엔 0을 리턴해줬다.

 

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool visited[101] = {false, };
vector<int> group;

bool compare(int a, int b) {
    return a > b;
}

void game(int cur, int cnt, vector<int> cards) {
    if (visited[cur-1]) {
        group.push_back(cnt);
        return ;
    }
    visited[cur-1] = true;
    game(cards[cur-1], cnt+1, cards);
}

int solution(vector<int> cards) {
    int answer = 0, lim = cards.size();

    for (int i=0; i<lim; i++) {
        if (!visited[cards[i]-1]) game(cards[i], 0, cards);        
    }

    if (group.size() == 1) return 0;

    sort(group.begin(), group.end(), compare);

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

 

Python 코드

def game(cur, cnt, cards, visited, group):
    if visited[cur - 1]:
        group.append(cnt)
        return
    visited[cur - 1] = True
    game(cards[cur - 1], cnt + 1, cards, visited, group)

def solution(cards):
    answer = 0
    lim = len(cards)
    visited = [False] * len
    group = []

    for i in range(lim):
        if not visited[cards[i] - 1]:
            game(cards[i], 0, cards, visited, group)

    if len(group) == 1:
        return 0

    group.sort(reverse=True)

    return group[0] * group[1]

 

회고

 

cpp 의 sort() 를 사용할 때, compare 함수를 직접 구현하여 사용하는데 좀 익숙해 진 것 같다.

알고리즘 스터디를 하면서 많이 얻어가는 것 같아 다행이다.