Skip to main content

131130 - 혼자 놀기의 달인

info

풀이 키워드​

스포주의

구현 그래프 dfs


풀이 코드​

info
  • 메모리: 89600 KB
  • 시간: 1 ms
import java.util.*;

class Solution {
    int[] cards;
    boolean[] visited;
    
    int findCycle(int i) {
        if (visited[i]) return 0;
        visited[i] = true;
        
        return findCycle(cards[i]-1) + 1;
    }
    
    public int solution(int[] cards) {
        this.cards = cards;
        visited = new boolean[cards.length];
        List<Integer> clenList = new ArrayList<>();
        
        // 1. 모든 사이클 뭉치를 찾는다 (길이만 구해두기)
        for (int i = 0; i < cards.length; ++i) {
            clenList.add(findCycle(i));
        }
        
        if (clenList.size() < 2) return 0;
        
        // 2. 뭉치 길이 제일 긴거 2개 곱하기
        Collections.sort(clenList, Collections.reverseOrder());
        
        return clenList.get(0) * clenList.get(1);
    }
}

풀이 해설​

알고리즘 자체의 난이도보단 약간의 독해력과 방향 그래프 문제로 치환하는 능지가 요구된다.

그래프 구현까진 안가고 visited 처리로 사이클 뭉치만 잘 찾아주면 된다.


🔁 사이클 찾기 문제로 치환하기​

지문에서 화려하게 설명했지만 결국 상자를 열면 다음에 열 상자 번호가 들어있다는 점에서, 사이클 찾으라는 소리다.

예를 들어 규칙대로 상자를 계속 열어봤더니 이런 순서로 열게 되었다고 가정해보자.
(마지막 3을 열었을 때 5가 들어있었고, 이미 5는 열려있으므로 끝)

상자를 열어본 순서
5 -> 1 -> 2 -> 4 -> 3

여기서 한 사이클 그룹이면 시작을 5로 하든 2로 하든 3으로 하든 결국 구성원은 똑같다는 점을 알 수 있다.

그리고 cards의 값들이 서로 unique하기 때문에,
자기 자신을 가리키는 self-loop 노드를 포함해서, 모든 노드의 in-degree / out-degree는 1이다.
따라서 사이클끼리는 서로 겹치는 노드가 없다.

그래서 visited를 통해 이미 열린 상자만 표시하면서 O(n)O(n)으로 모든 사이클을 찾아주면 된다.

심지어 사이클 멤버를 알 필요도 없다. 그냥 사이클 당 길이만 구해두면 된다.

호출부
for (int i = 0; i < cards.length; ++i) {
    clenList.add(findCycle(i));
}
피호출부
int findCycle(int i) {
    if (visited[i]) return 0;
    visited[i] = true;
    
    return findCycle(cards[i]-1) + 1;
}

그리고 이렇게 찾은 길이 값 중 가장 큰 2개의 값을 서로 곱해 정답을 구한다.

길이 값이 1개밖에 안나온다면 0점 처리한다.

if (clenList.size() < 2) return 0;

// 2. 뭉치 길이 제일 긴거 2개 곱하기
Collections.sort(clenList, Collections.reverseOrder());

return clenList.get(0) * clenList.get(1);

메모​

  • sorting boxed integer list in reverse order... 귀하군요
  • 실버 3쯤으로 예상되는 다소 쉬운 문제