Chapter 04. HashMap, TreeSet (해쉬, 정렬지원 Set)

1. 학급 회장 (Hash)

<hide/>
import java.util.*;
public class Main {
 	public char solution(int n, String s){
    	char answer = ' ';
      	HashMap<Character, Integer> map = new HashMap<>();
    	for(char x : s.toCharArray()){
        	map.put(x, map.getOrDefault(x, 0) + 1);	
          	// x의 value가 있으면 가져오고 없으면  0리턴
        }
      	int max = Integer.MIN_VALUE;
      	for(char key : map.keySet() ){
			// System.out.println(x + " " + map.get(x));	// 각각의 key를 출력     
       		if(map.get(key) > max){
            	max = map.get(key);
            	answer = key;		// 키를 answer에 저장
            }	
        }
    	return answer;
    }
  
  public static void main(String[] args){
    Main T = new Main();
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    String str = in.next();
    System.out.println(T.solution(n, str));
    return ;
  }
}

  Note)

  - get()은 key의 값(value)을 가져온다.

  - getOrDefault( x, 0 ) + 1 : 아주 중요!

  - map.containsKey() : key가 존재하는지 boolean형으로 반환한다.

  - map.size() : key의 개수를 반환한다.

  - map.keySet()으로 탐색한다.

 

 

2. 아나그램 (HashMap)

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
   	Main T = new Main();
    Scanner in=new Scanner(System.in);
    String a = in.next();
    String b = in.next();
    System.out.println(T.solution(a, b));
    return ;
  }
  
  public String solution(String a, String b){
  	String answer = "YES";
 	HashMap<Character, Integer> map = new HashMap<>();
    for(char x : a.toCharArray()){			// map에 문자와 개수를 각각 저장한다.
    	map.put(x, map.getOrDefault(x, 0) + 1);
    }
    for(char x : b.toCharArray()){
    	if(!map.containsKey(x) || map.get(x) == 0) return "NO";  
        // 0이면 더이상 value를 마이너스 할 수 없다.
      	// map에 b의 문자가 포함되지 않거나 value가 0이면  NO를 리턴한다.
    	map.put(x, map.get(x) - 1); 		
        // 반복문 실행할 때마다 map에서 문자를 하나씩 제거한다. 
        // put을 통해 value를 초기화시킨다.
    }
  	return answer;
  }
}

  Def) 아나그램(Anagram): 두 문자열에 대해 알파벳의 나열 순서는 다르지만 그 구성이 일치하는 경우, 두 단어를 말한다.

  Note)

  - 길이가 같은 두 단어

  - map.containsKey( )  .. key가 있는지 여부를 boolean형태로 반환

  - 같은 key에 대해 map.put() 을 여러번 하면 마지막에 넣은 value값이 key의 value로 저장된다.

 

 

3. 매출액의 종류 (Hash, Sliding Window)

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
   	Main T = new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    int[] arr = new int[n];
    
    for(int i = 0; i < n; ++i){
    	arr[i] = in.nextInt(); 
    }
    for(int x : T.solution(n, k, arr)){
    	System.out.print(x + " " );
    }
    return ;
  }
  
  public ArrayList<Integer> solution(int n, int k, int[] arr){	// k: 연속되는 길이
  	ArrayList<Integer> answer = new ArrayList<Integer>();
    HashMap<Integer, Integer> HM = new HashMap<>();		// key, value 모두 Integer
    
    for(int i = 0; i < k -1; ++i ){
    	HM.put(arr[i], HM.getOrDefault(arr[i], 0 ) + 1);		
        // HM에 (숫자 , 개수)를 넣는다.
    }
    int lt = 0;
    
    for(int rt = k -1; rt < n; ++rt){
    	HM.put(arr[rt],  HM.getOrDefault(arr[rt] , 0) + 1);		
        	// 초기 k개의 값으 map에 들어간다.
      	answer.add(HM.size());				
        	// 사이즈(키의 개수)를 answer 리스트에 추가한다.
      	HM.put(arr[lt], HM.get(arr[lt]) - 1 );		
        	// 맨 앞 arr[lt]의 값을 감소시킨다.
      	if( HM.get(arr[lt]) == 0) HM.remove(arr[lt]);	
            // 개수가 0이면 윈도우에서 없다는 뜻이므로
            //  반드시 지우고 lt증가 
      	lt++;
    }
    return answer;
  }
}

  Note)

  - two point를 이용한다.

  - arr[lt] 는 앞서 넣어둔 값이 존재하므로 get()메서드 이용한다.

 

 

4. 모든 아나그램 찾기 (Hash, Two Points, Sliding Window)

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
    Main T  = new Main();
    Scanner in = new Scanner(System.in);
    String a = in.next();
    String b = in.next();
    System.out.println(T.solution(a, b));
    return ;
  }
  
  public int solution(String a, String b){ 		// a = "bacaAacba", b = "abc"
    int answer = 0;
  	HashMap<Character, Integer> am = new HashMap<>();
    HashMap<Character, Integer> bm = new HashMap<>();
    
    for(char x : b.toCharArray()) bm.put(x, bm.getOrDefault(x, 0) + 1 );	// a-1, b-1, c-1
  	
    int L = b.length() - 1;		//	L = 2  ( 인덱스 = 3 (= b 길이) 부터 rt를 이동시키기 위해)
    for(int i = 0; i < L; ++i) am.put(a.charAt(i), am.getOrDefault(a.charAt(i), 0) + 1);
  	// b - 1, a - 1 ?????
    // am에 a의 문자별 카운트하고 저장.
    
    int lt = 0;
    for(int rt = L; rt < a.length(); ++rt){		// rt = 2 ~ 8
    	am.put(a.charAt(rt), am.getOrDefault(a.charAt(rt), 0) + 1);	//??
    	if(am.equals(bm)) answer++;
    	am.put(a.charAt(lt), am.get(a.charAt(lt)) - 1);
      	if(am.get(a.charAt(lt)) == 0) am.remove(a.charAt(lt));
      	lt++;
    }
    return answer;
  }
}

  Note)

  - 윈도우로 밀고 가면서 같은지 equals로 확인한다.

  - am.equals(bm) 은 key와 value를 모두 비교해서 같은지 확인한다.

 

 

5. K번째 큰 수 (TreeSet)

<hide/>
import java.util.*;  
public class Main {
   public static void main(String[] args){
   	Main T = new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int [] arr = new int[n];
    int k = in.nextInt();
    for(int i = 0; i < n; ++i){
    	arr[i] = in.nextInt();    
    }
    System.out.println(T.solution(arr, n, k));
    return ;
  }
  
  public int solution(int [] arr, int n, int k){
    int answer = -1;	// k번째 수가 존재하지 않으면 -1리턴 
    TreeSet<Integer> Tset = new TreeSet<>(Collections.reverseOrder());	
    //기본적으로 오름차순이나 괄호 추가하면 내림차순 정렬
  	
    for(int i = 0; i < n; ++i){
    	for(int j = i + 1; j < n ; ++j){
        	for(int l = j + 1; l < n; ++l){
            	Tset.add(arr[i] + arr[j] + arr[l]);
            }          
        }
    }
    int cnt = 0;
    for(int x : Tset){
    	cnt++;
      	if(cnt == k) return x;
    }
  	return answer;
  }
}

  Note) 

  - TreeSet : 중복제거 & 자동정렬된다.

  - Tset.first() : treeset의 가장 앞에 있는 값 출력 , Tset.last() : 가장 뒤에 있는 값 출력

  - reverseOrder를 생략하면 자동으로 오름차순 정렬이 기본값이다.