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

Yuno·2024년 7월 20일

Java)코테 연습

목록 보기

14/18

사용한 자료구조 : 그래프
사용한 알고리즘 : DFS를 사용한 사이클 찾기

문제를 이해하는데 굉장히 애를 먹었다.

오랜시간끝에 이해한 결과..

[8, 6, 3, 7, 2, 5, 1, 4] 의 카드들이 있을때,

0번 인덱스, 즉 8번 카드를 얻는다.
8번카드는 8번째, 즉 7번 인덱스에 접근한다.
7번 인덱스에는 4가 있으니, 4번째, 즉 3번 인덱스에 접근한다.
3번 인덱스에는 7이 있으니, 7번째, 즉 6번 인덱스에 접근한다.
6번 인덱스에는 1이 있으니 1번째, 즉 0번 인덱스에 접근한다.
0번 인덱스에는 이미 방문한적이 있으니 이 카드들을 모아서 1번 박스를 만든다.

결국 1번박스에는 [1, 4, 7, 8]의 카드 4장이 있다.

다음으로 2번인덱스로 접근하여 숫자를 확인한다.
이 작업들을 계속 반복하다보면

1번 박스 : [1, 4, 7, 8] 4장의 카드
2번 박스 : [2, 5, 6] 3장의 카드
3번 박스 : [3] 1장의 카드

() 안의 숫자는 이미 방문한 적이 있는 숫자
8 -> 4 -> 7 -> 1 -> (8)
6 -> 5 -> 2 -> (6)
3

3개의 상자중 가장 많이 들어있는 두 상자를 찾아 상자안의 카드 갯수만큼 곱해준다

1번 박스 : 4장
2번 박스 : 3장
4 $\times$ 3 $=$ 12

📌방문 확인을 하기위한 boolean 배열과, 상자 안의 갯수를 확인하기 위한 ArrayList

박스의 최대크기는 2개 이거나, 최대 100개가 될수도 있어
동적으로 배열을 생성하는 ArrayList 생성
각 카드의 방문확인을 위해 boolean 배열 생성

List<Integer> boxes = new ArrayList<>();
boolean[] visited = new boolean[cards.length];

📌DFS를 사용해 사이클 찾기

반복문을 통해 위에 기술한 것처럼 각 카드의 연결점을 찾은 후 마지막 연결점(사이클) 이 완성되면 갯수를 세어 ArrayList에 넣어주는 작업을 했다.

for (int i = 0; i < cards.length; i++) {
    if (!visited[i]) {
        int size = 0;
        int cur = i;

        while (!visited[cur]) {
            visited[cur] = true;
            cur = cards[cur] - 1;
            size++;
        }
        boxes.add(size);
    }
}

📌빵점일수도 있쟈나..?

만약 한사이클만에 cards 배열을 돌수도 있으니
박스 갯수가 1개일수도 있으니..
이럴땐 0점으로 처리한다.

if (boxes.size() < 2) {
    return 0;
}

📌점수계산

sort를 사용하면 오름차순으로 계산이 된다. 하지만 나에게 필요한건 내림차순 계산.
변수명.sort(거꾸로 명령을 내린다!)
현재 boxes List는 [4, 3, 1] 로 정렬되어있다.
List의 0번 인덱스와 1번 인덱스의 값들을 꺼내 계산하면 끝!

boxes.sort(Collections.reverseOrder());

    return boxes.get(0) * boxes.get(1);
}

💻 최종 코드 💻

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int solution(int[] cards) {
        List<Integer> boxes = new ArrayList<>();
        boolean[] visited = new boolean[cards.length];

        for (int i = 0; i < cards.length; i++) {
            if (!visited[i]) {
                int size = 0;
                int cur = i;

                while (!visited[cur]) {
                    visited[cur] = true;
                    cur = cards[cur] - 1;
                    size++;
                }
                boxes.add(size);
            }
        }

        if (boxes.size() < 2) {
            return 0;
        }

        boxes.sort(Collections.reverseOrder());

        return boxes.get(0) * boxes.get(1);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] cards = {8, 6, 3, 7, 2, 5, 1, 4};
        System.out.println(sol.solution(cards));
    }
}

👏👏👏👏👏👏👏👏👏

🤔 흠..

추가적으로 재귀적으로 문제를 접근해서 풀수 있지 않을까 생각했다.

재귀적으로 문제를 접근하면, 스택 오버플러우(Stack Overflow) 가 발생하기 쉬워서 오류가 일어날수 있지만, 해당문제는 데이터량이 그렇게 크지 않은것 같아서 재귀구현 연습하는겸, 시도해보았다.

스택 오버플로우(Stack Overflow)

스택은 함수호출, 지역 변수 저장 등에 사용되는 메모리 영역

재귀호출이 너무 깊어지면(많아지면) 메모리가 부족해질수 있음

스택 메모리가 한계를 초과하게 되면 오류가 발생을 함

재귀가 너무 취약한 나는 모든것이 취약하지만.. 재귀적으로 구현을 시도해 보았다.

📌DFS 함수 구현

카드 배열, 방문 배열, 현재 위치를 계속 넘겨주어, 카드의 갯수를 세는 방법으로 구현했다.
탈출조건으로, 방문한 적이 있는 카드면 0을 반환하여 더이상 카드의 갯수를 카운트 하지 않는다.
재귀적으로 반복할때, 1을 반환하며, 현재 계산된 카드를 1씩 증가시켜준다.

public int dfs (int[] cards, boolean[] visited, int cur) {
    if (visited[cur]) {
        return 0;
    }
    visited[cur] = true;

    int next = cards[cur] - 1;
    return 1 + dfs(cards, visited, next);
}

📌solution 메서드

카드 배열들을 순회하며, DFS함수에서 방문체크한 카드들을 확인하며, ArrayList에 값들을 넣어준다.

for (int i = 0; i < cards.length; i++) {
    if (!visited[i]) {
        int size = dfs(cards, visited, i);
        boxes.add(size);
    }
}

💻 최종 코드 💻

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int dfs (int[] cards, boolean[] visited, int cur) {
        if (visited[cur]) {
            return 0;
        }
        visited[cur] = true;

        int next = cards[cur] - 1;
        return 1 + dfs(cards, visited, next);
    }
    public int solution(int[] cards) {
        boolean[] visited = new boolean[cards.length];
        List<Integer> boxes = new ArrayList<>();

        for (int i = 0; i < cards.length; i++) {
            if (!visited[i]) {
                int size = dfs(cards, visited, i);
                boxes.add(size);
            }
        }
        boxes.sort(Collections.reverseOrder());

        if (boxes.size() < 2) {
            return 0;
        }

        return boxes.get(0) * boxes.get(1);
    }