PS/이코테

[이코테][Java] 볼링공 고르기

nyrimmm 2025. 2. 14. 02:22

문제 설명

A, B 두 사람이 서로 무게가 다른 볼링공을 골라 볼링을 치고 있습니다.

볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여됩니다. 볼링공의 무게는 1부터 M까지 자연수의 형태로 존재하고, 같은 무게의 공은 서로 다른 공으로 간주합니다.

두 사람이  서로 다른 무게의 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하세요.

 

입력조건

  • 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M(1 ≤ N ≤ 1000, 1 ≤ M ≤ 10)
  • 둘째 줄에 각 볼링공의 무게 K(1 ≤ K ≤ M)

출력조건

  • 두 사람이 볼링공을 고르는 경우의 수

입출력 예시

입력예시 출력예시
5 3
1 3 2 3 2
8
8 5
1 5 4 3 2 4 5 2
25

 

 

 

문제 풀이

  • n개의 볼링공을 입력받은 후, 순차적으로 두 볼링공의 무게를 비교해서 다른 경우 카운트한다.
  • 하지만 이 방법은 비효율적이다.
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());   //볼링공의 개수
        int m = Integer.parseInt(st.nextToken());   //공의 최대 무게

        st = new StringTokenizer(br.readLine());
        ArrayList<Integer> balls = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            balls.add(Integer.parseInt(st.nextToken()));
        }

        int count = 0;
        for (int i = 0; i < balls.size() - 1; i++) {
            for (int j = i + 1; j < balls.size(); j++) {
                if (balls.get(i) != balls.get(j)) {
                    count++;
                }
            }
        }

        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
    }
}

 

 

 

효율적인 방법

  • 무게마다 볼링공이 몇 개 있는지 계산한 후, 무게가 낮은 공부터 높은 공까지 순서대로 확인한다.
  • 무게가 낮은 공부터 (해당 무게의 볼링공 개수) × (해당 무게의 볼링공보다 무거운 볼링공 개수) 를 합한다.
  • ex) n=5, m=3, {1, 3, 2, 3, 2}일 때,
    무게 1 → 1 × 4 = 4
    무게 2 → 2 × 2 = 4
    무게 3 → 2 × 0 = 0
    로 가능한 경우는 총 8가지이다.
public class Main1 {

    public static int n, m;
    public static int[] balls = new int[11];    //볼링공의 무게를 담을 수 있는 배열
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int weight = sc.nextInt();
            balls[weight]++;    //무게별로 볼링공이 몇 개 있는지 카운트
        }

        int count = 0;
        //무게가 낮은 공부터 높은 공 순으로 확인
        for (int i = 1; i <= m; i++) {
            n -= balls[i];  //i보다 무거운 볼링공의 개수
            count += balls[i] * n;  //무게가 i인 볼링공의 개수 * i보다 무거운 볼링공의 개수
        }

        System.out.println(count);
    }
}

 

[참고서적]

이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