Pearlii-Log

문제 풀이 날짜: 2023.05.03
포스트 작성일: 2023.05.06

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

프로그래머스 코딩테스트 고득점Kit 해시 편 : 베스트앨범 (Lv.3) (문제 링크)

키워드

해시맵, 우선순위 큐

풀이 접근법

• 주어진 조건에 부합하는 노래를 ‘두 곡’만 선정하는데, 만약 조건에 부합하는 것이 오직 한 곡만 존재한다면 한 곡만 수록해야 한다. 조건은 다음과 같다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록
   • 각 노래별로 총 재생수를 집계하고, 해당 장르의 곡 목록을 탐색한다 ⇒ 정렬 필요
2. 장르 내에서 많이 재생된 노래를 먼저 수록
   • 그 장르 내에서 가장 재생수가 높은 노래 탐색 ⇒ 정렬 필요
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록
   • 별도의 Comparator를 이용한 정렬 기준이 필요하다.

• 장르별 재생수를 집계한 다음에 수록은 어떻게 할까?
  • 우선순위 큐에 모든 장르를 넣고, 재생수가 높은 장르를 하나씩 뽑는다. (poll) ⇒ Entry 자료구조 필요
  • 해당 장르의 노래들로 Entry<장르, 재생수> 리스트를 만들어 사전순의 반대로 정렬한다.
  • 앨범 등록을 마친 장르는 자연히 우선순위 큐에서 삭제된 상태이다.
  • 큐에 더 이상 들어있는 것이 없다면 종료한다.

코드

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        int[] answer = {};

        HashMap<String, Integer> map = new HashMap<>();

        //장르별 총 재생횟수 집계
        for(int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            int play = plays[i];

            map.put(genre, map.getOrDefault(genre, 0) + play);
        }

        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
            (o1, o2) -> Integer.compare(o2.getValue(), o1.getValue())); //내림차순

        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            pq.add(entry);
        }

        ArrayList<Integer> result = new ArrayList<>();

        //pq에서 재생수가 높은 장르 순으로 뽑으며 앨범에 수록한다.
        while(!pq.isEmpty()) {
            Map.Entry<String, Integer> entry = pq.poll();
            String genre = entry.getKey();

		//poll()로 뽑은 장르의 노래들만 모은다.
            ArrayList<int[]> list = new ArrayList<>();
            for(int i = 0; i < genres.length; i++) {
                if(genre.equals(genres[i])) { 
                    int[] a = {i, plays[i]};
                    list.add(a);
                }
            }

            Collections.sort(list, (o1, o2) -> (Integer.compare(o2[1], o1[1])));

            int avaliableSize = 0;
            if(list.size() >= 2) {
                avaliableSize = 2;
            }
            else if (list.size() == 1) {
                avaliableSize = 1;
            }

            for(int i = 0; i < avaliableSize; i++) {
                int num = (list.get(i))[0];
                result.add(num);
            }
        }

        answer = new int[result.size()];
        for(int i = 0; i < result.size(); i++) {
            answer[i] = result.get(i);
        }

        return answer;
    }
}

해시 문제집에 있었지만 해시 그 자체보다는 여러 자료구조를 알아야 풀기 쉬운 문제인 것 같다. 시간을 정해놓고 풀었기 때문에 급하게 마무리했으나, 개인적으로 코드를 더 깔끔하게 짰으면 좋았을 텐데 하는 아쉬움이 있다. Stream을 사용하면 몇몇 코드를 깔끔하게 다듬을 수 있을 듯하다. 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week7/day1/BestAlbum.java

문제 풀이 날짜: 2023.05.05

포스트 작성일: 2023.05.06

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

프로그래머스 코딩테스트 고득점Kit 그리디 편 : 구명보트 (Lv.2) (문제 링크)

키워드

그리디, 투포인터

풀이 접근법

• 보트에는 한 번에 최대 2명씩만 탈 수 있다는 점에 유의하자.
• 입력의 수는 1 ≤ n ≤ 50,000 이므로, 50,000 × 50,000 = 2,500,000,000 으로 10^9 시간을 초과한다. 따라서 O(n²) 시간을 넘지 않는 방식으로 풀이해야 한다.
• 보트의 무게 제한을 넘기지 않으려면 가능한 가벼운 사람과 무거운 사람을 함께 태워 보내야 한다. ⇒ 주어진 인원의 무게를 오름차순으로 정렬해서 양 끝을 탐색한다.
• 배열을 정렬하였으므로 왼쪽 포인터와 오른쪽 포인터가 가리키는 사람을 함께 태울 수 있는지의 여부를 체크한다.
• 만약 두 사람을 함께 태울 수 없다면 맨 오른쪽의 무거운 사람을 먼저 보트 하나에 태워보내고(right += 1) 다음 사람들의 무게를 체크한다.
• 둘 다 태울 수 있다면 해당 2인을 태우고 양쪽의 인덱스를 모두 증가시킨다. (left += 1 & right += 1)
• 두 포인터가 만나는 지점까지 탐색하면 종료된다. (같은 사람을 가리키게 되면 종료)

코드

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;

        Arrays.sort(people);

        int left = 0;
        int right = people.length - 1;

        while(left <= right) {
            if(people[left] + people[right] <= limit) { 
                left += 1;
            }
            right -= 1;
            answer += 1;
        }

        return answer;
    }
}

처음에는 배열을 정렬한 뒤 맨 앞부터 두 명씩 가벼운 사람을 태우는 방식으로 풀었는데 대부분의 테스트 케이스에서 틀렸다. 반례를 찾아보니 인접한 무게의 사람들끼리 태우는 것으로는 해를 구할 수 없어, 투포인터로 바꿔 풀었다. 

Git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week7/day3/Lifeboat.java