프로그래머스 코딩테스트 고득점 Kit : 해시(Java)

1. 포켓몬(Level 1)

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/1845

프로그래머스

 

문제 풀이

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;

        HashSet<Integer> set = new HashSet<>();
        for(int i=0; i<nums.length; i++) {
            set.add(nums[i]);
        }
        
        if(set.size() > nums.length/2) {
            answer = nums.length/2;
        } else {
            answer = set.size();
        }
        
        return answer;
    }
}

---

2. 완주하지 못한 선수(Level 2)

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42576

프로그래머스

 

문제 풀이

처음 제출한 코드에서 효율성 테스트 모두 시간 초과 발생..

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        // 크기가 고정되어 크기 변경 연산이 허용되지 않음
        // List<String> participantList = Arrays.asList(participant);
        // List<String> completionList = Arrays.asList(completion);
        
        // 가변 크기의 리스트로 변환해야 함!!!
        List<String> participantList = new ArrayList<>(Arrays.asList(participant));
        List<String> completionList = new ArrayList<>(Arrays.asList(completion));
        
        Collections.sort(participantList);
        Collections.sort(completionList);
        
        for(int i=0; i<participantList.size(); i++) {
            String str = participantList.get(i);
            boolean isCompleted = false;
            for(int j=0; j<completionList.size(); j++) {
                if(str.equals(completionList.get(j))) {
                    isCompleted = true;
                    completionList.remove(j); // 동명이인 고려
                    break;
                }
            }
            
            if(!isCompleted) {
                answer = str;
            }
        }
        return answer;
    }
}

-> 동명이인 계산을 위해 remove 연산을 수행하였으나 java.base/java.util.AbstractList.remove(AbstractList.java:167)이 발생하였다.

 

* 불변(immutable) 리스트에서 remove() 메서드를 호출했을 때 예외 발생

Arrays.asList()로 생성된 리스트는 배열에 기반한 리스트로 크기가 고정되어 있어 크기를 변경하는 연산(예 : remove(), add())가 허용되지 않는다.

 

-> 가변 크기의 리스트로 변환해야 함!!

// 변경 전
// List<String> participantList = Arrays.asList(participant);
// List<String> completionList = Arrays.asList(completion);
        
// 변경 후 : 가변 크기의 리스트로 변환해야 함!!!
List<String> participantList = new ArrayList<>(Arrays.asList(participant));
List<String> completionList = new ArrayList<>(Arrays.asList(completion));

 

하지만 효율성에서 실패..

 

HashMap 사용으로 개선하였다.

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        // List<String> participantList = new ArrayList<>(Arrays.asList(participant));
        // List<String> completionList = new ArrayList<>(Arrays.asList(completion));
    
        Map<String, Integer> map = new HashMap<>();
        for(String str : participant) {
            if(map.containsKey(str)) {
                map.put(str, map.get(str) + 1);
            } else {
                map.put(str, 1);
            }
        }
        
        for(String str : completion) {
        if(map.containsKey(str)) {
                map.put(str, map.get(str) - 1);
            }        
        }
        
        for(String str : map.keySet()) {
            if(map.get(str) == 1) {
                answer = str;
                break;
            }
        }
        
        return answer;
    }
}

---

3. 의상(Level 2)

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42578?language=java

프로그래머스

 

문제 풀이

조합 사용

: 마지막에 -1을 해주는 이유는 모든 의상을 한번에 입는 경우를 제외해 주는 것

 

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        
        Map<String, Integer> map = new HashMap();
        for(int i=0; i<clothes.length; i++) {
            if(map.containsKey(clothes[i][1])) {
                map.put(clothes[i][1], map.get(clothes[i][1]) + 1);
            } else {
                map.put(clothes[i][1], 1);
            }
        }
        
        
        // 조합
        for(String str : map.keySet()) {
            answer *= (map.get(str) + 1);
        }
        return answer - 1;
    }
}

---

4. 전화번호 목록(Level 2)

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

 

문제 풀이

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);
        
        // 정렬을 수행하여 앞뒤만 비교하면 됨
        for(int i=0; i<phone_book.length-1; i++) {
            if(phone_book[i+1].startsWith(phone_book[i])) {
                answer = false;
                break;
            }
        }
        
        return answer;
    }
}

---

5. 베스트앨범(Level 3)

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42579

프로그래머스

 

문제 풀이

