경우의 수를 자바를 이용하여 이해하기

코딩테스트 문제를 보면 경우의 수를 구하는 문제가 출제되는데 정말 어렵다고 생각한다.

그렇기 때문에 어떻게 경우의 수를 자바 프로그래밍을 통해서 구현하는지 알아볼려고 한다.

 

1. 경우의 수

    - 어떤 사건에서 일어날 수 있는 경우의 가짓수 를 의미한다.

      예를 들면, 동전을 던지는 사건 : 경우의 수 2, 주사위를 던지는 사건 : 경우의 수 6

      집합으로 표기 :  n(A)

2. 합의 법칙

    - 사건 A 또는 사건 B가 일어날 경우의 수를 의미한다.

      예를 들면, 두 개의 주사위를 던졌을 때 합이 3또는 4의 배수일 경우의 수

      사건 A : 합이 3의 배수일 경우 : 12가지

           3 : {1,2}, {2,1}

           6 : {1,5}, {2,4}, {3,3}, {4,2}, {5,1}

           9 : {3,6}, {4,5}, {5,4}, {6,3}

          12 : {6,6}

      사건 B : 합이 4의 배수일 경우 : 9 가지

            4 : {1,3}, {2,2}, {3,1}

            8 : {2,6}, {3,5}, {4,4}, {5,3}, {6,2}

           12 : {6,6}

      집합으로 표기 : n(AUB) = n(A) + n(B) - n(A ∩ B) : 12 + 9 - 1(12의 중복 제거) = 20 가지

3. 곱의 법칙

    - 사건 A와 사건 B가 동시에 일어날 경우의 수를 의미한다.

       예를 들면, 두 개의 주사위 a,b를 던졌을 때 a는 3의 배수, b는 4의 배수인 경우의 수

      사건 A : a가 3의 배수일 경우 : 2가지

          3, 6

      사건 B : b가 4의 배수일 경우 : 1가지

          4

      집합으로 표기 : n(A ∩ B) = n(A) X n(B) : 2 X 1  = 2 가지

 

자바로 구현해 보면 아래와 같다.

- 합의 법칙 경우 HashSet을 이용하여 해당 경우의 수를 추가해주면 HashSet 특성 상 중복이 제거 되므로 구현하기 편하다.

- 주사위 경우 각각의 경우의 수를 계산해서 합 또는 곱의 법칙인지 판단하여 구현하면 된다.

import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; public class Main {     public static void main(String[] args) {         // 1. 합의 법칙         System.out.println("== 합의 법칙 ==");         // 두 개의 주사를 던졌을 때 합이 3 또는 4의 배수일 경우의 수         int[] dice1 = { 1, 2, 3, 4, 5, 6 };         int[] dice2 = { 1, 2, 3, 4, 5, 6 };         int nA = 0;         int nB = 0;         int nAandB = 0;         // 기본 풀이         for (int itemA : dice1) {             for (int itemB : dice2) {                 if ((itemA + itemB) % 3 == 0) {                     nA += 1;                 }                  if ((itemA + itemB) % 4 == 0) {                      nB += 1;                  }                  if ((itemA + itemB) % 12 == 0) {                      nAandB += 1;                  }              }         }         int result = nA + nB - nAandB;         System.out.println("결과: " + result);         // HashSet 이용         HashSet<ArrayList> allCase = new HashSet();         for (int itemA : dice1) {             for (int itemB : dice2) {                 if ((itemA + itemB) % 3 == 0 || (itemA + itemB) % 4 == 0) {                     ArrayList list = new ArrayList(Arrays.asList(itemA, itemB));                     allCase.add(list);                 }             }         }         System.out.println("결과: " + allCase.size());         // 2. 곱의 법칙         System.out.println("== 곱의 법칙 ==");         // 두 개의 주사위 a, b를 던졌을 때 a는 3의 배수, b는 4의 배수인 경우의 수         nA = 0;         nB = 0;         for (int itemA : dice1) {             if (itemA % 3 == 0) {                 nA += 1;             }         }         for (int itemB : dice2) {             if (itemB % 4 == 0) {                 nB += 1;             }         }         System.out.println("결과: " + nA * nB);     } }