[백준] KCPC 3758번(🥈실버2)

사이트

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

 

문제

 

분석

아 열심히 작성했는데 날라갔다..... 

차근차근 설명을 해보자 

이번 문제는 간단했는데 구현이 복잡한 문제였다. 

 

일단 입력을 전체 테스트케이스로 받고 

그 후 팀의 개수, 문제의 개수, 내 팀 ID, 로그 갯수

그 후 로그 갯수의 따라 팀 ID, 문제 번호, 획득 점수로 받는다.

 

입력을 다 받고 코드로 구현을 할라 했으나 너무 비효율적인거 같아서 

입력을 받으면서 처리를 하도록 구현을 하였다. 

for (int j = 0; j < m; j++) {
    st = new StringTokenizer(br.readLine());
    teamId = Integer.parseInt(st.nextToken());
    problem = Integer.parseInt(st.nextToken());
    score = Integer.parseInt(st.nextToken());

    if (totalScore[teamId - 1][problem - 1] != 0) {
        score = Math.max(totalScore[teamId - 1][problem - 1], score);
    }
    totalScore[teamId - 1][problem - 1] = score;
    cnt[teamId - 1] += 1;
    list.add(teamId);
}
rank();

위 코드가 입력의 핵심 코드이다. 

totalScore 배열은 [팀별][팀별 당 문제] 로 선언을 하여 받았다. 

 

이때 문제의 대한 조건은 아래와 같다. 

1. 한 문제에 대한 풀이를 여러 번 제출할 수 있는데, 그 중 최고 점수가 그 문제에 대한 최종 점수가 된다. (만약 어떤 문제에 대해 풀이를 한번도 제출하지 않았으면 그 문제에 대한 최종 점수는 0점이다.) 

2. 최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다. 

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

 

1번 조건에 따라 Math.max로 선언하여 문제에 따라 최고점수만 totalScore배열에 저장하도록 하였다. 

 

2번 조건에 따라 cnt 배열에 각 팀별 당 제출횟수를 저장한다.

 

3번 조건에 따라 list를 선언하여 팀별당 제출순서를 기록한다.

 

참고로 배열에서 -1을 한 이유는 배열의 첫번째는 0이기 때문이다. 

 

그 후 이젠 순위를 측정하기 위해 rank()함수로 이동한다. 

private static void rank() {

    int[][] result_score = new int[n][2];
    for (int i = 0; i < n; i++) {
        result_score[i][0] = i + 1;
        for (int j = 0; j < k; j++) {
            result_score[i][1] += totalScore[i][j];
        }
    }

    Arrays.sort(result_score, Comparator.comparingInt((int[] a) -> a[1]).reversed()); // 이차원 배열 두번째 열 기준으로 정렬



    int rank = 0;
    for (int i = 0; i < n; i++) {
        if (result_score[i][0] == my) {
            rank = i + 1;
        }
    }

    int equal = result_score[rank - 1][1];
    int my_cnt = cnt[my - 1];
    int down_rank = 0;
    int equal_rank = 0;

    Collections.reverse(list);
    int f_rank = 0;
    int m_rank=0;
    for (int i = 0; i < n; i++) {
        if (result_score[i][1] > equal){
            m_rank++;
        }


        if (result_score[i][1] == equal && result_score[i][0] != my) {
            f_rank++;
            if (my_cnt < cnt[result_score[i][0] - 1]) {
                down_rank++;
            } else if (my_cnt == cnt[result_score[i][0] - 1]) {
                boolean flag = false; // 값 동등일떄 빨리 나온거
                for (int index : list) {
                    if (index == result_score[i][0]) {
                        flag = true;
                        break;
                    } else if (index == my) {

                        break;
                    }
                }
                if (flag) {
                    equal_rank++;
                }
            }
        }
    }
    f_rank++; //자기 자신

    f_rank = f_rank - down_rank - equal_rank+m_rank;
    System.out.println(f_rank);
}

 

rank()함수이다. 차근차근 알아보자. 

int[][] result_score = new int[n][2];
for (int i = 0; i < n; i++) {
    result_score[i][0] = i + 1;
    for (int j = 0; j < k; j++) {
        result_score[i][1] += totalScore[i][j];
    }
}

Arrays.sort(result_score, Comparator.comparingInt((int[] a) -> a[1]).reversed()); // 이차원 배열 두번째 열 기준으로 정렬

 

위 코드는 totalScore 배열에서 팀별로 구분해서 즉 팀별의 문제별로 총합을 구하는 코드이다. 

resultScore은 2차원 배열로 [아무의미 없는 순서][팀ID, 문제 총합 점수]로 선언을 하였다. 

 

그 후 순위를 측정하기 위해 문제 총합 점수를 기준으로 Arrays.sort를 하여 내림차순으로 지정하였다. 

int rank = 0;
for (int i = 0; i < n; i++) {
    if (result_score[i][0] == my) {
        rank = i + 1;
    }
}

int equal = result_score[rank - 1][1];
int my_cnt = cnt[my - 1];
int down_rank = 0;
int equal_rank = 0;

