[BOJ] 11652번: 카드 (JAVA)

1. 문제

11652번: 카드

• N (1 ≤ N ≤ 100,000)
• 카드 숫자 : -2^62보다 크거나 같고, 2^62보다 작거나 같다. => long 타입을 써야 한다.
  • int 타입 사용 시 런타임 에러 발생
• 정렬을 이용해서 답을 구할 수 있다.

2. 시간복잡도

• 배열 정렬 O(NlogN)
• 순서대로 읽기 O(N)

시간복잡도 : O(NlogN) = 100,000 * log100,000 < 100,000,000(1억, 1초)

 

3. 구현

(1) Sort를 이용한 첫 시도 => 100% 실패

• N (1 ≤ N ≤ 100,000)
  • N-1일 때의 경우를 생각하지 못하였다.
    • N이 1일때 for문을 돌지 않는다.
  • maxValue = card[0]; 코드를 추가함으로써 N=1일 때의 경우를 계산한다.

(2) Sort 이용

public class S4_11652 {
    static int N;
    static long[] card;
    static int maxCount;
    static long maxValue;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        card = new long[N];
        for (int i = 0; i <N; i++) {
            card[i] = Long.parseLong(br.readLine());
        }
        
        Arrays.sort(card); //정렬

        int currentCount = 1;
        maxValue = card[0];
        for (int i = 1; i <N; i++) {
            if(card[i-1] != card[i]) {
                currentCount = 1;
            } else {
                currentCount++;
            }
            if(maxCount < currentCount) {
                maxValue = card[i-1];
                maxCount = currentCount;
            }
        }
        System.out.println(maxValue);
    }
}