Sohn SooKyoung

💛💚

최대 1 분 소요

[백준 1302번] 베스트셀러

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class 백준_손수경_정답_1302 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        String[] books = new String[n]; 
        //입력받음
        for (int i = 0; i < n; i++) {
            books[i] = br.readLine();
        }
        //배열 정렬을 통해서 옆에 있는 책이 같은 책인지 다른 책인지 비교
        Arrays.sort(books); 
        int maxCnt = 0;
        int maxIdx = 0;
        //팔린 책이 여러개인 경우 사전순으로 가장 앞서는 책을 찾기 위해서 인덱스를 줄여나가면서 베스트 셀러를 찾는다. 
        int i = n - 1; 
        while (i >= 0) {
            int cnt = getCnt(books, n, i);
            if (cnt >= maxCnt) {
                maxCnt = cnt;
                maxIdx = i;
            }
            //cnt만큼 같은 책이 있다는 것이므로 다음 비교를 위한 인덱스를 다른 책부터 비교할 수 있도록 인덱스를 수정해줌
            i -= cnt;
        }
 
        System.out.println(books[maxIdx]);
    }
 
    public static int getCnt(String[] books, int size, int startIdx) {
        int cnt = 1;
        for (int i = startIdx; i >= 1; i--) {
            if (!books[i].equals(books[i - 1])) {
                break;
            }
            cnt++;
        }
        return cnt;
    }
}
 
cs

풀이 방법

입력받은 책을 정렬 -> 배열상 앞에 있는 책과 같은지 비교(getCnt를 통해서), 이때 인덱스가 큰 값부터 1씩 줄여나가므로 사전순으로 가장 앞서는 베스트 셀러를 찾을 수 있다.(cnt >= maxCnt 조건을 통해서 같은 경우에도 베스트 셀러로 지정해놓았기 때문) -> 그래서 결국 남아있는 maxIdx가 베스트 셀러의 인덱스가 되도록 만들어 놓았다. 메인에서 i(인덱스값)을 정한 기준은 같은 책의 개수만큼 인덱스에서 빼서 같은 책들 앞에 있는 다른 책부터 비교를 통해 개수를 셀 수 있도록 하였다. 예를 들어서 책이 a a b b b c 라면 c라는 책은 1개 이므로 i는 5부터 시작하여 getCnt라는 함수로 들어간다. 근데 그 앞에 있는 책과 다르므로 getCnt의 리턴값은 1이 되고 i는 4부터 다시 그 앞의 책과 비교를 한다. 여기서 b에 대한 cnt의 값은 3이 되고, 그 값은 가장 큰 값이므로 maxCnt로 들어가고, maxIdx는 4가 된다. 그리고 i는 4 - 3인 1로 지정이 된다.

댓글남기기

참고