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

1. 학급 회장
2. 아나그램(HashMap)
3. 매출액의 종류(Hash, sliding window)
4. 모든 아나그램 찾기 ( Hash, sliding window : 시간복잡도 O(n))
5. K번째 큰 수

 

---

1. 학급회장

 

 

 

import java.util.*;
public class Main {
    public char solution(int n,String str){
        char answer=' ';
        HashMap<Character, Integer> map=new HashMap<>();
       for(char x:str.toCharArray()){
           map.put(x,map.getOrDefault(x,0)+1);
       }
       int max=Integer.MIN_VALUE;
       for(char key:map.keySet()){
           if(map.get(key)>max){
                max=map.get(key);
                answer=key;
           }
       }
        return answer;
    }
    public static void main(String[] args){
        Main T=new Main();
        Scanner kb =new Scanner(System.in);
        int n=kb.nextInt();
        String str=kb.next();
        System.out.print(T.solution(n, str));
    }
}

 

 

 

2. 아나그램 ( HashMap)

 

 

 

import java.util.*;
public class Main {
    public String solution(String s1, String s2){
       String answer="YES";
       HashMap<Character,Integer> map = new HashMap<>(); // 해시맵 객체 map 생성
        for(char x : s1.toCharArray()){
            map.put(x, map.getOrDefault(x, 0)+1);  // x 키가 없으면 0 return
        }
        for(char x : s2.toCharArray()){
            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){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        String n=kb.next();
        String m=kb.next();
        System.out.print(T.solution(n,m));
    }
}

 

 

 

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

 

 

import java.util.*;
public class Main {
    public ArrayList<Integer> solution(int n, int k,int[] arr){
        ArrayList<Integer> answer=new ArrayList<>();
        HashMap<Integer, Integer> map=new HashMap<>();
        for(int i=0; i<k-1; i++){
            map.put(arr[i], map.getOrDefault(arr[i],0)+1);
        }
        int lt=0;
        for(int rt=k-1; rt<n; rt++){
            map.put(arr[rt], map.getOrDefault(arr[rt],0)+1);
            answer.add(map.size());
            map.put(arr[lt],map.get(arr[lt])-1);
            if(map.get(arr[lt])==0) map.remove(arr[lt]);
            lt++;
        }
        return answer;
    }
    public static void main(String[] args){
        Main T=new Main();
        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+" ");
    }
}

 

 

 

4. 모든 아나그램 찾기 (  Hash, sliding window : 시간복잡도 O(n))

 

 

 

import java.util.*;
public class Main {
    public int solution(String a, String b){
        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); // b 미리 Key 세팅
        int L=b.length()-1; // b가 abc, 3이면 L = 2
        for(int i=0; i<L; i++) am.put(a.charAt(i), am.getOrDefault(a.charAt(i),0)+1);
        int lt=0;
        for(int rt=L; rt<a.length(); rt++){
            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;
    }
    public static void main(String[] args) {
        Main T=new Main();
        Scanner kb=new Scanner(System.in);
        String a=kb.next();
        String b=kb.next();
        System.out.print(T.solution(a,b));
    }
}

 

 

 

5. K번째 큰 수

 

 

 

import java.util.*;
public class Main {
    public int solution(int[] arr, int n, int k){
        int answer=-1;
        TreeSet<Integer> Tset=new TreeSet<>(Collections.reverseOrder()); // reverseOrder = 내림차순 / default : 오름차순
        for(int i=0; i<n; i++){ // 3장 뽑기
            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; // cnt==k 값이 없으면 -1 return
    }
    public static void main(String[] args) {
        Main T=new Main();
        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();
        }
        System.out.println(T.solution(arr, n, k));
    }
}