[이것이 코딩 테스트다 with Java] 그리디 예제 - 볼링공 고르기

볼링공 고르기

난이도 ●○○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB | 기출 2019 SW  마에스트로 입학 테스트

A,B 두 사람이 볼링을 치고 있습니다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 합니다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여됩니다. 또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주합니다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재합니다.
예를 들어 N이 5이고, M이 3이며 각각의 무게가 차례대로 1,3,2,3,2일 때 각 공의 번호가 차례대로 1번부터 5번까지 부여됩니다. 이때 두 사람이 고를 수 있는 볼링공 번호의 조합을 구하면 다음과 같습니다

(1번, 2번), (1번, 3번), (1번, 4번), (1번, 5번), (2번, 3번), (2번, 5번), (3번, 4번), (4번, 5번)

결과적으로 두 사람이 공을 고르는 경우의 수는 8가지입니다. N개의 공의 무게가 각각 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하세요.

 

입력 조건

• 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어집니다.
  (1<=N<=1,000 ,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

요점

• 2중 for 문으로도 구현할 수 있지만 효율적이지 않다.
• 무게 별 볼링공의 개수를 파악한다. 첫 번째를 입력 예시로 들 때 무게별 볼링공은 다음과 같다.
  
  • 무게가 1인 볼링공: 1개
  • 무게가 2인 볼링공: 2개
  • 무게가 3인 볼링공 2개
• 위 기준으로 가능한 조합은 아래와 같다.
  이미 조합했던 경우는 제외하기 때문에 B의 수가 점점 줄어든다. 아래에 따라 가능한 경우의 수는 총 8가지다

STEP 1	A가 무게가 1인 공을 선택할 때의 경우의 수
	1(무게가 1인 공의 개수) X 4(무게가 1보다 큰 공의 개수) = 4
STEP 2	A가 무게가 2인 공을 선택할 때의 경우의 수
	2(무게가 2인 공의 개수) X 2(무게가 2보다 큰 공의 개수) = 4
STEP 3	A가 무게가 3인 공을 선택할 때의 경우의 수
	2(무게가 3인 공의 개수) X 0(무게가 3보다 큰 공의 개수) = 0

소스 코드

import java.util.*;

public class Main
{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int ballCnt = scan.nextInt();
		int maxWeight = scan.nextInt();
		int count[] = new int[maxWeight+1];
		int result = 0;
		
		for(int i = 0; i < ballCnt; i++){
			int weight = scan.nextInt();
			
			count[weight]++;
		}
		
		for(int i = 1; i <= maxWeight; i++){ 
			ballCnt -= count[i]; // A가 선택할 수 있는 개수 제외
			result += (ballCnt * count[i]); // B가 선택하는 경우의 수와 곱해주기
		}
		
		System.out.println("result = " + result);
	}
}

 

문제 풀이 후기

처음에 냅다 2중 for문으로 풀었는데 너무 효율성을 생각 안하고 푼 것 같아서 반성했다. 아무래도 정해진 시간 제한이 있다보니 주로 방법이라고 생각하는 아이디어로 빠르게 구현하는데 앞으로는 효율성을 다시 한 번 생각해봐야겠다.

 

GitHub: https://github.com/Leeyeonjae/coding-test/blob/main/11_Greedy_Example/11_5_bowlingBall.java

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