[ 백준 ] 21775 가희와 자원 놀이

📌 Problem

N명의 친구들이 자원 놀이를 한다. 자원 놀이는 주어진 순서에 따라 자신의 차례가 되면 하나의 카드를 수행하며 자원을 모으는 것이다. 카드의 종류는 다음과 같이 있다.

next - 어떠한 것도 하지 않으며 넘어간다.
acquire n - 자원 n을 요청한다.
    - 만약 다른 사람이 자원 n을 가지고 있다면 해당 카드를 본인이 hold하고 넘어간다.
release n - 자원 n을 반환한다.

자원은 1번부터 2,000,000,000번까지 하나씩 존재한다.

참가자들은 자신의 차례가 되면 카드를 하나 뽑아서 수행한다. 다만, 본인이 카드 하나를 hold하고 있다면 카드를 뽑지않고 hold하는 카드를 수행한다. 각 턴에서 수행되는 카드의 번호를 출력한다.

📌 Solution

참가 가능한 사람의 수가 최대 500,000명이고 자원의 개수 또한 2,000,000,000개로 굉장히 크기 때문에 메모리 관리를 잘 해야 한다. 우리가 알아야 하는 것은 어떤 사람이 어떤 자원을 가지고 있냐가 아니다. 그렇기 때문에 특정 자원을 누군가가 가져갔는지에 대한 여부만 알면 된다. 그러면 보통 다음과 같이 자료구조를 초기화한다.

boolean[] resources = new boolean[SIZE];

그러면 메모리가 너무 커지기 때문에 다음과 같이 선언한다.

Set<Integer> takenResources = new HashSet<>();

그리고 누군가가 자원을 가져갔다면 Set에 추가한다.

사람 또한 마찬가지이다. 다음과 List를 통해 모든 사람을 초기화하면 메모리가 커진다.

List<Player> players = new ArrayList<>();

이를 다음과 같이 초기화한다.

Map<Integer, Card> playersHoldingCard = new HashMap<>();

이러면 카드를 hold하고 있는 사람만 판별할 수 있다.

📌 Code

StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(tokenizer.nextToken());
int T = Integer.parseInt(tokenizer.nextToken());

Queue<Integer> playSequence = Arrays.stream(reader.readLine().split(" "))
        .map(Integer::valueOf).collect(Collectors.toCollection(LinkedList::new));

Queue<Card> cards = new LinkedList<>();
while (T-- > 0) cards.offer(new Card(reader.readLine().split(" ")));

Game game = new Game(cards);

while (!playSequence.isEmpty()) 
	result.append(game.play(playSequence.poll())).append('\n');

class Game {

    private final Map<Integer, Card> playersHoldingCard = new HashMap<>();
    private final Set<Integer> takenResources = new HashSet<>();
    private final Queue<Card> cards;

    public Game(Queue<Card> cards) {
        this.cards = cards;
    }

    public int play(int pno) {
        Card card = playersHoldingCard.get(pno);
        if (card != null) {
            if (!takenResources.contains(card.getRNO())) {
                playersHoldingCard.remove(pno);
                takenResources.add(card.getRNO());
            }
        } else {
            card = cards.poll();
            assert card != null;
            if (card.commandOfCard().equals("acquire"))
                if (takenResources.contains(card.getRNO())) playersHoldingCard.put(pno, card);
                else takenResources.add(card.getRNO());
            else if (card.commandOfCard().equals("release")) takenResources.remove(card.getRNO());
        }
        return card.getCNO();
    }
}

class Card {

    private final int CNO;
    private final String COMMAND;
    private final int RNO;

    public Card(String... infos) {
        CNO = Integer.parseInt(infos[0]);
        COMMAND = infos[1];
        RNO = infos.length == 3 ? Integer.parseInt(infos[2]) : 0;
    }

    public int getCNO() {
        return CNO;
    }

    public String commandOfCard() {
        return COMMAND;
    }

    public int getRNO() {
        return RNO;
    }
}