99클럽 코테 스터디 38일차 TIL / [프로그래머스] 혼자 놀기의 달인

오늘의 학습 키워드

---

DFS

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/131130

• 플랫폼: 프로그래머스
• 문제명: 혼자 놀기의 달인
• 난이도: Lv2

풀이

---

import java.util.*;

class Solution {
    
    static List<Integer> list = new ArrayList<>();
    static boolean[] visited = new boolean[100];
    
    public int solution(int[] cards) {
        int answer = 0;
        
        for(int i=0; i<cards.length; i++) {
            int boxCnt = 0;
            int idx = i;
            
            while(!visited[idx]) {
                visited[idx] = true;
                boxCnt++;
                idx = cards[idx] - 1;
            }
            
            list.add(boxCnt);
        }
        
        Collections.sort(list, Collections.reverseOrder());
        
        return list.get(0) * list.get(1);
    }
}

접근

• [2, 3, 1]과 같이 입력이 들어온 경우, 어느 위치에서 시작해도 3개의 상자가 열리게 됩니다.
• 방문 여부 배열을 만들어 cards 배열을 앞에서부터 순회한다면 O(n)의 복잡도로 문제 풀이가 가능합니다.

  for(int i=0; i<cards.length; i++) {
      int boxCnt = 0;
      int idx = i;
      
      while(!visited[idx]) {
          visited[idx] = true;
          boxCnt++;
          idx = cards[idx] - 1;
      }
      
      list.add(boxCnt);
  }

  • for문을 통해 앞에서부터 순회하며, 만약 아직 열리지 않은 박스를 발견하면 모두 열어 해당 그룹 내 박스 개수를 카운트합니다.
  • 이후 list에 그룹의 개수들을 저장합니다.
  • 그리고 list를 내림차순 정렬하여 index 0, 1의 원소를 추출해 곱해주면 정답을 도출할 수 있습니다. (개수가 가장 많은 그룹 2개를 추출한 것과 같은 의미)

소요 시간

20분