문제

문제링크

접근

• 처음에는 문제가 생각보다 쉽다 생각하고 아래와 같이 정렬과 indexOf 메서드를 활용하였지만 반 이상이 시간초과가 났다... ㅠ
• O(n) 수준 이하로 복잡도를 낮추기 위해서 고민하다가, 수 범위가 1000이하로 좁다는 것을 확인하였다.
• 1000 모든 값에 대해서 누적합 dp를 이용하면 시간복잡도를 낮출 수 있을 것이라 생각하고 풀었다.
• cnts에는 해당 인덱스에 같은 사람 수를 저장한다. 0으로 초기화되므로 그냥나온 수만 저장하면 된다.
• dp는 내림차순이므로 제일 끝에서부터 내려오는데, dp에는 지금까지 누적 사람 수를 저장하는 것이다.
• 최종 출력에는 해당 수의 바로 앞 dp + 1 하면 등수를 얻을 수 있다.

// 시간초과 오답코드 !!!!
import java.util.*;
import java.io.*;


public class Main
{
    static int N;
    static int[] sums;
    static int[] currNums;
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        List<Integer> numArr = new ArrayList<>();

        N = Integer.parseInt(br.readLine());
        sums = new int[N];
        

        for (int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());
            numArr.clear();

            currNums = new int[N];
            for (int j = 0; j < N; j++) {
                currNums[j] = Integer.parseInt(st.nextToken());
                numArr.add(currNums[j]);
                sums[j] += currNums[j];
            }

            Collections.sort(numArr);
            Collections.reverse(numArr);

            for (int j = 0; j < N; j++) {
                bw.append((numArr.indexOf(currNums[j]) + 1) + " ");
            }
            bw.append("\n");
        }

        numArr.clear();
        currNums = new int[N];
        for (int j = 0; j < N; j++) {
            numArr.add(sums[j]);
        }

        Collections.sort(numArr);
        Collections.reverse(numArr);

        for (int j = 0; j < N; j++) {
            bw.append((numArr.indexOf(sums[j]) + 1) + " ");
        }

        bw.flush();   
    }
}

풀이

// 정답 코드
import java.util.*;
import java.io.*;


public class Main
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[] cnts, dp, nums, dnums = new int[N];
        for (int tc = 0; tc < 3; tc++) {
            st = new StringTokenizer(br.readLine());

            cnts = new int[1001];
            dp = new int[1001];
            nums = new int[N];
            for (int i = 0; i < N; i++) {
                nums[i] = Integer.parseInt(st.nextToken());
                dnums[i] += nums[i];
                cnts[nums[i]]++;
            }

            dp[1000] = cnts[1000];
            for (int i = 999; i >= 0; i--)
                dp[i] = dp[i+1] + cnts[i];

            for (int i = 0; i < N; i++) {
                if (nums[i] == 1000) {
                    bw.append("1 ");
                    continue;
                }

                bw.append((dp[nums[i]+1] + 1) + " ");
            }
            bw.append("\n");
        }
        cnts = new int[3001];
        dp = new int[3001];
        for (int i = 0; i < N; i++)
            cnts[dnums[i]]++;

        dp[3000] = cnts[3000];
        for (int i = 2999; i >= 0; i--)
            dp[i] = dp[i+1] + cnts[i];
        
        for (int i = 0; i < N; i++) {
            if (dnums[i] == 3000) {
                bw.append("1 ");
                continue;
            }

            bw.append((dp[dnums[i]+1] + 1) + " ");
        }


        bw.flush();
    }
}