알고리즘이 재미있다

[프로그래머스] n + 1 카드게임(java) 본문

카테고리 없음

[프로그래머스] n + 1 카드게임(java)

javajohaha 2024. 1. 5. 15:25

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

이 문제도 저번에 봤었는데, 시간이 없어서 제대로 분석하지 못했었다.

다시 여유 있을 때 지문을 읽어보니 단순 구현 문제였다.

 

핵심

직관적으로 생각하면 순간순간 카드를 받을지 말지에 대한 모든 케이스를 생각해야 할 것 같지만, 실제로는 모든 카드를 다 받고 사용할 때 코인을 제출하면 된다.

 

정답 코드

import java.util.ArrayList;
import java.util.List;

class Solution {

    private boolean[] used;
    private int coin;
    private boolean canNext = true;

    public int solution(int coin, int[] cards) {
        List<Integer> list = new ArrayList<>();
        used = new boolean[cards.length];
        this.coin = coin;

        for (int i = 0; i < cards.length / 3; i++) {
            list.add(cards[i]);
        }

        int round = 1;

        for (int i = cards.length / 3; i < cards.length; i += 2) {
            list.add(cards[i]);
            list.add(cards[i + 1]);
            submit(list, cards.length + 1, cards);

            if (this.coin < 0 || !canNext) {
                return round;
            }

            round++;
        }

        return round;
    }

    private void submit(List<Integer> list, int n, int[] cards) {
        for (int i = 0; i < cards.length / 3; i++) {
            for (int j = i + 1; j < cards.length / 3; j++) {
                if (list.get(i) + list.get(j) == n && !used[i] && !used[j]) {
                    used[i] = true;
                    used[j] = true;
                    return;
                }
            }
        }

        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if (list.get(i) + list.get(j) == n && !used[i] && !used[j]) {
                    used[i] = true;
                    used[j] = true;
                    if (i >= cards.length / 3) {
                        coin--;
                    }
                    if (j >= cards.length / 3) {
                        coin--;
                    }
                    return;
                }
            }
        }

        canNext = false;
    }
}

 

해설

우선 단순하게 지문에 나와있는 대로 n/3개의 카드를 받고, 이후에 각 라운드마다 2장을 받게 된다.

이후에 카드를 리스트에서 제거하는 방식을 사용해도 되지만,

그럴 경우 처음 덱에 있던 카드가 무엇인지 구분하기 어렵기에 boolean배열을 사용했다.

 

이후에 카드를 제거하면 다음 라운드에 진출하는데, 이때 카드를 제거하지 못하거나 coin의 개수가 0개 미만이 되면 게임을 종료한다.

여기서 submit 메서드를 보면 비용일 들지 않는 카드부터 버리는 것을 볼 수  있다.

이는 내가 나중에 찾은 케이스인데 coin = 0, {3 6 7 2 10....} 이런 식 일 때 비용이 들지 않는 것부터 하지 않으면 3과 10을 골라서 coin이 0개 미만이 되어 라운드가 1이 된다.

 

 

배운 점

저번에 풀기 전에는 문제 자체가 해석이 어려워 보였다.

다시 지문을 읽어보니 생각보다 단순한 구현문제였다.

또한 실제로 각각 카드를 받는지가 중요한 게 아닌 사용시점이 중요하다는 판단을 하는 게 중요한 것 같다.

꾸준히 풀면서 문제풀이 능력을 늘려보자.

 

자바의 첫 번째 풀이에 올라가게 되었다.