[백준] 3758번 KCPC JAVA (자바) 풀이

문제 3758

 

• 총 k개의 문제
• 문제에 대한 점수 = 0점 ~ 100점
• 풀이를 제출한 팀의 ID, 문제 번호, 점수 시간 순서대로 저장
• 한 문제에 대한 풀이를 여러 번 제출할 수 있고 그 중 최고 점수
• 풀이를 한번도 제출하지 않았으면 0점
  
  
• 팀 최종 점수 = 각 문제의 최고 점수의 총합
• 팀 순위 = 현재 팀보다 높은 점수를 받은 팀의 수 + 1 

 

1. 최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다. 
2. 최종 점수도 같고 제출 횟수도 같은 경우, 마지막 제출 시간이 더 빠른 팀의 순위가 높다. 

 

[입력]

 

 :  첫 번째 줄 테스트 데이터의 수 T

 :  각 테스트 데이터의 첫 번째 줄 팀의 개수 n, 문제의 개수 k, 당신 팀의 ID t, 로그 엔트리의 개수 m

 :  다음 m개의 줄에 각 풀이에 대한 정보가 제출되는 순서대로 주어진다

 :  각 줄에는 팀 ID i, 문제 번호 j, 획득한 점수 s를 나타내는 세 개의 정수가 주어진다

 :  첫 줄에 물품의 수 N(1 ≤ N ≤ 100), 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)
 :  두 번째 줄부터 N개의 줄까지 물건 무게 W(1 ≤ W ≤ 100,000), 해당 물건의 가치 V(0 ≤ V ≤ 1,000)

 

 

 [출력]

 :  각 테스트 데이터에 대해 당신 팀의 순위  출력

 

 

[구조]

 

• Team 클래스: 대회 참가 팀
  • int id: 팀 고유 번호
  • int[] scoreList: 팀의 점수를 저장 (=해당 문제의 최고 점수를 저장)
  • int submitNum: 풀이 제출 횟수
  • int lastSubmit: 마지막으로 제출한 순서
  • int totalScore: 팀의 총 점수
• main 메서드: 프로그램 시작

 

[코드]

import java.io.*;
import java.util.*;

public class Main {

	static class Team {
		int id;
		int[] scoreList;
		int submitNum;
		int lastSubmit;
		int totalScore;

	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(br.readLine());
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		for (int T = 0; T < testCase; T++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken()); // 팀 수
			int k = Integer.parseInt(st.nextToken()); // 문제수k
			int t = Integer.parseInt(st.nextToken()); // 내 팀ID
			int m = Integer.parseInt(st.nextToken()); // 로그개수

			Team[] list = new Team[n];
			for (int i = 0; i < m; i++) {
				// 로그수만큼 반복
				st = new StringTokenizer(br.readLine());
				int teamID = Integer.parseInt(st.nextToken());
				int problemNum = Integer.parseInt(st.nextToken());
				int score = Integer.parseInt(st.nextToken());

				if (list[teamID - 1] == null) {
					list[teamID - 1] = new Team();
					list[teamID - 1].id = teamID;
					list[teamID - 1].scoreList = new int[k + 1];
				}

				list[teamID - 1].scoreList[problemNum] = Math.max(score, list[teamID - 1].scoreList[problemNum]);
				list[teamID - 1].submitNum++;
				list[teamID - 1].lastSubmit = i;

			}
			for (int i = 0; i < n; i++) {
				int sum = 0;
				for (int j = 1; j <= k; j++) {
					sum += list[i].scoreList[j];
				}
				list[i].totalScore = sum;
			}

			Arrays.sort(list, new Comparator<Team>() {

				@Override
				public int compare(Team o1, Team o2) {
					// TODO Auto-generated method stub
					if (o1.totalScore == o2.totalScore) {
						if (o1.submitNum == o2.submitNum) {
							// 제출횟수는 적은게 좋다.
							return o1.lastSubmit - o2.lastSubmit;
						}
						return o1.submitNum - o2.submitNum;
					}
					return o2.totalScore - o1.totalScore;// 점수는 높은게 좋다.
				}
			});

			for (int i = 0; i < n; i++) {
				if (list[i].id == t) {
					// 내 팀 찾음
					bw.append(String.valueOf(i + 1) + "\n");
				}
			}
		}
		bw.flush();
		bw.close();
		br.close();
	}
}

 

 [해설]
     

 :  static class Team {
         int id; 팀 고유 번호

         int[] scoreList;  팀의 점수를 저장 (=해당 문제의 최고 점수를 저장)
         int submitNum;  풀이 제출 횟수
         int lastSubmit;  마지막으로 제출한 순서
         int totalScore;  팀의 총 점수

    }

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

 

 :  int testCase = Integer.parseInt(br.readLine()); 첫째줄 입력 테스트케이스 수

 :  for (int T = 0; T < testCase; T++) {

          StringTokenizer st = new StringTokenizer(br.readLine());
          int n = Integer.parseInt(st.nextToken());  팀 수
          int k = Integer.parseInt(st.nextToken());  문제수k
          int t = Integer.parseInt(st.nextToken());  내 팀ID
          int m = Integer.parseInt(st.nextToken());  로그개수

 :  Team[] list = new Team[n];  팀정보 초기화

 

 :  for (int i = 0; i < m; i++) { 로그수만큼 반복
         st = new StringTokenizer(br.readLine());
         int teamID = Integer.parseInt(st.nextToken());  팀 ID
         int problemNum = Integer.parseInt(st.nextToken());  문제 번호
         int score = Integer.parseInt(st.nextToken());  점수

 :  if (list[teamID - 1] == null) 
          list[teamID - 1] = new Team();  Team 객체 생성 = 초기화
          list[teamID - 1].id = teamID; 
          list[teamID - 1].scoreList = new int[k + 1];  문제 수 + 1로 초기화 (문제번호가 1부터 시작해서)
    }

 :  list[teamID - 1].scoreList[problemNum] = Math.max(score, list[teamID - 1].scoreList[problemNum]);

   현재 로그에 기록된 점수가 기존 점수보다 높은 경우에만 업데이트
    list[teamID - 1].submitNum++;  제출 횟수 1 증가
    list[teamID - 1].lastSubmit = i;  마지막 제출 순서 = 현재 로그의 순서로 설정

 :  for (int i = 0; i < n; i++) { 총점 계산

          int sum = 0;
          for (int j = 1; j <= k; j++) {
                    sum += list[i].scoreList[j];  모든 문제에 대한 점수를 합산
          }
          list[i].totalScore = sum;
    }

 :  Arrays.sort(list, new Comparator<Team>() { 팀 정렬

          @Override
          public int compare(Team o1, Team o2) {
          if (o1.totalScore == o2.totalScore) {
              if (o1.submitNum == o2.submitNum) {
                      return o1.lastSubmit - o2.lastSubmit;  마지막 제출 순서(오름차순)
              }
              return o1.submitNum - o2.submitNum;  제출 횟수(오름차순)
          }
          return o2.totalScore - o1.totalScore; 정렬 기준은 총점(내림차순)
    }


 :  for (int i = 0; i < n; i++) {  순위 출력 

          if (list[i].id == t) { 정렬된 배열에서 자신의 팀(t)을 찾기
                    bw.append(String.valueOf(i + 1) + "\n"); 배열의 인덱스는 0부터 시작하니까 1을 더하기

          }
    }

 

 :  bw.flush();
    bw.close();
    br.close();

    


 

 

이제 풀어보러 갈께요 :)

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

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

3758번: KCPC