백준 31796번: 한빛미디어 (Easy)

문제

대학교를 졸업한 산지니는 2022년부터 부산대학교 프로그래밍 대회의 후원사를 맡아온 한빛미디어의 의뢰를 받았다. 바로 한빛미디어가 출판한 책들의 데이터베이스를 이용한 웹사이트의 책 진열 프로그램을 개발해달라는 의뢰였다. 산지니는 기쁜 마음으로 의뢰를 승낙했고, 프로그램을 개발하기 시작했다. 데이터베이스의 책들은 아래 규칙에 따라 웹사이트의 페이지에 진열된다.

웹사이트의 한 페이지에 책을 한 종류 이상 진열해야 한다.
가격이 두 배 이상 차이 나는 책을 한 페이지에 함께 진열할 수 없다. 예를 들어 가격이
$3\,000$원인 책은
$5\,000$원인 책과 함께 진열할 수 있지만
$6\,000$원인 책과는 함께 진열할 수 없다.
산지니는 책이 진열된 페이지가 많으면 고객이 책을 찾기 힘들 것으로 생각해 책이 진열될 페이지 수를 최소화하기로 했다. 산지니를 도와주자!

입력

첫 번째 줄에 책의 개수를 나타내는 정수
$N$이 주어진다.
$(1 \leq N \leq 10^5)$ 

두 번째 줄에
$i$번째 책의 가격을 나타내는 정수
$S_{i}$가 공백으로 구분되어 주어진다.
$(10^3 \leq S_{i} \leq 10^6)$ 

출력

모든 책을 진열하는 데 필요한 최소 페이지 수를 출력한다.

풀이

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] S = new int[N];
        for(int i = 0; i < N; i++){
            S[i] = scanner.nextInt();
        }

        Arrays.sort(S); // 책 가격을 오름차순으로 정렬

        int page = 1; // 진열할 페이지 수
        int prevBookIndex = 0; // 이전에 진열한 책의 인덱스

        // 각 책을 순회하면서 페이지에 진열 가능 여부 확인
        for(int i = 1; i < N; i++){
            if(S[i] >= 2 * S[prevBookIndex]){
                // 새로운 페이지에 진열
                page++;
                prevBookIndex = i; // 새로운 페이지의 첫 번째 책으로 설정
            }
        }

        System.out.println(page);
        scanner.close();
    }
}