코딩 테스트 Java Hash, Set 문제 풀이

개요와 목적

코딩 테스트 대표적인 Hash, Set 문제들을 풀어보고,

Hash, Set의 문제 풀이 방식에 대해서 알아본다.

아나그램

AbaAeCe baeeACA

abaCC Caaab

---

풀이

정렬로도 풀 수 있지만, hashMap과 getOrDefault를 사용해서 풀어보자

public class 아나그램 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();

        char[] aChars = a.toCharArray();
        char[] bChars = b.toCharArray();

        HashMap<Character, Integer> map = new HashMap<>();
        String answer = "YES";
        //먼저 첫번 째 문자열로 문자 별로 개수 값으로 가지고 있는 맵 만들기
        for (char aChar : aChars) {
            map.put(aChar, map.getOrDefault(aChar, 0)+1);
        }

        for (char bChar : bChars) {
            //두번 째 문자열의 문자가 없거나,값이 0이면 NO 출력
            if (!map.containsKey(bChar) || map.get(bChar) == 0) {
                answer = "NO";
                break;
            } else {
                map.put(bChar, map.get(bChar) - 1);
            }
        }
        System.out.println(answer);
    }
}

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

7 4 20 12 20 10 23 17 10

---

풀이

이중 for문으로 풀게 되면 시간이 초과된다

HashMap과 lt, rt(slide window)를 사용하여 풀어보자.

public class 매출액의종류 {
    public static void main(String[] args) {
        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();
        }

        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<Integer, Integer> HM = new HashMap<>();
        //먼저 k번 전 까지 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++){
            //한칸 전진 했으니, 해시 맵의 키 개수를 answer에 넣어 준다.
            HM.put(arr[rt], HM.getOrDefault(arr[rt], 0)+1);
            answer.add(HM.size());
            //lt를 앞으로 한칸 전진
            HM.put(arr[lt], HM.get(arr[lt])-1);
            //값이 0이되면 삭제하기 맵 사이즈에 포함되지 않게.
            if(HM.get(arr[lt])==0) HM.remove(arr[lt]);
            lt++;
        }
        System.out.println(answer);
    }
}

K번째 큰수(TreeSet)

10 3 13 15 34 23 45 65 33 11 26 42

---

풀이

3개의 값을 합한 값을 중복을 제거하고, 정렬을 시켜주는 TreeSet에 넣어서 K번 째 값을 구하면 된다.

package 해시셋;

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

public class K번째큰수 {

    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();
        }
        //내림차순으로 중복을 제거하는 Set
        TreeSet<Integer> set = 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++) {
                    set.add(arr[i] + arr[j] + arr[l]);
                }
            }
        }

        int answer = -1;
        int cnt = 1;
        for (Integer integer : set) {
            if (cnt == k) {
                answer = integer;
            }
            cnt++;
        }
        System.out.println(answer);
    }
}