Collections.reverse(list);
int f_rank = 0;
int m_rank=0;
for (int i = 0; i < n; i++) {
    if (result_score[i][1] > equal){
        m_rank++;
    }

 

이젠 내가 속한 순위를 알아야 된다. 

이전에 my 변수에 내 팀 ID를 입력받았다. 

resultScore[i][0] 번째에는 팀별 ID 가 있으므로 my랑 일치하는 데이터는 내 팀 이므로 그 순위를 rank 변수에 할당한다. 

이때 +1 을 해주는 이유는 첫 시작이 0이기 때문이다.

 

그 후 result_score에서 rank를 통해 내 팀의 점수를 equal에 저장하고 

my_cnt 변수에 내 팀이 제출한 횟수를 저장한다. 

그 후 list를 거꾸로 배치시킨다.

 

for 문을 통해 첫번 째 if문에서는 내 점수 보다 높은 팀들이 있을때 m_rank를 증가시킨다. 

if (result_score[i][1] == equal && result_score[i][0] != my) {
    f_rank++;
    if (my_cnt < cnt[result_score[i][0] - 1]) {
        down_rank++;
    } else if (my_cnt == cnt[result_score[i][0] - 1]) {
        boolean flag = false; // 값 동등일떄 빨리 나온거
        for (int index : list) {
            if (index == result_score[i][0]) {
                flag = true;
                break;
            } else if (index == my) {

                break;
            }
        }
        if (flag) {
            equal_rank++;
        }
    }
}

 

두 번째 if문에서는 내 점수랑 동일함과 동시에 자기 자신이 아닌 팀들만 들어오게 된다.

그리고 f_rank를 더함으로써 내 팀이랑 동일한 점수의 팀의 횟수를 센다. 

 

들어오게 되면 if문을 또 마주 하게 되는데 이것은 내가 제출한 횟수보다 상대팀들이 제출한 횟수가 더 많을때 

down_rank가 증가하게 된다. 

즉 이것은 2번 조건이다.  

 

만약 그렇지 않을때 else if를 마주하게 되는데 이것은 횟수가 동일할때 즉 3번 조건이다.

flag 변수를 선언하여 이때 list는 거꾸로 배열 되었으므로 해당 팀의 index가 즉 팀의 ID가 더 빨리 나왔을때 

flag는 true로 바뀌게 된다. 그리고 true면 equal_rank 가 올라가는데 

 

즉 이 뜻은 해당 팀이 더 늦게 제출했으므로 equal_rank를 올린다는 것이다. 

 

f_rank++; //자기 자신

f_rank = f_rank - down_rank - equal_rank+m_rank;
System.out.println(f_rank);

 

그 후 최종적으로 f_rank를 통해 자신 팀을 더해준다. 

그리고 down_rank, equal_rank변수는 본인 팀보다 못한 애들이니깐 f_rank에서 뺴주고 

m_rank는 본인 팀보다 높은 팀이니깐 더해준다. 

 

최종적으로 f_rank를 출력하면 끝이다!  

전체코드

package implement;

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

public class Implement3758 {

    static int n;

    static int k; //문제 갯수

    static int my; // 내팀 id

    static int m; //엔트리

    static int[] cnt;


    static int teamId;

    static int problem;

    static int score;

    static int[][] totalScore;
    static List<Integer> list = new ArrayList<>();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            my = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            cnt = new int[n];
            totalScore = new int[n][k];
            for (int j = 0; j < m; j++) {
                st = new StringTokenizer(br.readLine());
                teamId = Integer.parseInt(st.nextToken());
                problem = Integer.parseInt(st.nextToken());
                score = Integer.parseInt(st.nextToken());

                if (totalScore[teamId - 1][problem - 1] != 0) {
                    score = Math.max(totalScore[teamId - 1][problem - 1], score);
                }
                totalScore[teamId - 1][problem - 1] = score;
                cnt[teamId - 1] += 1;
                list.add(teamId);
            }
            rank();
        }

    }

    private static void rank() {

        int[][] result_score = new int[n][2];
        for (int i = 0; i < n; i++) {
            result_score[i][0] = i + 1;
            for (int j = 0; j < k; j++) {
                result_score[i][1] += totalScore[i][j];
            }
        }

        Arrays.sort(result_score, Comparator.comparingInt((int[] a) -> a[1]).reversed()); // 이차원 배열 두번째 열 기준으로 정렬



        int rank = 0;
        for (int i = 0; i < n; i++) {
            if (result_score[i][0] == my) {
                rank = i + 1;
            }
        }

        int equal = result_score[rank - 1][1];
        int my_cnt = cnt[my - 1];
        int down_rank = 0;
        int equal_rank = 0;

        Collections.reverse(list);
        int f_rank = 0;
        int m_rank=0;
        for (int i = 0; i < n; i++) {
            if (result_score[i][1] > equal){
                m_rank++;
            }


            if (result_score[i][1] == equal && result_score[i][0] != my) {
                f_rank++;
                if (my_cnt < cnt[result_score[i][0] - 1]) {
                    down_rank++;
                } else if (my_cnt == cnt[result_score[i][0] - 1]) {
                    boolean flag = false; // 값 동등일떄 빨리 나온거
                    for (int index : list) {
                        if (index == result_score[i][0]) {
                            flag = true;
                            break;
                        } else if (index == my) {

                            break;
                        }
                    }
                    if (flag) {
                        equal_rank++;
                    }
                }
            }
        }
        f_rank++; //자기 자신

        f_rank = f_rank - down_rank - equal_rank+m_rank;
        System.out.println(f_rank);
    }
}

결과

느낀점

굉장히 복잡했던 문제였다. 무려 2시간30분...... 정처기 때문에 알고리즘 능력이 많이 떨어진거 같다.

열심히 해야된다.. 열심히!!