https://school.programmers.co.kr/learn/courses/30/lessons/131130
문제가 정말 길다.
하지만 우리가 봐야할 것은
입력에서 주어지는 나열된 상자를 보면 된다.
이 상자를 순회하면서 문제에서 주어진 방식대로 상자 안의 숫자로 계속 상자를 방문처리하면서 그룹을 나누고 만약 그룹이 2개보다 작다면 0점이고 아니라면 그룹 수 중에 제일 많은 수와 그 다음으로 많은 수를 곱해서 반환해주면 된다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 특정 시작점에서 그룹의 크기를 찾는 함수
int find_group(int start, vector<int>& cards, vector<bool>& visited) {
int group_size = 0; // 그룹 크기 초기화
int current = start; // 현재 상자를 시작 상자로 설정
while (!visited[current]) { // 현재 상자가 방문되지 않은 동안 반복
visited[current] = true; //방문처리
current = cards[current] - 1; // 상자 안의 숫자를 통해 다음 상자 선택
group_size += 1; // 그룹 크기를 증가시킴
}
return group_size;
}
int solution(vector<int> cards) {
int n = cards.size(); // 상자의 수
vector<bool> visited(n, false); // 방문 여부를 저장
vector<int> group_sizes; // 각 그룹의 크기를 저장
// 모든 상자에 대해 그룹을 찾음
for (int i = 0; i < n; ++i) {
if (!visited[i]) { // 현재 상자가 방문되지 않았다면
int group_size = find_group(i, cards, visited); // 그룹의 크기를 찾음
group_sizes.push_back(group_size); // 그룹 크기를 벡터에 추가
}
}
// 그룹 크기를 내림차순으로 정렬
sort(group_sizes.rbegin(), group_sizes.rend());
// 최대 점수를 계산
if (group_sizes.size() < 2) { // 그룹이 2개 미만이면
return 0; // 점수는 0
} else {
return group_sizes[0] * group_sizes[1]; // 가장 큰 두 그룹의 크기를 곱한 값이 최대 점수
}
}
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
[프로그래머스][LV2][C++]두원 사이의 정수 (0) | 2024.06.27 |
---|---|
[프로그래머스][LV2][C++]과제 진행하기 (0) | 2024.06.26 |
[프로그래머스][LV2][C++]점 찍기 (0) | 2024.06.24 |
[프로그래머스][LV2][C++] (0) | 2024.06.21 |
[프로그래머스][LV2][C++]광물 캐기 (0) | 2024.06.20 |