프로그래머스: H-index

문제 설명

• 배열에서 h보다 큰 수가 h개 이상 있다면 조건을 만족하는 h입니다.
• 조건을 만족하는 h중 가장 큰 h를 찾는 문제입니다.

접근법

• citations의 길이가 1000이하이기 때문에 $O(n^2)$으로 풀어도 시간초과가 나지 않습니다.
• 가장 큰 값을 찾아야 하기 때문에 0부터 n까지가 아니라 n부터 0까지 반복문을 실행합니다. 처음 조건을 만족하는 값이 가장 큰 정답이 됩니다.

정답

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
		Here : for (int i = citations.length; i >= 0; i--) { //H-index의 값은 최대 citations.length일 수 있습니다. 가장 큰 값을 찾기 위해 큰수부터 확인합니다.
            //H-index의 값이i일 때, H-index의 조건을 만족하는지를 검사합니다
            int h = i; 
			int cnt = 0;//H-index의 값이 i일 때, 몇개의 원소가 조건을 만족했는지를 저장합니다
			for (int c = 0; c < citations.length; c++) {//citations를 순회하면서
				if(citations[c]>=h) {//해당 원소가 H-index의 조건을 만족했다면
					cnt++;//cnt를 1 증가시킵니다
				}
			}
            //citations을 모두 순회한 후 몇 개의 cnt가 쌓였는지 확인합니다.
			if (cnt >= h) {//cnt의 개수가 h보다 많다면 H-index의 조건을 만족한다는 뜻입니다
                //우리는 H-index가 될 수 있는 가장 큰 수(citations.length)부터 1씩 감소하는 방향으로 검사를 하고 있기 때문에, 처음 등장하는 H-index가 가장 큰 H-index입니다.
				answer = h;//정답값을 저장합니다.
				break Here;//H-index를 찾는 루프 자체를 탈출합니다.
			}
		}
        return answer;
    }
}

기타

• 처음에 if (cnt >= h)이 아니라 if (cnt == h)로 확인해서 틀렸었다.
  • h이상인 수(cnt)가 h개 있어야 하는 게 아니라 h이상인 수(cnt)가 h개 보다 많이 있으면 조건을 만족하기 때문에 이렇게 수정해야 한다.