[JAVA] 프로그래머스 H-Index

문제: H-Index https://programmers.co.kr/learn/courses/30/lessons/42747

[H-Index]

• 문제 재정의:

citations 배열(input)의 length->n

citations 배열 중 h 이상 인용된 논문이 h개 이상이고, 나머지 논문이 h번 이하 인용되었다면, h return

---

• 생각한 것:

1. 일단 citations 배열 정렬

2. 배열.length의 /2를 일단 int h로 잡고 검사. h 이상 인용된 논문이 h편 이하이면 h--, 또 검사. h 이상 인용된 논문이 h편 이상이면 h++, 또 검사. 반복.

->h이상 인용된 논문의 갯수를 count로 잡음

3. 2번 단게를 반복하다가 h이상 인용된 논문이 h이면, 나머지 논문이 h번 이하 인용되었다면. 맞다면 return

근데 3번 단계는 2번단계가 완료되면 무조건 OK. 왜냐면 배열이 이미 정렬되어 있기 때문.

---

여러 테스트 케이스들

5 3 99 98 97 96

입력	출력
{2, 2, 2} /{0} /{0, 0}/{2, 0}	2/0/0/1

출처: https://stroot.tistory.com/115 [Strong Root]

http://blog.naver.com/PostView.nhn?blogId=promarketyj&logNo=221434899288&categoryNo=0&parentCategoryNo=0&viewDate=¤tPage=1&postListTopCurrentPage=1&from=postView

---

• 코드:

//BufferedReader 사용
package till;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // StringTokenizer 객체 선언
        StringTokenizer st = null;

        // String Line이므로 Integer.parseInt를 이용하여 형변환해야함
        int n = Integer.parseInt(br.readLine()); //citations 배열 length 미리 받기 (편의상)

        int[] citations = new int[n];
        st = new StringTokenizer(br.readLine()); //stringtokenizer 공백 기준으로  나누고 

        for(int i=0;i<n;i++){
            citations[i]=Integer.parseInt(st.nextToken());//int로 형변환 해주면서 citations 배열에 저장
        }

        System.out.println(solution(citations));

    }

    public static int solution(int[] array) {
        int result=0;
        Arrays.sort(array);

        int h=array.length/2;
        int count=checking_count(array,h); //h이상인 해당 논문 개수 몇개인지 확인용 변수


        while(count!=h){
            if(count>h){
                h++;
                count=checking_count(array,h);
            }
            if(count<h){
                h--;
                count=checking_count(array,h);
            }
            else{
                result=h;
            }

        }

        result=h;


        return result;
    }

    public static int checking_count(int[] array, int h){
        int count=0;

        for(int i=0;i<array.length;i++){
            if(array[i]>=h){
                count++;                  
            }
        }     
        return count;
    }

}

테스트 케이스 2개가 통과되지 않는 문제점 발생 (시간초과)

->while문 대신 for문을 사용해봄

//성공 프로그래머스 코드
class Solution {
    public int solution(int[] array) {
         int result=0;
        Arrays.sort(array);

        int h=array.length/2;
        int count=checking_count(array,h); //h이상인 해당 논문 개수 몇개인지 확인용 변수


        for(int i=0;i<array.length;i++){
            if(count>h){
                h++;
                count=checking_count(array,h);
            }
            if(count<h){
                h--;
                count=checking_count(array,h);
            }
            else{
                result=h;
            }

        }

        result=h;


        return result;
       }
    public static int checking_count(int[] array, int h){
        int count=0;

        for(int i=0;i<array.length;i++){
            if(array[i]>=h){
                count++;                  
            }
        }     
        return count;
    }
}

&

//성공 이클립스 코드
//BufferedReader 사용
package till;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // StringTokenizer 객체 선언
        StringTokenizer st = null;

        // String Line이므로 Integer.parseInt를 이용하여 형변환해야함
        int n = Integer.parseInt(br.readLine()); //citations 배열 length 미리 받기 (편의상)

        int[] citations = new int[n];
        st = new StringTokenizer(br.readLine()); //stringtokenizer 공백 기준으로  나누고 

        for(int i=0;i<n;i++){
            citations[i]=Integer.parseInt(st.nextToken());//int로 형변환 해주면서 citations 배열에 저장
        }

        System.out.println(solution(citations));

    }

    public static int solution(int[] citations) {
        int result=0;
        Arrays.sort(citations);

        int h=citations.length/2; //일단 h값을 중간값으로 해둠. 아이디어는 pivot두고 정렬하는 알고리즘에서 생각남
        int count=checking_count(citations,h); //h이상인 해당 논문 개수 몇개인지 확인용 변수

        //for문 대신 while문 쓰고 탈출조건을 생각했는데, 런타임 에러가 났음
        //(이때까지만 해도 런타임에러가 while문 때문이라고 생각함) 쨌든 while문은 여러모로 복잡하니까 for문으로 바꾸겠다고 생각함
        //for문을 어디까지 돌아야할까 생각하다 최대 비교횟수는 끽해봐야 배열 길이 인 것을 알게 됨
        for(int i=0;i<citations.length;i++){
            if(count>h){
                h++;
                count=checking_count(citations,h); 
                //배열이 222와 같은 경우 h가 1일때도 해당, 2일 때도 해당, 그러나 답은 2이다. 
                //h가 조건에 해당한다는 가정하에 최대를 구해야 하는 것을 깨달음.
                //count>h일때 h가 정답을 벗어나는 직후에 count가 0이 되는 것을 알고 이걸 탈출조건으로 잡음
                //정답 '직후'에 0이 되는 것이기에 정답은 h--가 되는 것
                if(count==0){
                    h--;
                    break;
                }
            }
            if(count<h){
                h--;
                count=checking_count(citations,h);
                //배열이 00과 같은 경우 (내 코드에 따르면)h 초기값은 1임, 근데 답은 0임
                //그 이후 count<h 조건문에 들어와서 h--가 됨. 
                //count가 배열길이이면 답임을 알게됨
                if(count==citations.length)
                    break;
            }
            else{
                result=h;
            }
        }


        result=h;


        return result;
    }

    public static int checking_count(int[] array, int h){
        int count=0;

        for(int i=0;i<array.length;i++){
            if(array[i]>=h){
                count++;                  
            }
        }     
        return count;
    }

}