[Java] n+1 카드게임 (2024 KAKAO WINTER INTERNSHIP)

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

해결방법

• 사용한 알고리즘: 그리디, 구현
• 접근 방법:
  • 현재 들고 있는 카드를 관리할 Set과 뽑은 카드를 관리할 Set을 사용합니다.
  • 3가지 경우를 순서대로 확인합니다. 오래 라운드를 진행할 수 있는 유리한 순서입니다.
    • 1. 코인을 쓰지 않고 n+1을 만족하는 카드가 2장 존재하는 경우 (카드를 안뽑아도 되는 경우)
    • 2. 코인을 하나만 쓰고 n+1을 만족하는 경우 (카드를 1장만 뽑아도 되는 경우)
    • 3. 코인 두 개를 써야 n+1을 만족하는 경우 (카드를 2장 뽑아야 하는 경우)
  • 3가지 모두 만족하지 않을 경우, 라운드는 종료됩니다.
  • 이렇게 구현하면 coin의 개수 또는 card 뭉치의 길이에 시간 복잡도가 의존됩니다. 따라서 O(n)에 풀이가 가능합니다.

코드

import java.util.*;

class Solution {
    
    public int solution(int coin, int[] cards) {
        int answer = 0;
    
        // 1. 코인을 안쓰고 n+1을 만족하는 경우
        // 2. 코인 하나를 쓰고 n+1을 만족하는 경우
        // 3. 코인 두 개를 써야 n+1을 만족하는 경우
        // 4. n+1을 만족하지 않는 경우
        
        int n = cards.length;
        int idx = n/3;
        
        // 숫자 중복 X, 포함관계만 확인하면 됨.
        Set<Integer> myCard = new HashSet<>();
        Set<Integer> newCard = new HashSet<>();
        
        for(int i=0; i<idx; i++) {
            myCard.add(cards[i]);
        }
        
        int target = n+1;
        while(true) {
            
            answer++;
            
            if(idx >= n) {
                break;
            }
            
            newCard.add(cards[idx]);
            newCard.add(cards[idx+1]);
            idx += 2;

            boolean flag = false;
            for(int num : myCard) {
                if(myCard.contains(target - num)) {
                    myCard.remove(num);
                    myCard.remove(target - num);
                    flag = true;
                    break;
                }
            }
            
            if(!flag) {
                if(coin >= 1) {
                    for(int num : myCard) {
                        if(newCard.contains(target - num)) {
                            myCard.remove(num);
                            newCard.remove(target - num);
                            coin--;
                            flag = true;
                            break;
                        }
                    } 
                }
            }
            
            if(!flag) {
                if(coin >= 2) {
                    for(int num : newCard) {
                        if(newCard.contains(target - num)) {
                            newCard.remove(num);
                            newCard.remove(target - num);
                            coin -= 2;
                            flag = true;
                            break;
                        }
                    } 
                }
            }
            
            if(!flag) {
                break;
            }
        }
        return answer;
    }
}

문제리뷰

• 저는 그리디하게 생각을 못해서 매 라운드마다 (뽑지 않는 경우, 1장만 뽑는 경우, 2장 뽑는 경우) 3가지 경우를 모두 완전탐색 하려고 하였습니다. 시간 초과가 우려되어 memorization을 활용하여 구현하였습니다. (구현을 제대로 하지 못했습니다..)
• 뽑은 카드를 관리하는 Set을 두고, 필요한 경우 코인을 소모해 가져가게 되면 특정 라운드에 얽매이지 않아도 된다는 점이 새로웠습니다.
  • 저는 매 라운드에서 뽑을 수 있는 카드가 정해져 있다고 생각했고, 라운드가 지나가면 해당 카드를 뽑을 수 없다고 생각했습니다.
  • 하지만 뽑은 카드들을 모두 Set에 넣어놓고, 필요할 때마다 꺼내면 해당 라운드에서 뽑았다고 생각할 수 있습니다.
• 그리디하게 생각하는 연습이 부족한 것 같습니다. 카카오 코테에서 생각보다 그리디 문제가 많이 나온다는 것을 알게되었습니다.