알고리즘)[JAVA] 프로그래머스_해시_베스트앨범(Level 3)

문제 설명

 

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

 

제한사항

 

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

 

 

처음부터 문제 이해를 잘 했더라면 훨씬 빨리 풀었을텐데... 거의 하루종일 붙잡고 있었다.

잘못이해한 포인트는

- 속한 노래가 많이 재생된 장르를 먼저 수록합니다.

//여기서 위 문장은 각장르의 재생수 총합을 의미하는데, 나는 그냥 각각의 재생수 중에서 가장 큰수가 속한 장르순서로 이해를 했음

 

- 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

//이부분을 아예 고려하지 않고 코드를 짯음, 문제를 꼼꼼히 읽어야겠음,,

 

 

static HashMap<String, Integer> baseHm = new HashMap<String, Integer>();// 해시맵선언
	static HashMap<String, Integer> firstHm = new HashMap<String, Integer>();// 그 카테고리의 가장 큰수
	static HashMap<String, Integer> secondHm = new HashMap<String, Integer>();// 그카테고리의 두번쨰로 큰수
	static HashMap<Integer, Integer> indexHm = new HashMap<Integer, Integer>();// 인덱스 저장 위치
	static HashMap<Integer, Integer> subIndexHm = new HashMap<Integer, Integer>();// 인덱스 저장 위치

	public static int[] solution(String[] genres, int[] plays) {

		String[] genresList = new String[genres.length]; // 최대갯수인 장르의 길이만큼 배열생성
		int k = 0;// 장르리스트의 인덱스역할이자 장르의 종류 갯수

		// 각 재생횟수가 몇번째 인덱스에 있는지
		for (int i = 0; i < plays.length; i++) {// 인덱스 저장위치 해시맵에 저장
			if (indexHm.getOrDefault(plays[i], -1) == -1) {// 처음임
				indexHm.put(plays[i], i);//그냥 그자리에 넣음
			} else {// 해당하는 재생수 값이 들어온게 처음이 아니면
				indexSet(indexHm.get(plays[i]), i);//값을 넣을자리를 찾을때까지 재귀함수를 실행
			}
		}

		for (int i = 0; i < genres.length; i++) {
			// baseHm에의해 각 카테고리의 총재생수를 구할 수 있음
			if (baseHm.getOrDefault(genres[i], -1) == -1) {// 처음들어가는 값일때
				baseHm.put(genres[i], plays[i]);
				genresList[k] = genres[i];// 장르가 중복없이 배열에 들어감
				k++;
			} else {// 처음들어온 값이 아닐때
				baseHm.put(genres[i], baseHm.get(genres[i]) + plays[i]);// 총재생 수 더해서 덮어쓰기
			}
			// 아래 조건문을 통해 각 카테고리의 첫번째로 큰 수와 두번째로 큰 수를 얻어올 수 있음
			if (firstHm.getOrDefault(genres[i], -1) == -1) {// 퍼스트해시맵 처음
				firstHm.put(genres[i], plays[i]);
			} else {// 처음 아닐때
				if (firstHm.get(genres[i]) > plays[i]) {// 새로들어온값보다 기존에 있던 값이 클때
					if (secondHm.getOrDefault(genres[i], -1) == -1) {// 세컨드해시맵 처음
						secondHm.put(genres[i], plays[i]);
					} else {// 세컨드 해시맵도 처음 아닐때
						if (secondHm.get(genres[i]) >= plays[i]) {// 새로 들어온값보다 기존에 있던값이 클때

						} else {// 새로들어온값이 더 클때
							secondHm.put(genres[i], plays[i]);
						}
					}
				} else if (firstHm.get(genres[i]) == plays[i]) {// 기존값과 같을때
					secondHm.put(genres[i], plays[i]);// 세컨드에 넣어버림
				} else {// 기존에 있던 값보다 새로들어온값이 클때
					secondHm.put(genres[i], firstHm.get(genres[i]));// 첫번째에 있던 값을 두번째로 옮기고
					firstHm.put(genres[i], plays[i]);// 새로들어온 값을 첫번째로 넣어줌
				}
			}
		}

		// baseHm에 있는 키들을 value의 값 순서대로 나열함
		ArrayList keySetList = new ArrayList<>(baseHm.keySet());
		Collections.sort(keySetList, (o1, o2) -> (baseHm.get(o2).compareTo(baseHm.get(o1))));

		int[] answer = new int[k * 2];//임시로 쓸 배열임 정답에 사용할 배열은 따로 만들거
		for (int i = 0; i < k * 2; i++) {//일단 값의 비교를위해 배열 전부에 더미값인 -1을 넣어줌
			answer[i] = -1;
		}

		for (String key : keySetList) {//위에서 정렬한 ArrayList를 순차적으로 반복함
			for (int i = 0; i < k * 2; i++) {
				if (answer[i] == -1) {// 빈인덱스라는의미
					answer[i] = indexHm.get(firstHm.get(key));
					for (int j = 0; j < i; j++) {
						if (answer[j] == indexHm.get(firstHm.get(key))) {
							answer[i] = subIndexHm.get(indexHm.get(firstHm.get(key)));
							break;
						}
					}
					if (indexHm.getOrDefault(secondHm.get(key), -1) != -1) {// 키에대한 두번째 큰수가 있다면
						i++;
						answer[i] = indexHm.get(secondHm.get(key));// 다음인덱스에 두번째로 큰값에대한 인덱스를 넣어줌
						for (int j = 0; j < i; j++) {
							if (answer[j] == indexHm.get(secondHm.get(key))) {
								answer[i] = subIndexHm.get(indexHm.get(secondHm.get(key)));
								break;
							}
						}
						break;
					} else {
						break;
					}
				}
			}

		}
		int realLength = 0;//실제 정답의 배열이 될 크기
		for (int i = 0; i < k * 2; i++) {//임시배열answer에서 더미로 넣어놓은 -1들을 제외한 길이를 구함
			if (answer[i] == -1) {
				break;
			} else {
				realLength++;
			}
		}

		int[] realanswer = new int[realLength];//실제 정답길이만큼의 배열생성
		for (int i = 0; i < realanswer.length; i++) {
			realanswer[i] = answer[i];//답을 넣어줌
		}

		return realanswer;
	}

	public static void indexSet(int key, int value) {//재귀함수
		if (subIndexHm.getOrDefault(key, -1) == -1) {//키로들어온걸로 get했을때 -1이 리턴되면 비어있다는의미
			subIndexHm.put(key, value);//비어잇으면 put함
		} else {//비어있지않음
			indexSet(subIndexHm.get(key), value);//키로 들어온부분이 빈값이 아니라면 빈값이 아닌걸 키값으로 다시 indexSet 호출함, value는 같음
		}
	}

 

 

