프로그래머스LV2_10

의상

접근 과정

1. 해당 의상의 종류의 개수와 다른 의상 종류의 개수를 맵을 이용하여 구한다.
2. 맵의 value + 1 을 answer에 곱한다. 해당 종류의 옷을 안 입을 수 있으므로 +1을 함
3. 나온 answer 값에서 아예 안 입는 경우는 없으므로 answer - 1을 반환하여 해결

시행착오

• 시행착오 없이 접근 과정대로 구현하여 해결

해결 코드

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        Map<String, Integer> m = new HashMap<>();
        for(String[] c : clothes){
            String type = c[1];
            m.put(type, m.getOrDefault(type, 0) + 1);
        }
        for(String type : m.keySet()){
            answer *= m.get(type) + 1;
        }
        return answer - 1;
    }
}

시간 및 공간 복잡도

• 시간 복잡도(의상 배열을 N)

• 공간 복잡도(의상 종류를 K)

개선

• 마지막 for문을 맵의 keySet이 아니라 맵의 values를 돌면 코드가 좀 더 간편해진다. values를 알아두자

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        Map<String, Integer> m = new HashMap<>();
        for(String[] c : clothes){
            String type = c[1];
            m.put(type, m.getOrDefault(type, 0) + 1);
        }
        for(Integer v : m.values()){
            answer *= v + 1;
        }
        return answer - 1;
    }
}

H-Index

접근 과정

1. h 값에 따라 인용 횟수가 큰 지 체크하여 개수를 센다.
2. 개수가 h 보다 크거나 같으면 answer를 해당 h로 갱신한다.
3. 개수가 h보다 작으면 더 큰 h는 당연히 안되므로 반복을 멈춘다.

시행착오

• 시행착오 없이 접근 과정대로 구현하여 해결

해결 코드

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        for(int i = 0; i <= 10000; i++){
            int cnt = 0;
            for(int j = 0; j < citations.length; j++){
                if(citations[j] >= i) cnt++;
            }
            if(cnt >= i) answer = i;
            else break;
        }
        return answer;
    }
}

시간 및 공간 복잡도

• 시간 복잡도(인용 횟수를 N, 논문의 개수를 M)

• 공간 복잡도

개선

• 2중 for문이 마음에 걸리고 인용 횟수와 논문의 개수가 늘어나면 시간 초과가 날 것이라 1중 for문으로 가능한지 다른 사람 풀이와 AI를 참고하여 개선하였다.
• 논문을 정렬하고 논문을 돌면서 해당 인덱스의 h를 구해 h값이 i의 인용 횟수보다 크거나 같으면 반환하여 해결할 수 있다.
• h의 최댓값이 필요하므로 h가 큰 것부터 체크한다.
• 시간 복잡도 : O(NlogN)

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations);
        int l = citations.length;
        for(int i = 0; i < l; i++){
            int h = l - i;
            if (citations[i] >= h) {
                return h;
            }
        }
        return answer;
    }
}