JAVA 해시맵 사용과 정렬 알고리즘

백준 1302번 문제를 병합 정렬로 진짜 내가 생각해도 번거롭게^^! 낑낑거리며 풀었는데 틀렸고, 역시나 오늘도 다른 분들 티스토리 찾아보다가 해시맵을 사용해야 한다는걸.. 알게 됐다....^^...................... 안드로이드할 때 해시맵 사용해봤으면서 그냥 싹 다 까먹어버리고 베스트셀러 클래스를 꾸역꾸역 만들어서 으이구

[BOJ] 백준 1302 - 베스트셀러 (자바)

 

Algorithm : 해시맵 사용과 정렬 알고리즘

---

해시맵

Map 인터페이스를 구현한 대표적인 Map 컬렉션. Map 인터페이스를 상속하고 있기에 Map의 성질을 그대로 가지고 있다. Map은 키와 값으로 구성된 Entry 객체를 저장하는 구조를 가지고 있는 자료구조이다. 여기서 키와 값은 모두 객체이다. 값은 중복 저장될 수 있지만 키는 중복 저장될 수 없다. 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대치된다.

 

해시맵 선언

HashMap<Key type, Value type> map_name = new HashMap<Key type, Value type>(capacity);
// new에서 타입 파라미터는 생략 가능하다.
// 초기에 capacity를 지정할 수 있다.

 

해시맵 값 추가

HashMap<String, Integer> bestSeller = new HashMap<String, String>();
bestSeller.put("Little Prince", 1);
bestSeller.put("Demian", 1);
bestSeller.put("Little Prince", 2);

bestSeller에 "Little Prince"라는 키 값이 중복되었기 때문에 기존의 값은 새로운 값으로 대치된다. 

 

해시맵 값 삭제

HashMap<String, Integer> bestSeller = new HashMap<String, String>();
bestSeller.put("Little Prince", 1);
bestSeller.put("Demian", 1);
bestSeller.put("El nido Ajeno", 1);
bestSeller.put("Little Prince", 2);

bestSeller.remove("El nido Ajeno"); // key 값이 "El nido Ajeno"인 요소 제거
bestSeller.clear(); // 모든 값 제거

 

해시맵 출력

HashMap<String, Integer> bestSeller = new HashMap<String, String>();
bestSeller.put("Little Prince", 1);
bestSeller.put("Demian", 1);
bestSeller.put("El nido Ajeno", 1);
bestSeller.put("Little Prince", 2);

System.out.println(bestSeller); // bestSeller에 있는 모든 Key 값과 Value 출력
System.out.println(bestSeller.get("Demian")); // key값 "Demian"의 value인 1 출력

// entrySet() 활용
for (Entry<Integer, String> entry : bestSeller.entrySet()) {
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}

// KeySet() 활용
for(String s : bestSeller.keySet()){ // 저장된 key값 확인
    System.out.println("[Key]:" + s + " [Value]:" + bestSeller.get(s));
}

keySet()은 key값을 이용해서 value를 찾는 과정에서 시간이 많이 소모되기 때문에 많은 양의 데이터를 가져와야 한다면 keySet()보다 entrySet()이 좋다.

 

해시맵 특정 Key의 Value 수정

HashMap<String, Integer> bestSeller = new HashMap<String, String>();
bestSeller.put("Little Prince", 1);
bestSeller.put("Demian", 1);
bestSeller.put("El nido Ajeno", 1);
bestSeller.put("Little Prince", 2);

System.out.println(bestSeller); // bestSeller에 있는 모든 Key 값과 Value 출력
System.out.println(bestSeller.get("Demian")); // key값 "Demian"의 value인 1 출력

// KeySet() 활용
for(String s : bestSeller.keySet()){ // 저장된 key값 확인
    if(bestSeller.containsKey(s)) {
        bestSeller.replace(s, bestSeller.get(s)+1);
        // s라는 key의 value에 1 추가된 값으로 value를 변경
    }
}

 

해시맵 사용 시 주의사항

HashMap을 생성하려면 키 타입과 값 타입을 파라미터로 주고 기본생성자를 호출하면 됩니다. HashMap은 저장공간보다 값이 추가로 들어오면 List처럼 저장공간을 추가로 늘리는데 List처럼 저장공간을 한 칸씩 늘리지 않고 약 두배로 늘립니다. 여기서 과부하가 많이 발생한다. 그렇기에 초기에 저장할 데이터 개수를 알고 있다면 Map의 초기 용량을 지정해주는 것이 좋다.

 

해시맵 사용과 정렬 알고리즘 코드

출처 : 1302번: 베스트셀러 (acmicpc.net)

1302번: 베스트셀러

 

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

class MergeSort {
    
    static String[] buf;
    
    static boolean compareString(String a, String b) {
    	
    	if(a.compareTo(b) >= 0) {
    		return true; // a가 b보다 순서가 앞설 때
    	} else {
    		return false; // b가 a보다 순서가 앞설 때
    	}
    	
    }
    
    static void __mergerSort(String[] a, int left, int right) {
        
        if(left < right) {
            
            int i;
            int center = (left + right) / 2;
            int p = 0;
            int j = 0;
            int k = left;
            
            __mergerSort(a, left, center);
            __mergerSort(a, center+1, right);
            
            for(i = left; i <= center; i++)
                buf[p++] = a[i]; 
            
            while(i <= right && j < p)
                a[k++] = (compareString(a[i], buf[j])) ? buf[j++] : a[i++]; 
            
            while (j < p)
                a[k++] = buf[j++];
                
        }
        
    }
    
    static void mergeSort(String[] a, int n) {
        
        buf = new String[n];
        
        __mergerSort(a, 0, n-1);
        
        buf = null;
        
    }
    
}

public class Main {
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        HashMap<String,Integer> bestseller = new HashMap<String,Integer>();
        
        String book_name = new String();
        
        for(int i = 0; i < n; i++) {
            
            book_name = br.readLine();
            
            if (bestseller.containsKey(book_name)) {
                
                bestseller.replace(book_name, bestseller.get(book_name) + 1);
                
            }
            else {
                
                bestseller.put(book_name, 1);
                
            }
            
        }
        
        int best = 0;
        
        for(String book : bestseller.keySet()) {
            
            best = Math.max(best, bestseller.get(book));
            
        }
        
        ArrayList<String> list = new ArrayList<String>(bestseller.keySet());
        String[] book_list = new String[list.size()];
        
        for(int i = 0; i < list.size(); i++)
            book_list[i] = list.get(i);
        
        MergeSort Sort = new MergeSort();
        Sort.mergeSort(book_list, book_list.length);
        
        for(String book : book_list) {
            if(bestseller.get(book) == best) {
                
                System.out.println(book);
                break;
    
            }
        }
        
    }
    
}

 

---

 

해시맵 참고 사이트

• [Java] 자바 HashMap 사용법 & 예제 총정리 (tistory.com)

 

 

---

 

이번 문제는 Scanner로 입력을 받고 StringBuilder를 사용해서 풀면 출력 초과가 뜨고, BufferedReader으로 입력을 받고 System.out.println을 통해 출력을 하면 통과할 수 있었다.