algorithm-HashMap_TreeSet

💥 HashMap_TreeSet

---

유형

1.학급회장(해쉬)

//문제
가장 많이 입력된 것을 학급회장으로 임명
//입력
15
BACBACCACCBDED
//출력
C

public class ex1 {
    public static 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);
        }
        int max=0;
        for(char x : map.keySet()){
            if(map.get(x) > max){
                max=map.get(x);
                answer = x;
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        System.out.println(solution(n,s));
    }
}

풀이
1.HashMap으로 Map을 만든다.
2.toCharArray를 이용해 문자열을 배열로 만들어서 forEach문으로 탐색한다.
3.map.put('key',value)을 이용해서 집어넣는다. 근데 여기서 value값은 숫자(갯수)를 뜻하는데 map.getOrDefault(x,0)를 이용해서 x값이 있으면 value값을 불러오고 없으면 0을 반환하겠다는 뜻이다. 여기에 +1을 해준다.
4.그리고 map.keySet()을 이용해서 map에 forEach를 돌릴 수 있다. 그렇게 해서 최댓값알고리즘을 적용해 값을 리턴한다. map.get(x)를 이용해서 value를 불러올 수 있다.

[ 주요 기능 ]
HashMap<Character, Integer> map = new HashMap<>(); : HashMap으로 map 생성
toCharArray() : 문자열을 Char형 배열로만든다.
map.put(ket,value) : map에 key값을 이용해 value를 집어넣는다.
map.getOrDefault(x,0) : map의 key값을 불러와서 있으면 x, 없으면 0을 넣겠다.
map.keySet() : map의 키 값에 접근 할 수 있다.
map.get(x) : map의 'x'라는 key를 찾아서 value를 리턴한다.

2.아나그램(해쉬)

//문제
입력되는 문자열의 각 종류와 그 종류의 갯수가 일치하는 지
//입력
AbaAeCe
baeeACA
//출력
YES

public class ex2 {
    public static String solution(String s,String x){
        String answer = "YES";
        HashMap<Character, Integer> map = new HashMap<>();

        for(char c1 : s.toCharArray()){
            map.put(c1,map.getOrDefault(c1,0) + 1);
        }

        for(char c2 : x.toCharArray()){
            if(!map.containsKey(c2) || map.get(c2)==0) return answer="NO";
            map.put(c2,map.get(c2)-1);
        }


        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String x = sc.next();
        System.out.println(solution(s,x));
    }
}

풀이
1.일단 기본 answer값을 YES로 설정, HashMap -> map을 생성한다
2.s.toCharArray를이용해서 첫 문자열을 forEach를 돌려서 map.put() 해서 map에 집어넣는다
3.두번 째 문자도 forEach문을 돌린다. 근데 여기서, 조건을 걸어준다. !map.containsKey(c2)를 해서 c2라는 key가 없는지 map.get(c2)를 해서 c2의 value가 0인지 조건을 건다. 둘 중에 해당하는 게 있으면 "NO"를 반환한다. 그렇게 하고 map.put(c2,map.get(c2)-1)을 문자열 끝까지 계속 해준다.

[ 주요 기능 ]
map.containsKey(key) : 해당 ket값이 map에 존재하는 지

3.매출액의 종류

//문제
입력되는  n만큼의 배열을 입력하고 k일 만큼의 경우에서 가지는 매출액의 종류의 개수
//입력
7 4
20 12 20 10 23 17 10
//출력
3 4 4 3

public class ex3 {
    public static ArrayList<Integer> solution(int n, int k,int[] arr){
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        int lt=0,rt=0;
        for(int i=0; i<k-1; i++){
            map.put(arr[i],map.getOrDefault(arr[i],0) + 1);
        }

        for(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) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }

        for(int x : solution(n,k,arr)) System.out.print(x + " ");
    }

풀이
1.ArrayList를 만들어서 k-1만큼(k=4라면 3의 길이만큼 0,1,2인덱스의 값까지)의 값을 미리 map에 담아 놓는다.
2.그러고 twopointer lt,rt를 이용해서 rt를 증가시기키면서 map.size()를 이용해서 map에 담겨있는 key의 갯수를 ArrayList에 담는다.
3.그러고 lt를 map에서 뺀다. 여기서 lt라는 값이 0이면 map에서 삭제시킨다

[ 주요 기능 ]
two pointer , sliding 알고리즘
HashMap 알고리즘
map.remove(key) : map의 key값 삭제

4.모든 아나그램 찾기

//문제
T,S 문자열이 주어지고 아나그램이 되는 S부분 문자열의 경우의 수를 구하라.
//입력
bacaAacba
abc
//출력
3

public class ex4 {
    public static int solution(String s1,String s2){
        int answer = 0;
        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();

        for(char x : s2.toCharArray()){
            map2.put(x,map2.getOrDefault(x,0)+1);
        }

        for(int i=0; i<s2.length()-1; i++){
            map1.put(s1.charAt(i),map1.getOrDefault(s1.charAt(i),0)+1);
        }

        int rt=0,lt=0;
        for(rt=s2.length()-1; rt<s1.length(); rt++){
            map1.put(s1.charAt(rt),map1.getOrDefault(s1.charAt(rt),0)+1);
                if(map1.equals(map2)) answer++;
                map1.put(s1.charAt(lt),map1.get(s1.charAt(lt))-1);
                if(map1.get(s1.charAt(lt)) == 0) map1.remove(s1.charAt(lt));
                lt++;
        }

        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String x = sc.next();
        System.out.println(solution(s,x));
    }
}

풀이
1.S문자 길이만큼만 T문자열을 map1에 저장, S문자열은 그냥 map2에 저장
2.lt,rt를 이용해서 .equals()를 이용해 비교하면서 같으면 answer++;

5.K번째 큰 수

//문제
카드를 3장 뽑아서 그 합의 k번째로 큰 수 출력.
//입력
10 3
13 15 34 23 45 65 33 11 26 42
//출력
143

public class ex5 {
    public static int solution(int n, int k, int[] arr){
        int answer = -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) answer=x;
        }
        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }

        System.out.print(solution(n,k,arr));
    }
}

풀이
1.3중 for문을 돌려서 TreeSet에 값을 더한다.
2.forEach문을 돌려서 Tset의 k번째 값을 리턴한다.