🎯문제
혼자서도 잘 노는 범희는 어느 날 방구석에 있는 숫자 카드 더미를 보더니 혼자 할 수 있는 재미있는 게임을 생각해냈습니다.
숫자 카드 더미에는 카드가 총 100장 있으며, 각 카드에는 1부터 100까지 숫자가 하나씩 적혀있습니다. 2 이상 100 이하의 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드들을 준비하고, 준비한 카드의 수만큼 작은 상자를 준비하면 게임을 시작할 수 있으며 게임 방법은 다음과 같습니다.
준비된 상자에 카드를 한 장씩 넣고, 상자를 무작위로 섞어 일렬로 나열합니다. 상자가 일렬로 나열되면 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호를 붙입니다.
그 다음 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인합니다. 다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자를 확인합니다. 마찬가지로 숫자에 해당하는 번호를 가진 상자를 계속해서 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복합니다.
이렇게 연 상자들은 1번 상자 그룹입니다. 이제 1번 상자 그룹을 다른 상자들과 섞이지 않도록 따로 둡니다. 만약 1번 상자 그룹을 제외하고 남는 상자가 없으면 그대로 게임이 종료되며, 이때 획득하는 점수는 0점입니다.
그렇지 않다면 남은 상자 중 다시 임의의 상자 하나를 골라 같은 방식으로 이미 열려있는 상자를 만날 때까지 상자를 엽니다. 이렇게 연 상자들은 2번 상자 그룹입니다.
1번 상자 그룹에 속한 상자의 수와 2번 상자 그룹에 속한 상자의 수를 곱한 값이 게임의 점수입니다.
상자 안에 들어있는 카드 번호가 순서대로 담긴 배열 cards가 매개변수로 주어질 때, 범희가 이 게임에서 얻을 수 있는 최고 점수를 구해서 return 하도록 solution 함수를 완성해주세요.
제한사항
2 ≤ cards의 길이 ≤ 100
cards의 원소는 cards의 길이 이하인 임의의 자연수입니다.
cards에는 중복되는 원소가 존재하지 않습니다.
cards[i]는 i + 1번 상자에 담긴 카드에 적힌 숫자를 의미합니다.
입출력 예
| cards | result |
|---|---|
| [8,6,3,7,2,5,1,4] | 12 |
입출력 예 설명
1, 4, 7, 8이 속하는 상자의 그룹과 2, 5, 6이 속하는 상자의 그룹과 3이 속하는 상자의 그룹이 존재합니다. 따라서 3번 상자를 고르지 않았을 때, 두 번의 시행에서 3과 4를 기록하며 최고 점수 12를 얻을 수 있습니다.
✏️풀이
코드
import java.util.*;
class Solution {
// 방문여부를 저장할 배열
boolean[] visit;
// 우선순위 큐
PriorityQueue<Integer> queue;
// 깊이 우선 탐색 시작
public void dfs(int[] cards, int index, int depth) {
// 박스를 연 적 있다면
if(visit[index]) {
// 지금까지 연 박스의 개수를 저장하고 반환
queue.add(depth);
return;
}
// 박스를 열고
visit[index] = true;
// 해당 박스에 있는 값으로 다른 박스를 열어줌
dfs(cards, cards[index] - 1, depth + 1);
}
public int solution(int[] cards) {
int answer = 0;
visit = new boolean[cards.length];
queue = new PriorityQueue<>(Collections.reverseOrder());
// dfs 반복
for(int i = 0; i < cards.length; i++) {
if(!visit[i]) {
dfs(cards, i, 0);
}
}
// 큐의 사이즈가 1일 경우 한번의 탐색으로 모두 열었다는 뜻
// 따라서 0을 반환해주고 아닐 경우 큰 수 2개를 뽑아서 곱한 값을 반환
return answer = queue.size() == 1 ? 0 : queue.poll() * queue.poll();
}
}설명
DFS와 우선순위 큐를 사용하여 문제를 해결하였다.
방문여부를 저장할 visit 배열과 우선순위 큐를 생성해주었다. visit 배열은 DFS 탐색을 진행할 때 방문을 했는지 여부를 판단할 수 있도록 해주는 배열이며, 우선순위 큐는 원하는 순서대로 값들을 정렬하는 자료구조이다.
문제에서 가장 높은 점수를 반환하도록 했으므로 Collections.reverseOrder()를 사용하여 내림차순으로 저장하도록 했다.
DFS 탐색을 진행하게 되는데 탐색 종료 조건문은 탐색을 진행하는 과정에서 이미 열었던 박스를 마주하게 될 경우이다. 문제에서도 이미 열었던 박스를 마주하게 됐을 경우 해당 박스들은 1번 그룹으로 두고, 2번 그룹의 탐색을 진행하기 때문이다.
종료 조건문에 만족할 경우 탐색한 횟수를 우선순위 큐에 저장하고 반환해준다. 우리가 구하려고 하는 것은 탐색한 횟수이기 때문이다.
만약 열지 않은 박스라면 박스를 연다. 열었다는 표시는 visit 배열에 해당 위치를 true로 바꿔주는 것으로 한다. 이후 해당 박스에 들어있는 값으로 다시 탐색을 진행한다. 주의해야할 점은 배열의 인덱스이기 때문에 배열에 있는 값을 그대로 인덱스에 넘겨줄 경우 오류가 날 수 있다. 배열 인덱스의 시작은 0부터이기 때문이다. 따라서 cards[index] - 1의 값을 넘겨주고, 탐색횟수도 추가해준다.
위의 과정을 모두 반복하고 난 뒤 우선순위 큐의 값을 확인하여 조건에 맞게 반환을 해주면 되는데, 만약 큐에 저장된 값이 1개 밖에 없을 경우 0을 반환해준다. 큐에 저장된 값이 1개인 경우는 한번의 탐색으로 모든 상자를 열 수 있으며 이는 다른 그룹이 나눠지지 않았다는 뜻이 된다. 따라서 문제의 조건처럼 0을 반환해주고, 2개 이상일 경우 값을 두개 가져와서 곱한 값을 반환해준다.
이때 우선순위 큐는 아까 위에서 얘기했던 것처럼 내림차순 정렬이다. 첫번째 값을 가져온 뒤, 다시 자동으로 정렬이 되기 때문에 큐에 저장된 가장 큰 값과 두번째로 큰 값을 가져올 수 있게 된다.
따라서, 해당 값을 반환하면 게임을 통해 얻을 수 있는 최고 점수를 반환해주는 것이므로 문제를 해결할 수 있다!
💡느낀 점
이전 문제들에서는 DFS 탐색이면 DFS 탐색, 우선순위 큐면 우선순위 큐 이렇게 각각 하나씩만 사용하는 문제였다면 이번에는 두가지를 동시에 사용해서 푸는 문제였다. 물론 하나만 사용하는 게 익숙했기에 두가지를 동시에 사용한다는 생각이 쉽게 들지 않았고, 값을 저장하는 방식에 대해서 찾다가 우선순위 큐가 생각나서 방법으로 채택해 문제를 풀었더니 해결할 수 있었다. 문제를 푸는 방식이 다양하다고는 하지만 두가지를 동시에 사용하는 것도 생각하니 머리가 아파진다 ;)
링크
