프로그래머스 Lv.2 - 혼자 놀기의 달인

문제

링크

title: "프로그래머스"
image: "https://school.programmers.co.kr/assets/img-meta-programmers-411e94bf29153dc31004168e6cd500279b1a531a23689303755e51971dee4526.png"
description: "SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프"
url: "https://school.programmers.co.kr/learn/courses/30/lessons/131130"

문제 풀이

문제 접근

이 코드는 주어진 카드 배열에서 상자에 들어 있는 카드들이 순서대로 연결된 순환 구조를 따라가며, 두 개의 가장 큰 상자 크기를 찾아 그 값을 곱한 결과를 반환하는 문제를 해결합니다.
접근 방법의 핵심은 다음과 같습니다:

카드 배열의 수정:
- 카드 배열의 값은 1-based 인덱스(1부터 시작)로 되어 있으므로, 이를 0-based 인덱스(0부터 시작)로 변환하여 처리합니다.
순환 구조 탐색:
- 각 카드 번호를 따라가며, 순환하는 상자들을 방문합니다. 이미 방문한 상자는 다시 방문하지 않도록 visited 배열을 사용합니다.
- 각 순환의 길이를 계산하여 boxes 리스트에 저장합니다.
가장 큰 상자 크기 계산:
- boxes 리스트에서 상자의 크기를 내림차순으로 정렬한 후, 가장 큰 두 상자의 크기를 곱합니다.
결과 반환:
- 가장 큰 두 상자의 크기를 곱한 값을 반환합니다.
  간단한 수도 코드 정리
```pseudocode function solution(cards): answer = 0 visited = array of false with size of cards boxes = empty list
for i from 0 to length(cards) - 1: cards[i] = cards[i] - 1 // convert to 0-based index
for i from 0 to length(cards) - 1: if visited[i] is false: count = 0 index = i while visited[index] is false: visited[index] = true index = cards[index] // move to the next card in the cycle count += 1 add count to boxes
sort boxes in descending order
answer = boxes[0] * boxes[1] // multiply the two largest box sizes
return answer

---
## 풀이 코드
```java
import java.util.*;

class Solution {
    public int solution(int[] cards) {
        int answer = 0;
        boolean[] visited = new boolean[cards.length];
        ArrayList<Integer> boxes = new ArrayList<>();
        
        // 박스에 1번 상자만 존재하면 에러가 나기 때문에, 0을 하나 삽입
        boxes.add(0);
        
        for (int i = 0; i< cards.length; i++) {
            cards[i] = cards[i] - 1;
        }
        
        for (int i = 0; i < cards.length; i++) {
            int count = 0;
            int index = i;
            
            while (!visited[index]) {
                visited[index] = true;
                index = cards[index];
                count++;
            }
            
            boxes.add(count);
        }
        
        Collections.sort(boxes, Collections.reverseOrder());
        
        answer = boxes.get(0) * boxes.get(1);
        
        System.out.println(boxes);
        
        return answer;
    }
}

Latest Docs

문제

문제 풀이

문제 접근

간단한 수도 코드 정리