[JAVA] 알고리즘 문제풀이 기초 - HashMap, TreeSet -2

HashMap, TreeSet

모든 아나그램 찾기 (4-4)

설명 : S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하세요. 아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.
입력 : 첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다. S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다.
출력 : S단어에 T문자열과 아나그램이 되는 부분문자열의 개수를 출력합니다.
작성답안

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main t = new Main();
        Scanner scan = new Scanner(System.in);
        String str1 = scan.next();
        String str2 = scan.next();

        System.out.println(t.solution(str1, str2));
    }

    public Integer solution(String str1, String str2){
        int result = 0;

        HashMap<Character, Integer> map = new HashMap<>();
        for(char c: str2.toCharArray()){
            map.put(c, map.getOrDefault(c, 0)+1);
        }
        int size = str2.length();
        char[] ch = str1.toCharArray();
        for(int i=0; i<size-1; i++){
            if(map.containsKey(ch[i])) {
                map.put(ch[i], map.get(ch[i])-1);
            }
        }
        int lt=0;
        for(int rt=size-1; rt<str1.length(); rt++){
            int sum = 0;
            if(map.containsKey(ch[rt])) {
                map.put(ch[rt], map.get(ch[rt])-1);
            }
            boolean chk = true;
            for (Character key : map.keySet()) {
                if (map.get(key)!=0) chk=false;
            }
            if(chk) result++;

            if(map.containsKey(ch[lt])) map.put(ch[lt], map.get(ch[lt])+1);
            lt++;
        }

        return result;
    }
}

풀이 답변 ``` java import java.util.*;

public class Main { public static void main(String[] args) { Main t = new Main(); Scanner scan = new Scanner(System.in); String str1 = scan.next(); String str2 = scan.next();

    System.out.println(t.solution(str1, str2));
}

public Integer solution(String str1, String str2){
    int result = 0;

    HashMap<Character, Integer> amap = new HashMap<>();
    HashMap<Character, Integer> bmap = new HashMap<>();
    for(char c: str2.toCharArray()){
        bmap.put(c, bmap.getOrDefault(c, 0)+1);
    }

    int size = str2.length();
    char[] ch = str1.toCharArray();
    for(int rt=0; rt<size-1; rt++){
        amap.put(ch[rt], amap.getOrDefault(ch[rt], 0)+1);
    }
    int lt=0;
    for(int rt=size-1; rt<str1.length(); rt++){
        amap.put(ch[rt], amap.getOrDefault(ch[rt], 0)+1);

        if(amap.equals(bmap)) result++;

        amap.put(ch[lt], amap.get(ch[lt])-1);
        if(amap.get(ch[lt])==0) amap.remove(ch[lt]);
        lt++;
    }

    return result;
} } ```

특징
1. 내 풀이의 경우 map을 하나만 만들어서 거기서 차감을 하고, 모든값이 0일때만 카운트되도록 했는데
2. 알고보니 두개의 map도 equals로 비교가 가능했다!!!!
3. 두개의 map을 만들어, 긴 문자열을 투포인트 방식으로 가감하고
4. amap.equals(bmap) 으로 비교해주면 됨

K번째 큰 수 (4-5)

설명 : 현수는 1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있습니다. 같은 숫자의 카드가 여러장 있을 수 있습니다. 현수는 이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려고 합니다. 3장을 뽑을 수 있는 모든 경우를 기록합니다. 기록한 값 중 K번째로 큰 수를 출력하는 프로그램을 작성하세요. 만약 큰 수부터 만들어진 수가 25 25 23 23 22 20 19……이고 K값이 3이라면 K번째 큰 값은 22입니다.
입력 : 첫 줄에 자연수 N(3<=N<=100)과 K(1<=K<=50) 입력되고, 그 다음 줄에 N개의 카드값이 입력된다.
출력 : 첫 줄에 K번째 수를 출력합니다. K번째 수가 존재하지 않으면 -1를 출력합니다.
작성답안

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main t = new Main();
        Scanner scan = new Scanner(System.in);
        int card  = scan.nextInt();
        int arr[] = new int[card];
        int num = scan.nextInt();
        for(int i=0; i<card; i++){
            arr[i] = scan.nextInt();
        }

        System.out.println(t.solution(arr, num));
    }

    public Integer solution(int[] arr, int num){
        int result = 0;

        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int i=0; i<arr.length; i++){
            for(int j=i+1; j<arr.length; j++){
                for(int k=j+1; k<arr.length; k++){
                    map.put(arr[i]+arr[j]+arr[k], map.getOrDefault(arr[i]+arr[j]+arr[k], 0)+1);
                }
            }
        }

        int cnt=0;
        while (cnt<num){
            if(map.size()>num){
                result = map.lastKey();
                map.remove(result);
                cnt++;
            } else result = -1;
        }

        return result;
    }
}

특징
1. 3중 for문을 써서 작성한 답안. 이후 map에서 제일 높은수를 num번에 거쳐 삭제함
풀이 답안

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main t = new Main();
        Scanner scan = new Scanner(System.in);
        int card  = scan.nextInt();
        int arr[] = new int[card];
        int num = scan.nextInt();
        for(int i=0; i<card; i++){
            arr[i] = scan.nextInt();
        }

        System.out.println(t.solution(arr, num));
    }

    public Integer solution(int[] arr, int num){
        int result = -1;

        TreeSet<Integer> ts = new TreeSet<>(Collections.reverseOrder());
        for(int i=0; i<arr.length; i++){
            for(int j=i+1; j<arr.length; j++){
                for(int k=j+1; k<arr.length; k++){
                    ts.add(arr[i]+arr[j]+arr[k]);
                }
            }
        }

        int cnt=1;
        for (Integer t : ts) {
            if(cnt==num) {
                return result = t;
            }
            cnt++;
        }

        return result;
    }
}

특징
1. map보다 set을 사용하는것이 효율적 (중복시 거르는거라 카운트가 필요 없었음)
2. Set 생성시 Collections.reverseOrder()를 넣어주면 내림차순으로 정렬 됨
3. 삭제연산을 굳이 거치지말고 iter 사용해서 세번째 값 바로 출력하는게 빠름

IM

HashMap, TreeSet

모든 아나그램 찾기 (4-4)

K번째 큰 수 (4-5)