코딩테스트 대비 (HashMap, TreeSet)

1. 학급 회장

문제

개념

HashMap.getOrDefault(문자, 0) : 문자를 key 값으로 가진 게 없으면 value로 0을 리턴해라.
HashMap.containsKey(문자) : 문자를 key 값으로 가진 게 있는지 없는지 true, false 리턴
HashMap.size() : key의 개수를 리턴
HashMap.remove(문자) : 문자에 해당하는 key를 삭제

풀이

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

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);
        }
        // System.out.println(map.containsKey('F'));
        // System.out.println(map.size());
        // System.out.println(map.remove('A'));
        
        int max = Integer.MIN_VALUE;
        for(char key : map.keySet()) {
            // System.out.println(key + " " + map.get(key));
            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.HashMap;
import java.util.Scanner;

public class Main {
    public String solution(String s1, String s2) {
        String answer = "YES";
        HashMap<Character, Integer> map = new HashMap<>();

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

        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 a = kb.next();
        String b = kb.next();
        System.out.print(T.solution(a, b));
    }
}

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

문제

풀이

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

public class Main {
    public ArrayList<Integer> solution(int n, int k, int[] arr) {
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<Integer, Integer> HM = new HashMap<>();

        for(int i = 0; i < k - 1; i++) {
            HM.put(arr[i], HM.getOrDefault(arr[i], 0) + 1);
        }
        
        int lt = 0;
        for(int rt = k - 1; rt < n; rt++) {
            HM.put(arr[rt], HM.getOrDefault(arr[rt], 0) + 1);
            answer.add(HM.size());
            HM.put(arr[lt], HM.get(arr[lt]) - 1);
            
            if(HM.get(arr[lt]) == 0) {
                HM.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, slding window : 시간복잡도 O(n))

문제

풀이

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

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);
        }
        
        int L = b.length() - 1;
        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번째 큰 수

문제

개념

Collections.reverseOrder() : 내림차순으로 정렬되게 만듦
TreeSet.remove(원소) : 원소에 해당하는 것을 TreeSet에서 삭제
TreeSet.size() : 원소의 개수를 리턴
TreeSet.first() : TreeSet에서 가장 첫번째 원소 값을 리턴
TreeSet.last() : TreeSet에서 가장 마지막에 위치한 원소 값을 리턴

풀이

import java.util.Collections;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public int solution(int[] arr, int n, int k) {
        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;
        // Tset.remove(143);
        // System.out.println(Tset.size());
        // System.out.println(Tset.first());
        // System.out.println(Tset.last());
        for(int x : Tset) {
            cnt++;
            if(cnt == k) {
                return x;
            }
        }

        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();
        }

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