자기개발/프로그래머즈Lv2

[Programmers Lv2, Java] 혼자 놀기의 달인

KGW2027 2022. 11. 1. 23:34
728x90
반응형

문제 설명

혼자서도 잘 노는 범희는 어느 날 방구석에 있는 숫자 카드 더미를 보더니 혼자 할 수 있는 재미있는 게임을 생각해냈습니다.

숫자 카드 더미에는 카드가 총 100장 있으며, 각 카드에는 1부터 100까지 숫자가 하나씩 적혀있습니다. 2 이상 100 이하의 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드들을 준비하고, 준비한 카드의 수만큼 작은 상자를 준비하면 게임을 시작할 수 있으며 게임 방법은 다음과 같습니다.

준비된 상자에 카드를 한 장씩 넣고, 상자를 무작위로 섞어 일렬로 나열합니다. 상자가 일렬로 나열되면 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호를 붙입니다.

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

이렇게 연 상자들은 1번 상자 그룹입니다. 이제 1번 상자 그룹을 다른 상자들과 섞이지 않도록 따로 둡니다. 만약 1번 상자 그룹을 제외하고 남는 상자가 없으면 그대로 게임이 종료되며, 이때 획득하는 점수는 0점입니다.

그렇지 않다면 남은 상자 중 다시 임의의 상자 하나를 골라 같은 방식으로 이미 열려있는 상자를 만날 때까지 상자를 엽니다. 이렇게 연 상자들은 2번 상자 그룹입니다.

1번 상자 그룹에 속한 상자의 수와 2번 상자 그룹에 속한 상자의 수를 곱한 값이 게임의 점수입니다.

상자 안에 들어있는 카드 번호가 순서대로 담긴 배열 cards가 매개변수로 주어질 때, 범희가 이 게임에서 얻을 수 있는 최고 점수를 구해서 return 하도록 solution 함수를 완성해주세요.

    public int solution(int[] cards) {

        int[] cnts = new int[cards.length];

        // 4 3 1 4 3 3 4 4
        for(int selectA = 0 ; selectA < cards.length ; selectA++) {
            List<Integer> cardsList = Arrays.stream(cards).boxed().collect(Collectors.toList());
            int groupASize = openBoxCycle(cardsList, cards, selectA);

            for(int selectB = 0 ; selectB < cards.length ; selectB++) {
                int groupBSize = openBoxCycle(cardsList, cards, selectB);
                cnts[selectA] = Math.max(cnts[selectA], groupASize * groupBSize);
            }
        }

        int answer = 0;
        for(int i = 0 ; i < cnts.length ; i++)
            if(cnts[i] > answer) answer = cnts[i];
        return answer;
    }

    public int openBoxCycle(List<Integer> boxes, int[] cards, int key) {
        if(!boxes.contains(cards[key])) return 0;
        boxes.remove((Object) cards[key]);
        return 1+openBoxCycle(boxes, cards, cards[key]-1);
    }

최초 코드의 형태는 이렇다.

그냥 문제 내용 그대로 A에 대한 사이클 구하고, 남은 박스에서 B에 대한 사이클을 구하는 대놓고 O(n^2) 형태로 만든 코드고, 일단 정확도부터 뚫은다음 효율성을 파려고 했는데.. 정확성테스트밖에 없어서 클리어 돼버렸다...

아무튼 그래도 효율성을 올릴수 있는만큼 올려봐야 공부가되므로 수정을 해봤다.

 

일단 이 문제는 cards Array 내에서 Cycle을 찾고, 가장 큰 Cycle 2개의 곱을 구하는 내용이다.

사이클이므로 배열내의 각 값은 하나의 사이클에만 속할것이고, 이는 배열 내의 모든 사이클을 구한 후 가장 큰 2개를 곱하기만 하면 해결된다는 것이다.

 

변경된 코드는 아래와 같다

    public int solution(int[] cards) {

        List<Integer> cycles = new ArrayList<>();
        for(int select = 0 ; select < cards.length ; select++) {
            if(cards[select] == 0) continue;
            cycles.add(getCycle(cards, select));
        }

        if(cycles.size() <= 1) return 0;
        cycles.sort(Collections.reverseOrder());
        return cycles.get(0) * cycles.get(1);
    }

    public int getCycle(int[] cards, int key) {
        if(cards[key] == 0) return 0;
        int buffer = cards[key];
        cards[key] = 0;
        return 1+getCycle(cards, buffer-1);
    }

자바에서 int[]같은 배열은 call by reference라고 하던가? 인자로 받은 내용을 수정해도 원래 변수에 영향을 준다.

그래서 다음과 같이 사이클을 구하면서 0으로 설정, 0이된 슬롯은 continue하면서 사이클을 구해준다.

 

사이클을 구하는곳은 O(n), // 각 key당 최대 2번 접근될 수 있으므로 O(2n)이라고 해야할까...뭐 다를게없으니.

자바 리스트 정렬은 최악O(n*lgn)로 알고 있으므로,

이 알고리즘은 O(nlgn)의 시간복잡도를 가지므로 처음의 코드 O(n^2)보다 빠를 것이다.

실제로 테스트케이스 결과는 더 어마무시했다.

728x90
반응형