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

allnight5·2023년 6월 30일
0

프로그래머스

목록 보기
70/73

해결 방법은 어렵지 않지만.. 문제자체를 이해하는데 오래걸리는 문제였다.

상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인합니다.
다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자를 확인합니다.
마찬가지로 숫자에 해당하는 번호를 가진 상자를 계속해서 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복합니다.

자세히.

언제나 0번째 부터 열기 시작한다. 그리고 그 다음 인덱스를 여는데 이미 0번째 그룹을 열때 열었다면 다음 인덱스로 넘어가는 식으로 한다.

상자라는 배열이 아래와 같이 있다고 하자
0, 1, 2, 3, 4, 5, 6, 7 // 배열에 인덱스 번호
[8, 6, 3, 7, 2, 5, 1, 4]// 배열

이제 상자를 열어보자
i=0;
int next = arrya[i];// array[0] -> 8이 나온다.
나는 0번 인덱스를 연다 0번 인덱스의 값은 8이다.
여기서 문제는.. 인덱스는 0부터 시작하지만
상자의 카드는 1부터 시작한 다는 것이다.
8에서 -1을 하면 7이 나온다. next ->7 로 만들어줘야한다.
int next = arrya[next] // arrai[7];-> 4 -> 4-1 -> 3
그러면 7번 인덱스로 이동하게 된다.
그리고 다음 인덱스인
array[3] ; ->7로 이동하게 된다. -> 7-1 -> 6 ;
array[6]; -> 1 -> 1-1 -> 0;
array[0] ; 0번째 인덱스는 이미 방문한 곳이라서 정지 여기서 카운트를 해줬다면 빼줘야 한다.
이런식으로 이미 지나간 인덱스를 방문할때까지 반복하면 된다.

간단히

  1. 카드뭉치에서 a번째 카드를 뽑습니다.
    a번째 카드에서 b라는 숫자가 나왔습니다.
  2. 이제 카드뭉치에서 b번째 카드를 뽑습니다.
    b번째 카드에서 c라는 숫자가 나옵니다.
  3. 이제 카드뭉치에서 c번째 카드를 뽑습니다.
    c번째 카드에서 a라는 숫자가 나옵니다.
  4. 이제 카드뭉치에서 a번째 카드를 뽑으려고 했으나 이미 뽑은 카드라 그만 두게 됩니다.
    -> 반복하면서 중단하기 전까지의 횟수를 count하여 보관해두고 위에 같이 카드를 뽑아서 숫자를 체크하는 것이
    2번 이상이라면 최대값 2개를 곱해서 반환하면 됩니다. 하지만 첫번째에 모든 카드를 뽑아낸다면 0을 반환하면 됩니다.
import java.util.PriorityQueue;
import java.util.Collections;
class Solution {
    public int solution(int[] cards) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int endPoint = cards.length;
        boolean[] visit = new boolean[endPoint]; 
        
        for(int card: cards){
            if(!visit[card-1]) pq.offer(inputQueue(cards, card, visit, endPoint));
        } 
         
        return pq.size() < 2 ? 0 : pq.poll()* pq.poll();
        
    }
    public static int inputQueue(int[] cards, int cur, boolean[] visit, int endPoint){
        int answer =0; 
        
        while(!visit[cur-1]){ 
            visit[cur-1] = true;
            cur = cards[cur-1];
            answer++;  
        }
        return answer;
    }
}
profile
공부기록하기

0개의 댓글