[코테/알고리즘] Java - HashMap을 이용한 알고리즘 풀이

Map

Map은 키 - 값의 쌍을 저장하는 자료구조 이다. 

• 키는 맵 내에서 유일해야 한다.
• 키는 중복될 수 없지만, 값은 중복될 수 있다.
• 순서를 유지하지 않는다. 

 

 

HashMap이란?

• 데이터를 저장할 때 Key와 Value가 짝을 이루어 저장된다.
• 데이터를 저장할때는 키 값으로 해시 함수를 실행한 결과를 통해 저장 위치를 결정한다.
• 따라서 HashMap은 특정 데이터의 저장위치를 해시 함수를 통해 바로 알 수 있기 때문에 데이터의 추가, 삭제, 검색이 빠르다.

 

삽입, 삭제, 검색 작업은 해시 자료 구조를 사용하므로 일반적으로 상수시간 O(1)의 복잡도를 가진다.

 

 

• HashMap 자주 쓰이는 메서드 정리

put(K key, V value)	키와 값을 맵에 저장. 기존 키가 있으면 값 덮어쓰기	기존 값 또는 null
get(Object key)	키에 매핑된 값 반환	값 또는 null
getOrDefault(Object key, V defaultValue)	지정된 키에 연결된 값을 반환한다. 키가 없는 경우 defaultValue에 지정한 값을 대신 반환한다.	값 또는 defaultValue
remove(Object key)	키와 매핑된 엔트리 제거	제거된 값 또는 null
containsKey(Object key)	특정 키 존재 여부 확인	boolean
containsValue(Object value)	특정 값 존재 여부 확인	boolean
size()	맵에 있는 엔트리 수 반환	int
isEmpty()	맵이 비어 있는지 확인	boolean
keySet()	맵의 모든 키 반환	Set<K>
values()	맵의 모든 값 반환	Collection<V>
entrySet()	맵의 모든 키-값 쌍 반환	Set<Map.Entry<K,V>>

 

String[] str = {"a", "b", "c"};
        HashMap<String, Integer> map = new HashMap<>();
        for (String key : str){
            map.put(key, map.getOrDefault(key,0)+1);
        }

 

getOfDefault()를 사용하여 알파벳의 개수를 저장할 수 있다.

 

 

 

---

 

 

 

 

백준 10815번 - 숫자 카드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

/*
문제
백준 10815번
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다
 */
public class baekjoon_10815 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] cardNums = br.readLine().split(" ");
        HashMap<String, Integer> map = new HashMap<>();

        for (int i=0; i<N; i++){
            String str = cardNums[i];
            map.put(str, 1);
        }

        int M = Integer.parseInt(br.readLine());
        String[] Nums = br.readLine().split(" ");

        for (String str : Nums){
            System.out.print(map.getOrDefault(str,0)+" ");
        }
    }
}

 

 

 

 

프로그래머스 lv1. 완주하지 못한 선수

import java.util.*;
/*
문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.
 */
 
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> map = new HashMap();

        for (String s : participant){
            if (map.containsKey(s)){
                map.put(s, map.get(s)+1);
            }
            else{
                map.put(s,1);
            }
        }

        for (String s : completion){
            map.put(s, map.get(s)-1);
        }

        for (String str : participant){
            if (map.get(str) != 0){
                answer = str;
            }
        }

        return answer;
    }
}

처음에 getOrDefault() 함수를 사용하여 간단하게 구현하였는데,

동명이인 완주자가 있을 경우 모두 완주자로 처리되는 오류가 발생하였다. 

완주자의 경우 value 값이 0이 되도록 하여, 동명이인 방식을 처리할 수 있도록 하였다.

 

 //참가자 명단 등록
 for (String s : participant) {
            map.put(s, map.getOrDefault(s, 0) + 1);
        }

 

containsKey() 대신, getOrDefault()를 이용하여 참가자 명단 등록 과정을 간소화 할 수 있다.