정렬 - 백준11652 카드

정렬문제는 정렬을 직접 구현할 일은 없다고 한다.
라이브러리에 정렬해주는 함수가 있기 때문이다.

풀이 시도

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 1 <= n <= 100,000
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        //정렬
        Arrays.sort(arr);
        //str[가장많은 숫자][가장많은 숫자의 갯수]
        int[][] str = new int[n][n];
        int j = 0;
        str[j][0] = arr[0];
        str[j][1] = 1;
        //정렬된 arr을 순차 탐색
        for(int i = 1; i < n; i++){
            if(arr[i] == arr[i-1]){
                //이전과 같은 숫자면 해당 숫자의 갯수++
                str[j][1]++;
            }else{
                //이전과 다른 숫자면 다음 칸에 해당 숫자 저장
                j++;
                str[j][0] = arr[i];
                str[j][1]++;
            }
        }
        int maxValue = str[0][0];
        int maxAmount = str[0][1];
        for(int i = 1; i < n; i++){
            //str[j][1]을 탐색하며 젤 큰놈의 str[j][0]출력
            if(str[i][1] > maxAmount){
                maxValue = str[i][0];
                maxAmount = str[i][1];
            }
        }
        System.out.println(maxValue);
    }
}

디버깅 결과 답은 맞게 나오지만, 제출시 메모리 초과가 뜬다..
대체 어떻게 해결해야 할까..

해답
아래 코드를 보면 어렵지 않게 이해할 수 있다.
값의 갯수를 저장하는 counts 배열을 주목해서 보자.

import java.io.*;
import java.util.*;
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());
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }
        Arrays.sort(arr);
        int[] counts = new int[n];
        counts[0] = 1;
        int maxCount = 1;
        long maxNum = arr[0];
        for (int i = 1; i < n; i++) {
            counts[i] = 1;
            if (arr[i] == arr[i-1]) counts[i] = counts[i-1] + 1;
            if (counts[i] > maxCount) {
                maxCount = counts[i];
                maxNum = arr[i];
            }
        }
        System.out.println(maxNum);
    }
}

https://propercoding.tistory.com/298
위 사이트를 참고했는데, 알고 보면 쉬워보여도 어떻게 이런 방법을 떠올릴 수 있는지 나는 잘 모르겠다

퀵소트 머지소트는 짜면서 실버4 정렬문제는 못 풀겠다..
일단 넘어가고 나중에 다시 풀어봐야겠다.