자바(백준) 11652 카드

오답 노트 & 새로 알게 된 점

해당 문제를 그냥 완탐으로 풀게 된다면 (O(N^2)로) TLE가 난다.

 

그래서 정렬을 하고 나서, 앞에서부터 순서대로 탐색을 한다.

 

현재 index에 있는 값과 앞의 값을 비교하여 같으면 curCnt를 늘려주고,

다르게 되면  curCnt를 1로 해준다. 새로운 값이 나왔으므로 1로 초기화를 시켜줘야한다.

 

그리고 curCnt가 maxCnt가 보다 크면 이 때 횟수가 가장 많은 수를 바꿔줘야한다.

 

---

코드

 

package Sort;
 
import java.io.*;
import java.util.*;
 
public class BOJ11652 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N;
    static long A[];
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        Arrays.sort(A);
 
        long max = A[0];
        int curCnt = 1, maxCnt = 1;
 
        for (int i = 1; i < N; i++) {
            if(A[i] == A[i-1]) curCnt++;
            else{
                curCnt = 1;
            }
 
            if(curCnt > maxCnt){
                maxCnt = curCnt;
                max = A[i];
            }
        }
 
        System.out.println(max);
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = atoi(br.readLine());
 
        A = new long[N];
 
        for (int i = 0; i < N; i++) {
            A[i] = Long.parseLong(br.readLine());
        }
    }
}