임스와 함께하는 미니게임 (BOJ 25757)

임스와 함께하는 미니게임 (BOJ 25757)

📖 문제 설명

임스와 함께 미니게임을 하려 한다.

게임 종류에 따라 한 판에 필요한 인원이 다르다.

• Y : 1명

• F : 2명

• O : 3명

신청한 사람들의 이름이 주어질 때,

임스가 총 몇 번 게임을 할 수 있는지 구하는 문제이다.

※ 같은 사람이 여러 번 신청할 수 있다.

✅ 조건 정리

• 신청 인원 수 N (1 ≤ N ≤ 100,000)

• 게임 종류: Y, F, O 중 하나

• 같은 사람이 여러 번 신청할 수 있음

• 중복 신청은 한 번만 인정

• 출력: 임스가 진행할 수 있는 게임 횟수

💡 풀이 방법

1️⃣ 접근 아이디어

핵심은:

🔥 “중복 제거”

같은 사람이 여러 번 신청할 수 있기 때문에

실제로 게임에 참여 가능한 인원은 중복 제거된 인원 수이다.

이를 위해 HashSet을 사용한다.

2️⃣ 게임 종류별 처리

게임 옵션에 따라 한 판에 필요한 인원이 다르다:

따라서:

게임 횟수 = (중복 제거된 인원 수) / (게임에 필요한 인원 수)

✔ 예시

입력:

7 F
a
b
c
a
d
b
e

중복 제거 후:

a, b, c, d, e → 총 5명

F는 2명 필요 →

5 / 2 = 2번 가능

💻 코드

package boj;

import java.io.*;
import java.util.*;

public class Boj10431 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int t = 1; t <= testCase; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int caseNum = Integer.parseInt(st.nextToken()); // 테스트 번호
            int[] arr = new int[20];
            int moveCount = 0;

            for (int i = 0; i < 20; i++) {
                arr[i] = Integer.parseInt(st.nextToken());

                // 현재 학생(arr[i])보다 앞에 있으면서 키 큰 학생 수 세기
                for (int j = 0; j < i; j++) {
                    if (arr[j] > arr[i]) {
                        moveCount++;
                    }
                }
            }

            sb.append(caseNum).append(" ").append(moveCount).append("\n");
        }

        System.out.print(sb);
    }
}

⏱ 시간 복잡도

• 시간복잡도: O(N)

• 공간복잡도: O(N)

🔎 배운 점 / 느낀 점

• 중복 제거 문제에서는 Set이 가장 간단한 해결 방법이다.

• 조건 분기는 나누기 연산 하나로 해결 가능하다.

• 자료구조 선택이 문제 난이도를 크게 낮춘다.