[백준, 1233번] 주사위 (브루트 포스, 구현, Java)

 

문제설명

입력 & 출력

나의 풀이

이번 문제는 3개의 주사위를 던졌을 때 나오는 합 중 가장 자주 등장하는 값을 구하는 문제입니다. 주사위의 면 수가 주어지고, 각 주사위가 가질 수 있는 눈의 합을 구해서 그 중 가장 많이 나오는 합을 찾아야 합니다.

 

예제 입력 3 2 3을 예로 들자면,

 

• 3 ➡️ (1, 1, 1)
• 4 ➡️ (1, 1, 2), (1, 2, 1), (2, 1, 1)
• 5 ➡️ (1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 1, 2), (2, 2, 1), (3, 1, 1)
• 6 ➡️ (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 2, 2), (2, 3, 1), (3, 1, 2), (3, 2, 1)
• 7 ➡️ (1, 3, 3), (2, 2, 3), (2, 3, 2), (3, 1, 3), (3, 2, 2), (3, 3, 1)
• 8 ➡️ (2, 3, 3), (3, 2, 3), (3, 3, 2)

 

3 2 3이 입력되었을 때는 5와 6이 가장 많이 등장하는 합입니다. 근데 이때 값이 여러개면 작은 값이 정답이 됩니다.

 

주사위 면 배열 생성 

• getArray(S) 메서드를 사용하여 각 주사위의 면 배열을 생성합니다.
• 예를 들어, S1 = 3이면 s1_array는 {1, 2, 3}이 됩니다.

3중 반복문을 통한 모든 합 계산 

• 세 개의 주사위에 대해 각각 S1, S2, S3의 면 수에 대해 가능한 모든 조합을 계산합니다.
• 각 조합의 합을 구하고, 그 합의 빈도를 HashMap에 기록합니다.
• 빈도를 계산할 때 HashMap의 getOrDefault 메서드를 사용하여 각 합의 빈도를 추적합니다.
• 이 메서드는 주어진 키가 존재하지 않으면 기본값을 반환하고, 존재하면 해당 값을 반환하는 방식으로 작동합니다. 이를 통해 주사위의 각 조합에 대한 합의 빈도를 계산하고, 값을 1씩 증가시킬 수 있습니다.
• 예를 들어, S1 = 3, S2 = 2, S3 = 3일 경우 (1, 1, 1), (1, 1, 2), (1, 1, 3) 등의 모든 조합을 확인하고 그 합을 계산합니다.

 

빈도 계산 후 최대값 찾기 

• HashMap에서 각 합의 빈도를 계산한 후, 가장 자주 나온 합을 찾습니다.
• 가장 자주 나온 합이 여러 개 있을 수 있으므로, 그 중에서 가장 작은 합을 선택합니다.

결과 출력 

• 가장 자주 나온 합 중에서 가장 작은 값을 출력합니다.

 

 

refactoring ✅

 

입력 받기 

• BufferedReader와 StringTokenizer를 사용하여 S1, S2, S3 값을 입력받습니다.
• 이 값들은 각각 첫 번째, 두 번째, 세 번째 주사위의 면의 개수입니다.

합의 빈도 계산 

• arr 배열은 주사위 세 개의 합이 나올 수 있는 가능한 모든 값에 대해 빈도를 기록하는 배열입니다.
• 주사위 면 수가 최대 2, 3, 2일 경우 가능한 합은 최대 9이므로, arr 배열의 크기는 S1 + S2 + S3 + 1로 설정됩니다.
  • 배열은 0부터 시작하는 0-based index를 사용하기 때문
• 브루트포스(Brute Force)방식을 사용하기 위해3중 for문을 통해 각 주사위에서 나올 수 있는 값들의 합을 계산하고, 그 합의 빈도를 arr[i + j + k]에 증가시킵니다.

가장 큰 값 구하기 

• Arrays.stream(arr).max()를 사용하여 arr 배열에서 가장 큰 값을 찾습니다.
• 이 값은 가장 많이 나오는 합의 빈도입니다. 

가장 자주 나온 합 찾기 

• arr 배열을 순회하면서, 가장 빈도가 높았던 합을 찾습니다.
• 이 때, 같은 빈도의 합이 여러 번 나올 수 있기 때문에, 가장 작은 합을 선택하기 위해 조건 i < result를 사용합니다.

결과 출력 

• result는 가장 빈도가 높은 합을 저장하고 있으며, 이 값은 1부터 시작하기 때문에합니다.

[Algorithm] 완전 탐색, 브루트 포스: 가장 단순한 알고리즘(Brute Force) 알아보기