[프로그래머스] 27 : H-Index | n^2 배열 자르기

서예진·2024년 2월 21일
0

목차 💻

▸ H-Index
▸ n^2 배열 자르기


💡 H-Index : Lv.2

▼ 문제

출처: 프로그래머스 코딩테스트 연습 > 정렬 > H-Index

▼ 내 풀이

  • 문제의 이해를 위해 예시를 더 찾아보았다.

    논문 n편 증, a번 이상 인용된 논문이 b편 이상이면 a 와 b중 작은 값이 hIndex 값입니다.
    [10, 8, 5, 4, 3] 의 인용횟수를 가진 교수가 있다면
    10번 이상 인용 횟수를 가진 논문은 1편입니다. 이때 H-Index는 1입니다.
    8번 이상 인용 횟수를 가진 논문은 2편입니다. 이때 H-Index는 2입니다.
    5번 이상 인용 횟수를 가진 논문은 3편입니다. 이때 H-Index는 3입니다.
    4번 이상 인용 횟수를 가진 논문은 4편입니다. 이때 H-Index는 4입니다.
    3번 이상 인용 횟수를 가진 논문은 5편입니다. 이때 H-Index는 3입니다.
    여기서 H-Index는 4

  • 따라서 먼저 전달받은 배열과 숫자를 통해 숫자 이상의 요소의 수를찾는 메서드를 만들었다.
  • 메서드의 결과 즉, b 와 메서드에 전달한 숫자 a를 비교하여 작은 값을 리스트에 저장했다.
  • 마지막으로 저장된 리스트이 요소 중 최대값을 반환했다.
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Solution {
    public int solution(int[] citations) {
        
        List<Integer> hindexList = new ArrayList<>();
        
        for(int c : citations){
            int count = over(citations, c);
            int min = Math.min(c, count);
            hindexList.add(min);
        }
        
        int answer = Collections.max(hindexList);
        return answer;
    }
    public int over(int[] citations, int num){
        int count = 0;
        for(int n : citations){
            if(num <= n){
                count++;
            }
        }
        return count;
    }
}

💡 n^2 배열 자르기 : Lv.2

▼ 문제

출처: 프로그래머스 코딩테스트 연습 > 월간 코드 챌린지 시즌3 > n^2 배열 자르기

▼ 내 풀이

  • 먼저 1 부터 n 까지의 수가 들어간 nums 배열을 만들었다.
  • 2차원 배열을 채울 때, i==j일 경우 nums 배열의 i(j) 번째 수를 가져와서 넣는다. 또한, i != j인 경우 (i > j) nums 배열의 i 번째 수를 가져와서 넣는다.
  • 이렇게 만들어진 2차원 배열을 리스트로 만들었다.
[오답 코드]
import java.util.List;
import java.util.ArrayList;

class Solution {
    public List<Long> solution(int n, long left, long right) {
        List<Long> answer = new ArrayList<>();
        long[][] arr = new long[n][n];
        long[] nums = new long[n];
        List<Long> list = new ArrayList<>();
        
        //1-n의 수가 들어간 배열 만들기
        for(int i = 0; i < nums.length; i++){
            nums[i] = i+1;
        }
        
        //2차원 배열 채우기
        for(int i = 0; i < arr.length; i++){
            for(int j = 0; j < arr[0].length; j++){
                if(i==j){
                    arr[i][j] = nums[i];
                }else{
                    int max = Math.max(i, j);
                    arr[i][j] = nums[max];
                }
            }
        }
        
        //2차원 배열을 리스트로 만들기
        for(int i = 0; i < arr.length; i++){
            for(int j = 0; j < arr[0].length; j++){
                list.add(arr[i][j]);
            }
        }
        
        //정답 리스트 만들기
        for(long i = left; i <=right; i++){
            answer.add(list.get((int)i));
        }
        return answer;
    }
}
  • 위의 코드를 돌려보니 메모리 초과가 났다. left와 right의 범위가 매우 클 경우는 당연히 메모리 초과가 날 수 밖에 없는 코드였다.
  • 해결하기 위해서 2차원 배열을 만들지 않고 바로 정답리스트로 만들었다.
  • 위에서 2차원 배열을 채웠던 것을 참고했다.
  • i/n을 행번호, i%n을 열번호로 활용하여 2차원 배열이였을 때의 index를 얻었다.
  • 2차원 배열에서도 해당 index의 요소는 행과 열 중의 큰 값 +1 이므로 여기에도 적용했다.
[수정 코드]
import java.util.List;
import java.util.ArrayList;

class Solution {
    public List<Long> solution(int n, long left, long right) {
        List<Long> answer = new ArrayList<>();

        for (long i = left; i <= right; i++) {
            long row = i / n; 
            long col = i % n; 
            long value = Math.max(row, col) + 1; 
            answer.add(value); 
        }

        return answer;
    }
}
  • 눈에 띄게 코드가 간결해지고 메모리 초과 문제도 해결했다.
  • 2차원 배열을 직접 만들지 않고 그 배열의 index를 통해서 필요한 부분만 계산할 수 있었다.

profile
안녕하세요

0개의 댓글