[프로그래머스/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이 되는지 검사한다.
- 내 덱의 카드 2장 (coin 소모 X)
- 내 덱의 카드 1장 + 임시저장소의 카드 1장 (coin 1개 소모)
- 임시저장소의 카드 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.

