Post

[프로그래머스/LV3] n + 1 카드게임 - Greedy, HashSet(Java)

프로그래머스 LV3 n + 1 카드게임 문제를 Java의 Greedy와 HashSet을 활용하여 해결한 풀이입니다.

[프로그래머스/LV3] n + 1 카드게임

🙋‍♂️ 들어가며

테스트케이스 1번을 보고 문제를 이해하지 못했으나, GPT와 함께 테스트케이스 2, 3, 4번을 검증하고 드디어 이해하였다.

나는 빡대가리임에 틀림없었던 것이었다.

아무튼 아래 내 사고의 흐름대로 작성하였다.



먼저 처음 지급받은 카드를 my_deck에 저장하고, 매 라운드마다 뽑는 카드 2장은 temp_save에 저장한다.

이후 다음과 같은 우선순위로 카드의 합이 N+1이 되는지 검사한다.

  1. 내 덱의 카드 2장 (coin 소모 X)
  2. 내 덱의 카드 1장 + 임시저장소의 카드 1장 (coin 1개 소모)
  3. 임시저장소의 카드 2장 (coin 2개 소모)

셋 중 하나라도 성공하면 다음 라운드로 넘어가고, 모두 실패하면 게임을 종료한다.

카드를 뽑을 때마다 coin을 소모하는 것이 아니라, 임시저장소에 저장해 두었다가 실제로 필요한 카드를 사용할 때 coin을 소모하는 방식으로 접근하였다.



HashSet

이번 문제를 통해 HashSet은 index가 없기에 get()을 사용할 수 없다는 것을 알게 되었다.

대신 contains()를 통해 값의 존재 여부를 확인하고, remove()를 통해 해당 값을 제거할 수 있다.



시간복잡도

이 문제의 시간복잡도는 O(N²)이다.

최악의 경우를 넉넉하게 계산하면 N = 996

  • 초기 카드 저장 : 332회
  • while문 : 최대 332회
  • 우선순위 1번 검사 : 최대 332회
  • 우선순위 2번 검사 : 최대 332회
  • 우선순위 3번 검사 : 최대 664회

332 + 332 * (332 + 332 + 664) = 441,228

약 44만 연산횟수 이므로 시간초과는아니다



✅ 코드 (Greedy + HashSet)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.util.Set;
import java.util.HashSet;


class Solution {
    public int solution(int coin, int[] cards) {
        int answer = 0;

        // 1. 내덱, 임시저장소 생성
        Set<Integer> my_deck = new HashSet<>();
        Set<Integer> temp_save = new HashSet<>();
        int N = cards.length;
        int idx = N / 3;
        for (int i = 0; i < idx; i++) {
            int cur_val = cards[i];
            my_deck.add(cur_val);
        }

        // 2. 첫 라운드
        int round = 1;

        // 3. while (남은 카드가 없을때까지 검사)
        while (idx < N) {

            // 3-1. 각 라운드 시작시 카드 2장 뽑기
            int first = cards[idx];
            int second = cards[idx+1];
            temp_save.add(first);
            temp_save.add(second);
            idx += 2;

            int leng = my_deck.size();
            int K = temp_save.size();

            // 3-2. 내 덱에서 카드 2장 합이 되는지 검사 (우선순위 1번)
            boolean is_first_priority_done = false;
            for (int x : my_deck) {
                int y = N+1 - x;
                if (my_deck.contains(y)) {
                    my_deck.remove(x);
                    my_deck.remove(y);
                    is_first_priority_done = true;
                    break;
                }
            }

            // 3-3. 내 덱에서 카드 2장 합 못채워서 -> 내덱 1개 + 임시덱 1개 (코인1) 가능한지 검사
            boolean is_second_priority_done = false;
            if (!is_first_priority_done && coin >= 1) {
                for (int x : my_deck) {
                    int y = N+1 - x;
                    if (temp_save.contains(y)) {
                        my_deck.remove(x);
                        temp_save.remove(y);
                        coin--;
                        is_second_priority_done = true;
                        break;
                    }
                }
            }

            // 3-4. 내덱 2장도 안되고, 내덱1 + 임시덱1 도 안될때
            // -> 임시덱 2장 (coin 2)
            boolean is_third_priority_done = false;
            if (!is_first_priority_done && !is_second_priority_done && !is_third_priority_done && coin >= 2) {
                for (int x : temp_save) {
                    int y = N+1 - x;
                    if (temp_save.contains(y)) {
                        temp_save.remove(x);
                        temp_save.remove(y);
                        coin -= 2;
                        is_third_priority_done = true;
                        break;
                    }
                }
            }

            // 3-5. 어떤 경우에서도 카드 제출을 못했다면?
            if (!is_first_priority_done && !is_second_priority_done && !is_third_priority_done) {
                break;
            }

            // 3-6. 셋중 하나라도 성공시 다음 라운드로
            round++;
        }

        // 4. 답
        answer = round;
        return answer;
    }
}
This post is licensed under CC BY 4.0 by the author.

Trending Tags

반갑습니다 무엇을 도와드릴까요?