1. 해시맵들을 static으로 선언한다.

//사실 indexHm과 subIndexHm만 static으로 선언해도 되는데 그냥 보기좋으라고 다뺏다.

//genresList는 장르들을 중복없이 종류로만 넣는 배열이다. k는 그에대한 인덱스이자 장르의 총갯수를 의미한다.

//baseHm은  각 장르의 총 재생수를 저장하는 역할과, genresList와 k값을 순조롭게 넣는걸 도와주는 해시맵이다. 

//firstHm는 각 장르별로 가장 큰 재생수를 저장하는 해시맵이다.

//secondHm는 각장릅려로 두번째로 큰 재생수를 저장하는 해시맵이다.

//indexHm는 각 재생수에 대한 plays에서의 인덱스를 저장하는 해시맵이다.

//subIndexHm는 같은장르내에서 plays에 중복된 재생수가 있을수 있기때문에 중복처리를 위해 생성된 해시맵이다.

 

2. 첫 for문에서 플레이 배열 길이만큼 반복한다.

//플레이의 각 인덱스를 indexHm에 저장하는데 만약 중복된 재생수가 있다면 indexSet()함수를 통해 subIndexHm에 저장한다.

 

3. 두번째 포문에서는 두가지 역할을 수행한다. baseHm에 각 장르의 총 재생수를 저장하고, 조건문을 통해 각 장르별로 첫번째로 큰 수와 두번째로 큰 수를  각각 firstHm와 secondHm에 저장한다.

 

4. ArrayList와 Collections.sort() 함수를 통해 baseHm에들어있는값을value 크기 기준으로 정렬한다.

 

5. 임시배열인 answer을 생성하고 더미값 -1을 넣어놓는다.

//이때 정답 배열의 길이를 아직 모르기때문에 정답이될수있는 최대 길이값인 장르*2(k*2)를 길이로 넣어놓는다.

 

6. 위에서 정렬한 ArrayList인 keySetList의 길이만큼 반복문을 수행한다.

//사실 2중포문으로 할수있을거같은데 고치기 귀찮다.

//내부에 포문을 중첩시켜 answer배열에 indexHm, 혹은 subIndexHm에서 값을 얻어와서 저장한다.

 

7. answer배열중에 -1부분은 위에서 넣어놓은 더미값을이니 그것을 제외한 길이를 구하기위해 realLength를 선언한다.

 

8. realLength값을 구하면 그길이만큼의 realanswer배열을 만들고 answer배열에서 값을 옮긴다.

 

P.S

indexSet(int key, int value) 함수는 내가 넣으려는 재생수 값이 이미 indexHm에 들어가있을때 중복을 방지해서 subIndexHm에 넣는데에 사용되는데,

indexHm에  key = 2500, value = 2로 값을 넣으려는데 이미  key = 2500, value = 1로 값이 들어가잇다면

subIndexHm에 key = 1, value = 2 이런식으로 값을 넣어서  2500 -> 1-> 2 이렇게 값을 찾아가는 방식이다.

 

 

 

다풀고나서 다른사람들 답을 보니 훨씬 간결하게 한사람들이 많았다.

좀 더 여러가지 문제들을 풀다보면 실력이 늘겠지 ㅜ