문제: https://school.programmers.co.kr/learn/courses/30/lessons/120812
문제설명
- 주어진 파라미터: int[] array
- 주어진 값들 중 가장 자주 나오는 값을 return 해주면 된다.
- 같은 빈도록 나온 값이 여러개일경우 -1을 return 해준다.
풀이방식
- Map을 활용해서 <나온 숫자: 빈도> 조합으로 저장을 하려한다.
- 저장된 값을 기준으로 Map을 순회하며 가장 많이 나온 값을 찾는다.
코드
import java.util.*;
class Solution {
public int solution(int[] array) {
Map<Integer, Integer> map = new HashMap<>();
// 최빈값 관련 map
for(int i : array){
Integer target = map.get(i);
if(target == null ){
map.put(i, 1); // 없으면 1번 나왔다고 넣기
}else{
map.put(i, target + 1); // 있으면 1번 추가해서 넣기
}
}
// Map 조회하며 가장 많이 나온 숫자 찾기
int max = 0;
int maxKey = 0;
boolean dup = false; // 중복 체크
Iterator<Integer> keys = map.keySet().iterator();
while(keys.hasNext()){
Integer key = keys.next();
//max 업데이트
if( max < map.get(key)){
maxKey = key;
max = map.get(key);
dup = false;
}else if(max == map.get(key)){
dup = true;
}
}
return dup == true? -1: maxKey;
}
}알게된 점
Map(HashMap)
Map의 경우 Key와 Value의 조합으로 한 쌍을 저장하는 자료구조이다.
Key는 Value를 찾기위한 이름의 역할을 하게 된다.
여기서 중요한 부분은 Map은 순서대로 저장되지 않고, Key는 중복을 허용하지 않는다는 점이다!
그렇다면 Map에 대해 간단하게 알아보자
선언부
Map의 경우 보통 HashMap을 많이 쓴다. Map은 인터페이스이기때문에 자체적으로 생성이 불가능하다. HashMap은 Map 인터페이스를 구현하는 구현체로 다양한 메서드를 포함하고 있다.
따라서, Map을 구현시Map<String, Integer> myMap = new HashMap<>()를 쓰게 된다.
→ Map에는 다른 구현체(HashMap, TreeMap)들도 많은데 왜 HashMap을 쓰는걸까??
이는 HashMap이 키를 해싱하여 저장하고 검색하기 때문에 연산이 더 빠르기 때문이다!
HashMap은 성능과 메모리 효율이 좋아 일반적인 키-값 저장 용도로 적합하다
TreeMap은 키가 정렬되어있어야 하거나 범위 검색이 필요한 특수 경우에 사용된다.
주요 메서드
- put(key, value): Map에 추가
- get(key): Key에 해당하는 Value 가져오기
- containsKey(key): 해당하는 Key가 존재하는지 T/F 체크
- remove(key): 해당하는 Key 쌍을 삭제
- size(): Map의 개수를 리턴
- keySet(): 모든 키를 Set 형태로 바꾼다.
- Values(): 모든 value를 Collection 형태로 반환한다.
Map 순회
Map은 앞서 설명했다시피 순서를 저장하지 않는 자료구조이다. 하지만 종종 Map 내의 Key들을 순회해야하는 경우가 있다. 이럴때 자주 사용하는 방법을 알려주겠다
-
Iterator를 통한 접근
위의 코드에서 내가 사용한 방법이다.
keySet()을 통해 반환받은 set을 iterator() 메서드를 통해 Iterator 객체로 반환받는다면 hasNext(), next(), remove() 메서드를 사용할 수 있게 된다.Iterator<Integer> keys = map.keySet().iterator(); while(keys.hasNext()){ Integer key = keys.next(); } -
EntrySet()을 통한 접근
EntrySet 이란 Map에 있는 모든 키-값 쌍을 Set<Map.Entry<Key, Value>>로 반환한다. → 리턴타입: Set<Map.Entry<Key, Value>>
여기서 Map.Entry 객체는 하나의 키와 값의 쌍을 표현한다.
getKey(), getValue()로 키와 값을 가져올 수 있다.``` for(Set<Map<Integer, Integer> entry: map.entrySet()){ entry.getKey(); entry.getValue(); } ``` -
KeySet을 통한 접근
for(Integer key : map.keySet()){ map.get(key); }
최종적으로 효율성의 측면에서 봤을때는 EntrySet()을 이용한 순회가 가장 효과적이라고 할 수 있다. EntrySet()을 이용해 다시 코드를 짜보자!
import java.util.*;
class Solution {
public int solution(int[] array) {
Map<Integer, Integer> map = new HashMap<>();
// 최빈값 관련 map
for(int i : array){
Integer target = map.get(i);
if(target == null ){
map.put(i, 1); // 없으면 1번 나왔다고 넣기
}else{
map.put(i, target + 1); // 있으면 1번 추가해서 넣기
}
}
// Map 조회하며 가장 많이 나온 숫자 찾기
int max = 0;
int maxKey = 0;
boolean dup = false; // 중복 체크
for(Map.Entry<Integer, Integer> entry : map.entrySet()){
if(entry.getValue() > max){
max= entry.getValue();
maxKey = entry.getKey();
dup = false;
}else if(entry.getValue() == max){
dup = true;
}
}
return dup == true? -1: maxKey;
}
}오늘 포스팅이 많이 길어지긴했지만 그만큼 얻어가는게 많은 글이었다!
참 쉽쥬잉?
