[백준] 2303번 : 숫자 게임 자바(JAVA) 풀이

문제

---

https://www.acmicpc.net/problem/2303

---

문제 탐색하기

• 5장의 카드 중 3장을 더한 합의 일의 자리 수가 큰 사람의 번호 출력하기
• 일의 자리 수가 같은 경우, 번호가 큰 사람을 출력

 

가능한 시간복잡도

입력 범위 ( 2 ≤ N ≤ 1000)

1. 가장 큰 일의 자리 수 구하기
   • 5장 중 3장을 고르는 조합 5*4*3 = 60
   • 각 사람에 대해 최대 60번의 연산 수행
   • 시간 복잡도 O(N*60)
2. N명의 사람 중 가장 큰 수를 가지고 있는 사람 탐색 시간 복잡도 O(N)
3. 전체 시간 복잡도 시간 복잡도 O(60*N ) + O(N)

---

코드 설계하기

1. 각 사람 당 입력 받은 카드 값 저장
2. 카드 조합
   • 각 사람에게 주어진 5장의 카드 중 3장을 선택하는 조합 계산
3. 일의 자리 계산
   • 그 조합의 합을 계산하고 그 합의 일의 자리 수 구함
   • (card[i] + card[j] + card[k]) % 10 로 일의 자리 수 구함
4. 최대 일의 자리 수 선택
   • 각 사람의 조합 중 일의 자리 수가 가장 큰 값을 저장
   • 최대 일의 자리 수를 저장하는 maxOfOnes 배열에 각 사람의 최대 일의 자리 값 저장
5. 최종 승자 선택
   • 일의 자리 수가 가장 큰 사람을 찾음
   • 동일한 값인 경우, 번호가 더 큰 사람을 선택 

---

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // 사람 수
		int now = 0; // 현재 계산된 값의 일의 자리 수 
		int[] maxOfOnes = new int[N];// 각 사람의 가장 큰 일의 자리 저장할 변수
		
		StringTokenizer st;
		int[] card = new int[5]; // 한 사람당 카드 5장
		for(int t=0;t<N;t++) {
			st = new StringTokenizer(br.readLine());
			
			// 입력받은 카드 값 저장
			for(int i=0;i<5;i++) {
				card[i] = Integer.parseInt(st.nextToken());
			}
			
			// 입력받은 카드 5장 중 3장을 선택하는 모든 경우의 수에서 일의 자리가 가장 큰 값 찾기 
			for(int i=0;i<5;i++) {
				for(int j=i+1;j<5;j++) {
					for(int k=j+1;k<5;k++) {
						now = (card[i]+card[j]+card[k]) % 10; // 3장 합의 일의 자리
						if(now > maxOfOnes[t]) { // 현재 계산된 값의 일의 자리 수가 더 큰 경우
							maxOfOnes[t] = now; // 가장 큰 값 저장
						}
						
					}
				}
			}
		}

		int ans=0; // 일의 자리가 가장 큰 값을 저장
		int ans_person = 0; // 가장 큰 값을 가진 사람의 번호
		
		// 가장 큰 일의 자리가 젤 큰 경우 찾기
		for(int i=0;i<N;i++) {
			// 일의 자리가 크거나 같으면, 나중에 나오는 사람 선택 (번호가 더 큰 사람을 자동으로 선택)
			if(maxOfOnes[i] >= ans) {
				ans = maxOfOnes[i];
				ans_person = i+1;
			}
		}
		
		System.out.println(ans_person);
		
	}
}