프로그래머스 (Java) 258707 : n + 1 카드게임

https://school.programmers.co.kr/learn/courses/30/lessons/258707

프로그래머스

 

---

풀이

다음 라운드로 갈 수 있는지를 확인하는 조건을 모르겠어서 다른 풀이를 봤다.

n + 1 을 만들 수 있는 조건이라면 코인을 최소로 사용해야 더 많은 라운드로 갈 수 있으니,

코인을 최대한 적게 쓰는 방향으로 각 라운드를 지나야 하는 게 포인트였다.

현재 가지고 있는 코인으로 다음 라운드를 갈 수 있는지 확인 -> 코인 1개로 갈 수 있는지 -> 2개로 갈 수 있는지를

순서대로 탐색했다.

 

현재 라운드에서 몇 개의 수를 들고 가야 할지가 고민이었는데next라는 예비 큐에 저장해두고 필요할 때에 코인과 바꾸는 방법을 사용한다면각 라운드와 상관 없이 총 게임에서 사용할 만큼의 숫자만 코인과 바꿀 수 있었다.

 

참고자료

[프로그래머스]n+1 카드게임 with Java

---

Java 코드

import java.util.*;
class Solution {
    public int solution(int coin, int[] cards) {
        Set<Integer> now, next;
        now = new HashSet<>();
        next = new HashSet<>();
        
        int round = 0;
        int n = cards.length;
        
        for (int i = 0; i < n / 3; i++) {
            now.add(cards[i]);
        }
        
        boolean goNext;
        int idx = n / 3;
        while (true) {
            round++;
            if (n <= idx) {
                break;
            }
            
            // 각 라운드가 지날 때마다 2개를 예비로 가짐
            next.add(cards[idx++]);
            next.add(cards[idx++]);
            
            // 현재 있는 카드들로 다음 라운드를 갈 수 있는지 확인
            goNext = false;
            for (int num : now) {
                if (now.contains(n - num + 1)) {
                    now.remove(num);
                    now.remove(n - num + 1);
                    goNext = true;
                    break;
                }
            }
                
            // 카드 하나만 가지고 갈 수 있는 지
            if (!goNext) {
                if (coin > 0) {
                    for (int num : now) {
                        if (next.contains(n - num + 1)) {
                            now.remove(num);
                            next.remove(n - num + 1);
                            coin--;
                            goNext = true;
                            break;
                        }
                    }
                }
            }
            
            // 두 개를 가지고 갈 수 있는지
            if (!goNext) {
                if (coin > 1) {
                    for (int num : next) {
                        if (next.contains(n - num + 1)) {
                            next.remove(num);
                            next.remove(n - num + 1);
                            coin -= 2;
                            goNext = true;
                            break;
                        }
                    }
                }
            }
            
            // 어떤 경우에도 다음 라운드를 갈 수 없다면
            if (!goNext) {
                break;
            }
        }
        return round;
    }
}