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

문제 설명

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 나동빈