HashMap, TreeSet - (1)

📍 섹션4.HashMap, TreeSet (해쉬, 정렬 지원 Set)

HashMap, TreeSet - (1)

---

HashMap (해쉬 맵) 이란?

• HashMap은 Key-Value가 1:1로 Mapping 되는 자료구조
• Mapping으로 인해 삽입, 삭제, 검색이 평균적으로 O(1)인 자료구조
• Key는 중복을 허용하지 않지만, Value는 중복을 허용한다.

[관련 주요 메소드]
    //특정 key 존재 여부 확인
    map.containsKey('A');

    //중복 key 없게 각 키에 해당하는 값(없으면 기본값) 가져오기
    map.getOrDefault('A', 0);

    //해쉬맵 크기 가져오기
    map.size();

    //해쉬맵 key값 기준으로 전체 탐색
    map.keySet();

    //특정 키 삭제
    map.remove('A');

---

4-1. 학급 회장

/* 04-01. 학급 회장 (해쉬) 
[입력]
첫 줄에는 반 학생수 N(5<=N<=50)이 주어집니다.
두 번째 줄에 N개의 투표용지에 쓰여져 있던 각 후보의 기호가 선생님이 발표한 순서대로 문자열로 입력됩니다.
[출력]
학급 회장으로 선택된 기호를 출력합니다.
*/
public class Main2 {
    //솔루션 함수
    public char solution (int n, String s) {
        char answer = 0;
        //<문자 , 누적값> 형태로 넣을 거임
        HashMap<Character, Integer> map = new HashMap<>();
        for(char x : s.toCharArray()) {
            //map에 중복 키 없도록 getOrDefault 로 값 얻어오되 없으면 0을 얻어옴
            map.put(x, map.getOrDefault(x, 0)+1); // +1처리해서 카운팅
        }

        int max = Integer.MIN_VALUE;

        //해쉬맵을 key값 기준으로 전체 탐색
        for(char key : map.keySet()) {
            if(map.get(key)>max) {
                max = map.get(key);
                answer = key;
            }
        }
        return answer;
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main2 T = new Main2();

        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        String str = kb.next();
        System.out.println(T.solution(n, str));
    }
}

---

4-2. 아나그램(HashMap)

/* 04-02. 아나그램 (해쉬)
Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램
[입력] 길이 같은 두 문자열 입력 [출력] 아나그램 판별 후 YES or No  
*/
public class Main3 {
    //솔루션 함수 
    public String solution(String s1, String s2) {
        String answer = "YES";

        HashMap<Character, Integer> map = new HashMap<>();
        //s1 기준으로 value에 누적시키고 
        for(char x : s1.toCharArray()) {
            map.put(x, map.getOrDefault(x, 0)+1    ); //누적
        }
        //-> s2 는 감소시키면서 아나그램 판별
        for(char x : s2.toCharArray()) {
            //s2의 각 문자에 해당하는 값이 존재하는지 여부
            if(!map.containsKey(x)|| map.get(x) == 0) return "NO";
            map.put(x, map.get(x) - 1); //감소
        }
        return answer;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        Scanner kb = new Scanner(System.in);

        String a = kb.next();
        String b = kb.next();

        System.out.println(T.solution(a, b));
    }
}

---

4-3. 매출액의 종류(Hash, sliding window)

• lt-rt사이 간격 (k일)간의 매출액을 종류별로 map에 카운팅해서 그 size() 를 출력하면 됨

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

/* 04-03. 매출액의 종류 Re
[입력]
첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.
[출력]
첫 줄에 각 구간의 매출액 종류를 순서대로 출력합니다.*/
public class Main1 {
    //솔루션 함수 
    public ArrayList<Integer> solution(int n, int k, int[]arr){
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<Integer, Integer> map= new HashMap<>();
        //초기값. 0부터 k-1까지 간격일수 동안의 매출액 종류 put처리
        for(int i =0; i<k-1; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0)+1);
        }

        //Two Pointers 알고리즘
        int lt = 0;
        for(int rt = k-1; rt<n; rt++) {
            //rt가 찍은 애를 담기 
            map.put(arr[rt], map.getOrDefault(arr[rt], 0)+1);
            //종류별로 카운팅 했으니까 answer에도 담기
            answer.add(map.size());

            //rt한칸 증가하면 기존에 lt찍었던 애는 가져와서 -1 감소해줘야 함 
            map.put(arr[lt], map.get(arr[lt])-1);
            //lt 감소했더니 0이 됐으면 그 종류는 카운팅 하면 안되니까 remove처리
            if(map.get(arr[lt]) == 0) map.remove(arr[lt]); 
            lt++;//lt도 한칸 증가
        }
        return answer;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i<n; i++) {
            arr[i] = kb.nextInt();
        }
        //출력 
        for(int x : T.solution(n, k, arr)) {
            System.out.print(x + " ");
        }
    }
}