프로그래머스 | Level 2 | 혼자 놀기의 달인
Programmers | Level 2 | 혼자 놀기의 달인
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Simulation
Description
혼자서도 잘 노는 범희는 어느 날 방구석에 있는 숫자 카드 더미를 보더니 혼자 할 수 있는 재미있는 게임을 생각해냈습니다.
숫자 카드 더미에는 카드가 총 100장 있으며, 각 카드에는 1부터 100까지 숫자가 하나씩 적혀있습니다. 2 이상 100 이하의 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드들을 준비하고, 준비한 카드의 수만큼 작은 상자를 준비하면 게임을 시작할 수 있으며 게임 방법은 다음과 같습니다.
준비된 상자에 카드를 한 장씩 넣고, 상자를 무작위로 섞어 일렬로 나열합니다. 상자가 일렬로 나열되면 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호를 붙입니다.
그 다음 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인합니다. 다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자를 확인합니다. 마찬가지로 숫자에 해당하는 번호를 가진 상자를 계속해서 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복합니다.
이렇게 연 상자들은 1번 상자 그룹입니다. 이제 1번 상자 그룹을 다른 상자들과 섞이지 않도록 따로 둡니다. 만약 1번 상자 그룹을 제외하고 남는 상자가 없으면 그대로 게임이 종료되며, 이때 획득하는 점수는 0점입니다.
그렇지 않다면 남은 상자 중 다시 임의의 상자 하나를 골라 같은 방식으로 이미 열려있는 상자를 만날 때까지 상자를 엽니다. 이렇게 연 상자들은 2번 상자 그룹입니다.
1번 상자 그룹에 속한 상자의 수와 2번 상자 그룹에 속한 상자의 수를 곱한 값이 게임의 점수입니다.
상자 안에 들어있는 카드 번호가 순서대로 담긴 배열 cards가 매개변수로 주어질 때, 범희가 이 게임에서 얻을 수 있는 최고 점수를 구해서 return 하도록 solution 함수를 완성해주세요.
Constraints
- 2 ≤
cards의 길이 ≤ 100 cards의 원소는 cards의 길이 이하인 임의의 자연수입니다.cards에는 중복되는 원소가 존재하지 않습니다.cards[i]는 i + 1번 상자에 담긴 카드에 적힌 숫자를 의미합니다.
Examples
| cards | result |
|---|---|
[8,6,3,7,2,5,1,4] | 12 |
Solutions
Code
import java.util.*;
class Solution {
public int solution(int[] cards) {
// 우선순위 큐를 사용하여 그룹 크기를 저장하며, 가장 큰 두 그룹의 크기를 곱할 예정
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
boolean[] opened = new boolean[cards.length]; // 상자의 열림 상태를 기록
// 각 상자를 순차적으로 확인하며 그룹을 형성
for (int i = 0; i < cards.length; i++) {
if (!opened[i]) {
int count = 0;
int curr = i;
// 해당 상자를 열고, 카드에 적힌 상자 번호로 이동하며 그룹 형성
while (!opened[curr]) {
count++; // 그룹 내 상자 개수 증가
opened[curr] = true; // 상자를 열었다고 표시
curr = cards[curr] - 1; // 카드에 적힌 번호로 이동
}
pq.add(count); // 형성된 그룹의 크기를 우선순위 큐에 저장
}
}
// 최고 점수 계산 후 반환
if (pq.size() < 2) return 0; // 두 그룹 이상의 그룹이 없을 경우, 점수는 0
return pq.poll() * pq.poll(); // 가장 큰 두 그룹의 크기를 곱하여 점수 계산
}
}
Approaches
이 문제는 주어진 카드 배열을 이용하여 두 그룹을 만들고, 각 그룹의 크기를 곱해 최대 점수를 계산하는 시뮬레이션 문제입니다. 상자와 카드의 순환 구조를 이용해 그룹을 형성하며, 상자를 열며 그룹을 나누는 방식입니다.
1. 문제 분석
이 게임은 주어진 카드 배열을 기반으로 상자를 열어 그룹을 형성하는 방식입니다. 각 상자는 하나의 카드에 연결되어 있어, 하나의 상자를 열면 카드에 적힌 번호를 가진 상자를 이어서 열어야 합니다. 이렇게 순환 구조를 형성하며 그룹이 만들어집니다. 중요한 점은, 이 그룹들이 서로 독립적이라는 점입니다. 두 개의 그룹을 선택하고, 그 그룹의 크기를 곱한 값이 게임의 점수가 됩니다.
2. 접근 방식
이 문제를 해결하기 위해서는, 상자를 열어 순환 구조를 파악하고 그룹을 형성하는 과정이 필요합니다. 다음과 같은 단계로 문제를 해결할 수 있습니다:
- 순환 구조 탐색: 각 상자를 순차적으로 확인하며, 아직 열리지 않은 상자부터 시작해 카드의 숫자에 따라 상자를 열어 나갑니다. 이 과정을 통해 독립적인 그룹이 형성됩니다.
- 그룹 크기 저장: 그룹의 크기를 우선순위 큐에 저장합니다. 가장 큰 두 그룹을 선택해 그 크기를 곱한 값을 최종 점수로 계산합니다.
- 최대 두 그룹 선택: 형성된 그룹 중 가장 큰 두 그룹의 크기를 선택해 점수를 계산합니다. 만약 그룹이 하나뿐이라면 점수는 0이 됩니다.
3. 우선순위 큐 및 상자 열림 상태 초기화
우선순위 큐를 사용하여 각 그룹의 크기를 저장하고, 가장 큰 두 그룹을 쉽게 선택할 수 있도록 준비합니다. 또한, 각 상자가 열렸는지 여부를 기록하기 위한 배열을 초기화합니다.
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // 큰 순서로 정렬되는 우선순위 큐
boolean[] opened = new boolean[cards.length]; // 상자의 열림 상태를 기록할 배열
4. 순환 구조 탐색 및 그룹 형성
주어진 카드 배열에서 각 상자를 차례로 탐색하며, 아직 열리지 않은 상자부터 시작하여 그룹을 형성합니다. 각 상자를 열면 카드에 적힌 숫자를 확인하여 다음 상자를 열고, 이를 반복합니다. 이미 열렸던 상자를 다시 만나게 되면 해당 그룹의 탐색을 종료하고 그룹의 크기를 우선순위 큐에 추가합니다. 이 과정에서 독립적인 그룹들이 형성됩니다.
for (int i = 0; i < cards.length; i++) {
if (!opened[i]) { // 해당 상자가 아직 열리지 않았다면 그룹 탐색 시작
int count = 0; // 현재 그룹의 상자 개수를 세기 위한 변수
int curr = i; // 현재 탐색 중인 상자의 인덱스
// 상자를 열면서 그룹을 형성
while (!opened[curr]) {
count++; // 그룹에 상자를 추가
opened[curr] = true; // 현재 상자를 열었다고 표시
curr = cards[curr] - 1; // 카드에 적힌 번호에 해당하는 상자로 이동
}
pq.add(count); // 그룹이 형성되면 해당 그룹의 크기를 우선순위 큐에 저장
}
}
5. 가장 큰 두 그룹 선택 및 점수 계산
우선순위 큐에 저장된 그룹 크기 중에서 가장 큰 두 그룹을 선택하여 그 크기를 곱해 점수를 계산합니다. 만약 형성된 그룹이 두 개 미만이면, 게임에서 얻을 수 있는 점수는 0이 됩니다.
if (pq.size() < 2) return 0; // 그룹이 두 개 미만이면 점수는 0
return pq.poll() * pq.poll(); // 가장 큰 두 그룹의 크기를 곱하여 점수 반환
Complexity
- ⏳ TC: O(n)
- 💾 SC: O(n)
주어진 상자의 수에 따라 그룹을 탐색하는데, 이는 각 상자를 한 번씩만 탐색하기 때문에 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 상자의 열림 여부를 저장하는 배열과 우선순위 큐를 사용하므로 O(n)입니다.
- Algorithm
- Simulation