구현
프로그래머스 2024 KAKAO WINTER INTERNSHIP Level 3 문제 n + 1 카드게임을 Java를 이용해 풀어보았다.
기존에 하고있던 삽질과 성공한 풀이를 적어보자.
문제 링크 첨부한다.
https://school.programmers.co.kr/learn/courses/30/lessons/258707
시간초과
기존의 내 풀이는 테스트 케이스 8개만을 통과하고 나머지 12개는 계속 시간초과가 났다. 모든 경우의 수를 다 파악해야 한다고 굳게 믿은 채로 문제를 풀기 시작했다. 그래서 시간 복잡도 측면에서는 생각하지 못했다. 내가 불필요하게 중복해서 계산하고 있는 로직이 있는지 몇시간을 살펴봤다. 하지만 완전탐색 로직 자체에는 중복된 계산이 없었다.
나중에 깨닫게 된 것은 n이 1000으로 제한되어 있고, 6의 배수여야 하기 때문에 가장 큰 n은 996이라는 것. 그리고 332개는 초기 상태에서 집어넣는다. 남은 664개에 대해서 먹을지 안 먹을지를 모두 따져본다고 하면 결국 2^664가 되는 것이다. (2^10)^66 -> 1000^66. 당연히 시간 초과가 날 수밖에 없었다.
그래서 모든 경우의 수를 검사하는 것이 아니라, 매순간 최적의 선택을 하는 방향으로 풀이의 방향을 바꿨다.
소유 & 후보
두 개의 List를 이용해서 풀이를 진행한다. 하나는 실제로 소유하고 있는 카드, 하나는 잠재적으로 취할 수 있는 후보 카드.
후보 카드라 함은, 소유 카드들만으로 다음 라운드 진출이 불가능할 때 코인을 소진해서 취할 수 있는 카드들을 뜻한다. 매 라운드마다 2장씩 꺼내는 카드를 후보 카드에 저장해둘 것이다.
풀이 전략
다음 세 가지 step을 거치며 다음 라운드에 진출할 것이다.
- 소유 카드만으로 다음 라운드 진출이 가능할 경우, 소유 카드 2장을 소진하고 코인은 소진하지 않는다. 그저 후보 카드에 2장의 카드를 넣어둘 뿐이다.
- step 1 에 실패하면, 소유 카드 1장과 후보 카드 1장을 조합해서 다음 라운드에 진출한다. 이때 코인을 1개 소진하게 된다.
- step 1과 step 2 모두 실패하면, 후보 카드 2장을 조합해서 다음 라운드에 진출한다. 이때 코인을 2개 소진하게 된다.
- 위 3개 step에 모두 실패하면 게임을 종료한다.
추가로 매 라운드마다 두 가지 조건을 확인하며 게임 종료 여부를 판단한다.
- 가능한 최대 라운드에 이미 도달했는지
- 카드 뭉치에 더이상 뽑을 카드가 없는지
초기 세팅
우선 n/3 만큼의 카드를 소유 카드 List에 넣어둔다. 매 라운드마다 2장의 카드를 뽑게 될텐데 이 카드들의 index를 설정해둔다. 코드로 표현하면 아래와 같다.
int round = 1; // 1 라운드부터 시작
n = cards.length;
int curIdx = n / 3; // 처음으로 뽑게될 카드의 index. 뽑을 때마다 index를 증가시켜줄 것
List<Integer> possession = new ArrayList<>();
for (int i = 0; i < curIdx; i++) {
possession.add(cards[i]);
}
List<Integer> candidates = new ArrayList<>(); // 매 라운드마다 2장 뽑고 넣어둘 List구체화
step 1
먼저 step 1 을 살펴보자.
소유 카드 List에서 n+1을 만드는 조합을 찾으면 그 카드들을 사용해서 없애주면 된다. 이를 코드로 구체화시키면 다음과 같다.
if (findNPlusOne(possession)) { // 소유 카드만으로 n+1 만들 수 있다면
round++; // 라운드 1 증가시키고
continue; // 다음 턴
}여기서 findNPlusOne(List<Integer>) 라는 메소드의 역할은 다음과 같다. 주어진 List 안에서 n+1을 만들 수 있는지 판단하고, 만들 수 있다면 그 조합을 만드는 카드들을 제거해주는 역할이다.
boolean findNPlusOne(List<Integer> list) {
if (list.isEmpty()) {
return false;
}
Collections.sort(list);
/* 이분탐색으로 타겟 찾기 */
for (int i = 0; i < list.size() - 1; i++) {
int target = n + 1 - list.get(i);
int l = 0;
int r = list.size() - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (list.get(mid) < target) {
l = mid + 1;
} else if (list.get(mid) > target) {
r = mid - 1;
} else {
list.remove(mid);
list.remove(i);
return true;
}
}
}
return false;
}처음 잘못된 풀이로 접근할 때 구현해둔 이분탐색을 이용한 방법이다. 물론 이분탐색을 사용하지 않아도 현재 풀이에서는 통과가 되겠지만 이미 구현해둔 것이 있어서 그냥 사용했다.
step 2
소유 카드 1장과 후보 카드 1장을 이용해서 다음 라운드 진출이 가능한지 살펴볼 것이다.
물론 후보 카드 1장을 사용해야 하기 때문에 코인이 최소 1개 이상 있어야 하는 전제 하에서 시작될 것이다.
소유 카드 1장씩 돌아가며, 해당 카드의 짝이 될 수 있는 카드가 후보에 존재하는지 확인할 것이다.
존재함을 확인하면 각 카드를 List에서 제거하고, 라운드를 증가시킨 채 다음 턴으로 넘어갈 것이다. 이를 코드로 표현하면 다음과 같다.
if (coin > 0) {
for (int i = 0; i < possession.size(); i++) {
int target = n + 1 - possession.get(i);
if (candidates.contains(target)) { // 짝이 후보군에 존재하는지
possession.remove(possession.get(i));
candidates.remove((Integer) target);
coin--;
round++;
continue L;
}
}
}step 3
마지막으로 오로지 후보 카드 2장만을 사용해서 다음 라운드로 진출이 가능한지를 확인해볼 것이다. 물론 코인 2개 이상이 존재하는 경우에만 가능하다.
이번에는 후보 카드 List 만을 확인해보면 된다. 소유 카드를 사용해서는 다음 라운드 진출이 불가능한 것을 이미 step 1과 step 2에서 실패했기 때문에 확인된 상태다.
만약 코인은 넉넉하지만, 후보 카드만을 사용해서도 n+1 조합을 찾을 수 없다면 게임은 종료된다.
혹은 코인 자체가 없어서 후보 카드 사용 기회조차도 없다면 그것 또한 게임 종료다.
step 1 에서 사용한 findNPlusOne(List<Integer>) 메소드를 재사용할 것이다.
if (coin > 1) {
if (findNPlusOne(candidates)) {
coin -= 2;
round++;
} else { // 후보 카드 이용해서 n+1 만들기 실패
break;
}
} else { // 후보 카드 사용조차 못해서 n+1 만들기 실패
break;
}마무리
시간 초과가 나는 경우를 접할 때마다, 현재 틀린 내 풀이를 몇줄 고쳐서 어떻게든 통과시키려 할 때가 많다. 아마도 새로운 풀이를 떠올리기 싫어서 무의식에 그런 식으로 반응하는 것 같다. 시간 초과가 났다면, 즉시 내 풀이 자체가 틀렸다는 것을 인지하는 연습을 해야할 것 같다. 잘 안되니까 그냥 외워.
시간 초과 나면 그냥 풀이를 바꿔라
완전 탐색을 하고 있는 상황에서 시간 초과가 났는데도 계속 완전 탐색으로 풀려고 하는 시도 자체가 나중에 보면 모양새가 참 우습지만 매번 반복한다는 사실에 열이 좀 받는다.
다음은 전체 코드다.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class 문제 {
static int n;
public static void main(String[] args) {
int coin = 10;
int[] cards = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18};
int result = solution(coin, cards);
System.out.println(result);
}
public static int solution(int coin, int[] cards) {
int round = 1;
n = cards.length;
int curIdx = n / 3;
List<Integer> possession = new ArrayList<>();
for (int i = 0; i < curIdx; i++) {
possession.add(cards[i]);
}
List<Integer> candidates = new ArrayList<>();
L:
while (true) {
/* 반복문 종료 조건 */
if (round > n / 3 + 1) { // 가능한 최대 라운드 넘어가면 종료
break;
}
if (curIdx >= n) { // 카드 뭉치가 모두 소진되면 종료
break;
}
/* 우선 후보군에 두 장 넣어둠 */
candidates.add(cards[curIdx++]);
candidates.add(cards[curIdx++]);
/* 소유 중인 카드에서 n+1 가능하면 coin 안 쓰고 다음 라운드 진출 */
if (findNPlusOne(possession)) {
round++;
continue;
}
/* 소유 카드 중 1개 + 후보군 1개 로 n+1 가능하면 코인 1개 소진 */
if (coin > 0) {
for (int i = 0; i < possession.size(); i++) {
int target = n + 1 - possession.get(i);
if (candidates.contains(target)) {
possession.remove(possession.get(i));
candidates.remove((Integer) target);
coin--;
round++;
continue L;
}
}
}
/* 후보군에서만 2장으로 n+1 만들 수 있는 경우에는 코인 2개 소진 */
if (coin > 1) {
if (findNPlusOne(candidates)) {
coin -= 2;
round++;
} else {
break;
}
} else {
break;
}
}
return round;
}
static boolean findNPlusOne(List<Integer> list) {
if (list.isEmpty()) {
return false;
}
Collections.sort(list);
/* 이분탐색으로 타겟 찾기 */
for (int i = 0; i < list.size() - 1; i++) {
int target = n + 1 - list.get(i);
int l = 0;
int r = list.size() - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (list.get(mid) < target) {
l = mid + 1;
} else if (list.get(mid) > target) {
r = mid - 1;
} else {
list.remove(mid);
list.remove(i);
return true;
}
}
}
return false;
}
}