1. 장르와 인덱스를 담는 Album 객체 생성

2. 각 장르 별 재생 횟수를 담는 findTopGenre HashMap 생성
2. findTopGenre 를 ArrayList 내림차순으로 정렬 -> topGenreList
3. Album과 장르를 담는 HashMap 생성 -> map
4. map을 재생된 횟수를 기준으로 내림차순 정렬 -> sortedMap
5. topGenreList를 순회하며 각 장르당 최대 2개씩 sortedMap에서 꺼내 answer에 담아준다.

import java.util.*;

class Solution {
		public int[] solution(String[] genres, int[] plays) {
			List<Integer> answer = new ArrayList<>();

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

			for(int i=0; i<genres.length; i++) {
				map.put(i, new Album(genres[i], plays[i]));

				if(findTopGenre.containsKey(genres[i])) {
					findTopGenre.put(genres[i], findTopGenre.get(genres[i]) + plays[i]);
				} else {
					findTopGenre.put(genres[i], plays[i]);
				}
			}

			// topGenreList 정렬 : 많이 재생된 장르 순서대로
            List<String> topGenreList = new ArrayList<>(findTopGenre.keySet());
			topGenreList.sort(new Comparator<String>() {
				@Override
				public int compare(String o1, String o2) {
					return findTopGenre.get(o2).compareTo(findTopGenre.get(o1));
				}
			});

			// map을 plays 기준으로 내림차순 정렬
			LinkedHashMap<Integer, Album> sortedMap = new LinkedHashMap<>();
			map.entrySet().stream()
					.sorted(Map.Entry.comparingByValue(Comparator.comparingInt(Album::getPlays).reversed()))
					.forEach(entry -> sortedMap.put(entry.getKey(), entry.getValue()));


			for(String genre : topGenreList) {
				int cnt = 0;
				for(Integer idx : sortedMap.keySet()) {
					Album album = sortedMap.get(idx);

					if(genre.equals(album.genres)) {
						answer.add(idx);
						cnt++;
					}
					if(cnt == 2) {
						break;
					}
				}
			}
			return answer.stream().mapToInt(Integer::intValue).toArray();
		}
        
		class Album {
			String genres;
			int plays;

			Album(String genres, int plays) {
				this.genres = genres;
				this.plays = plays;
			}

			public int getPlays() {
				return plays;
			}
		}
	}

 

* findTopGenre HashMap을 topGenreList ArrayList로 내림차순 정렬

// topGenreList : 많이 재생된 장르 순서대로 장르 내림차순 정렬
List<String> topGenreList = new ArrayList<>(findTopGenre.keySet());

// 참고) 오름차순 정렬 : 기본적으로는 o1이 더 크다면 양수를 반환하고, 순서가 바뀌게 됨
topGenreList.sort(new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        // compareTo() : 첫 번째 값과 두 번째 값 비교
        // 1. 양수 : 첫 번째 값이 더 큼
        // 2. 음수 : 두 번째 값이 더 큼
        // 3. 0 : 두 값이 같음
        return findTopGenre.get(o2).compareTo(findTopGenre.get(o1)); // 내림차순 정렬
    }
});

 

* map을 Album 객체의 plays 속성 기준으로 내림차순 정렬

// map을 plays 기준으로 내림차순 내림차순 정렬
LinkedHashMap<Integer, Album> sortedMap = new LinkedHashMap<>();

map.entrySet().stream() // map.entrySet() : Set<Map.Entry<Integer, Album>> 반환 -> stream()으로 스트림을 생성해 map의 항목들을 순차적으로 처리

// sorted() : 스트림의 요소들을 정렬하는 메서드
// comparingByValue() : Map.Entry의 값에 대해 비교기를 만들어주는 메서드
// Comparator.comparingInt(Album::getPlays).reversed() -> Album 객체의 getPlays()의 값을 기준으로 정렬할 수 있는 Comparator 생성
.sorted(Map.Entry.comparingByValue(Comparator.comparingInt(Album::getPlays).reversed()))

// 정렬된 항목들을 sortedMap에 순차적으로 키 - 값 쌍으로 입력
// entry.getKey() : Integer & entry.getValue() : Album
.forEach(entry -> sortedMap.put(entry.getKey(), entry.getValue()));

 

* 메서드 참조

Album::getPlays

-> Album 객체의 getPlays() 메서드를 직접 참조