- 오늘의 학습 키워드 : 구현
[문제 이름 : n+1 카드게임 (프로그래머스 258707, Lv 3)]
문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/258707
내가 작성한 코드는 아래와 같다.
import java.util.*;
class Solution {
public int solution(int coin, int[] cards) {
int answer = 0;
int len = cards.length;
int target = len + 1;
List<Integer> deck = new ArrayList<>();
List<Integer> hand = new ArrayList<>();
int idx = len / 3;
for (int i = 0; i < idx; ++i) {
deck.add(cards[i]); // 초기 카드
}
while (true) {
answer++;
// 카드가 없는 경우 종료
if (idx >= len) break;
// 카드 추가
hand.add(cards[idx]);
hand.add(cards[idx + 1]);
idx += 2;
boolean found = false;
// Step 1: 기존 카드에서 조합 찾기
found = findPair(deck, deck, target);
// Step 2: 기존 카드 + 추가 카드에서 조합 찾기
if (!found && coin > 0) {
found = findPair(deck, hand, target);
if (found) coin--;
}
// Step 3: 추가 카드에서 조합 찾기
if (!found && coin > 1) {
found = findPair(hand, hand, target);
if (found) coin -= 2;
}
// Step 4: 조합이 없으면 종료
if (!found) break;
}
return answer;
}
static boolean findPair(List<Integer> list1, List<Integer> list2, int target) {
Map<Integer, Integer> map = new HashMap<>();
// 첫 번째 리스트의 카드들을 맵에 추가
for (int num : list1) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// 두 번째 리스트에서 조합 찾기
for (int num : list2) {
int complement = target - num;
if (map.getOrDefault(complement, 0) > 0) {
// 조합을 찾으면 리스트에서 제거
list1.remove(Integer.valueOf(complement));
list2.remove(Integer.valueOf(num));
return true;
}
}
return false;
}
}
풀이 과정(풀이 시간 : 1시간)
1. N+1만큼 카드 뭉치를 만든다.
2. 1에서 문제의 조건에 성립하지 않는다면, 추가로 뽑은 카드 1개를 사용해 N+1을 만든다.
3. 2에서 문제의 조건에 성립하지 않는다면, 추가로 뽑은 카드 2개를 사용해 N+1을 만든다.
4. 3에서 문제의 조건에 성립하지 않는다면, 다음 라운드 진행이 불가능하다.
1을 진행할 때는 0 개의 동전이, 2를 진행할 때는 최소 1개의 동전이, 3을 진행할 때는 최소 2개의 동전이 필요하다.
위 코드 로직을 보며 문제를 풀면 빠르게 이해할 수 있다.
내일은 1차 면접 최종 준비를 마칠 예정이다.
[참고 블로그]