-
99클럽 코테 스터디 5일차 TIL + 베스트앨범(프로그래머스)Study(진행중)/항해99 2024. 7. 27. 00:53
오늘의 학습 키워드
- 알고리즘
- 구현
- 해시
- 우선순위 큐
공부한 내용 본인의 언어로 정리하기
스터디에 나온 삼성 기출 문제를 풀어보려 했는데 고민하다가 접근을 못해서 내일로 미뤘다.
내일은 꼭 풀어봐야겠다.
https://school.programmers.co.kr/learn/courses/30/lessons/42579
해시와 우선순위 큐를 다루는 구현 알고리즘 문제를 풀었다.
생각보다 구현하는게 까다로웠던 것 같다.
풀이 과정은 다음과 같다.
1. 장르와 노래 정보를 저장하는 클래스 생성
2. 장르가 처음 나왔다면 해당 장르에 별명(숫자)를 붙여주고 이를 Map<장르 이름, 장르 정보>으로 관리,
2 - 1. 해당 장르의 곡이 몇 번 나왔는지 계산하여 Map에 넣어줌
3. 노래 장르별로 따로 관리 되는 우선순위 큐 배열을 만들고, 특정 배열에 있는 장르는 2번에서 만든 장르 별명에 대응됨
4. 장르에 대해 정렬을 하고, 장르별 2곡씩 노래 우선순위 큐에서 가져옴
풀이는 다음과 같다.
import java.util.*; class Solution { class Song { int playTime, idx; Song(int _playTime, int _idx) { playTime = _playTime; idx = _idx; } } class Genre { int playTime, idx, count = 1; Genre(int _idx, int _playTime) { idx = _idx; playTime = _playTime; } } public int[] solution(String[] genres, int[] plays) { HashMap<String, Genre> genreMap = new HashMap<>(); PriorityQueue<Genre> genreQue = new PriorityQueue<>((o1, o2) -> o2.playTime - o1.playTime); int size = genres.length; PriorityQueue<Song>[] songQue = new PriorityQueue[size]; for (int i = 0; i < size; i++) { songQue[i] = new PriorityQueue<>((o1, o2) -> { if (o1.playTime != o2.playTime) return o2.playTime - o1.playTime; else return o1.idx - o2.idx; }); } int idx = 0; for (int i = 0; i < size; i++) { String genre = genres[i]; int play = plays[i]; int genreIdx = idx; if (genreMap.containsKey(genre)) { Genre curGenre = genreMap.get(genre); curGenre.playTime += play; curGenre.count++; genreIdx = curGenre.idx; } else { genreMap.put(genre, new Genre(idx++, play)); } songQue[genreIdx].add(new Song(play, i)); } genreQue.addAll(genreMap.values()); int genreCnt = 0; for (Genre genre : genreMap.values()) { if (genre.count == 1) genreCnt++; else genreCnt += 2; } int[] answer = new int[genreCnt]; int i = 0; while (i != genreCnt) { Genre curGenre = genreQue.poll(); int genreIdx = curGenre.idx; answer[i++] = songQue[genreIdx].poll().idx; if (!songQue[genreIdx].isEmpty()) answer[i++] = songQue[genreIdx].poll().idx; } return answer; } }
내일 학습할 것은 무엇인지
내일은 풀이를 보고서라도 정말 삼성 기출 알고리즘 문제를 풀어 볼 예정이다.
반응형'Study(진행중) > 항해99' 카테고리의 다른 글
99클럽 코테 스터디 7일차 TIL + 과제 진행하기(프로그래머스) (0) 2024.07.29 99클럽 코테 스터디 6일차 TIL + 테이블 해시 함수(프로그래머스) (0) 2024.07.27 99클럽 코테 스터디 4일차 TIL + 문자열 압축(프로그래머스) (0) 2024.07.26 99클럽 코테 스터디 3일차 TIL + 숫자 문자열과 영단어(프로그래머스) (0) 2024.07.24 99클럽 코테 스터디 2일차 TIL + 면접 특강 후기 (0) 2024.07.24