HashMap, TreeSet - (2)

HashMap, TreeSet - (2)

4-3. [Re] 매출액의 종류

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

/* 04-03. 매출액의 종류 Re
[입력]
첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.
[출력]
첫 줄에 각 구간의 매출액 종류를 순서대로 출력합니다.*/
public class Main1 {
    //솔루션 함수 
    public ArrayList<Integer> solution(int n, int k, int[]arr){
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<Integer, Integer> map= new HashMap<>();
        //초기값. 0부터 k-1까지 간격일수 동안의 매출액 종류 put처리
        for(int i =0; i<k-1; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0)+1);
        }

        //Two Pointers 알고리즘
        int lt = 0;
        for(int rt = k-1; rt<n; rt++) {
            //rt가 찍은 애를 담기 
            map.put(arr[rt], map.getOrDefault(arr[rt], 0)+1);
            //종류별로 카운팅 했으니까 answer에도 담기
            answer.add(map.size());

            //rt한칸 증가하면 기존에 lt찍었던 애는 가져와서 -1 감소해줘야 함 
            map.put(arr[lt], map.get(arr[lt])-1);
            //lt 감소했더니 0이 됐으면 그 종류는 카운팅 하면 안되니까 remove처리
            if(map.get(arr[lt]) == 0) map.remove(arr[lt]); 
            lt++;//lt도 한칸 증가
        }
        return answer;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        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-4. 모든 아나그램 찾기 (해쉬, 투포인터, 슬라이딩 윈도우)

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

/* 04-04. 모든 아나그램 찾기 (해쉬, 투포인터, 슬라이딩 윈도우)
[설명]
S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하세요.
아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.
*/
public class Main2 {
    //솔루션 함수
    public int solution(String a, String b) {
        int answer =0;
        HashMap<Character, Integer> aM = new HashMap<>();
        HashMap<Character, Integer> bM = new HashMap<>();
        //우선 b가 기준T 가 되므로 미리 세팅해둠
        for(char x : b.toCharArray()) {
            bM.put(x, bM.getOrDefault(bM, 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) {
        // TODO Auto-generated method stub
        Main2 T = new Main2();
        Scanner kb = new Scanner(System.in);

        String a = kb.next();
        String b= kb.next();

        System.out.println(T.solution(a, b));
    }
}

🟨Collection 인터페이스 기반 구현 클래스의 종류

1) List 클래스

: 선형 자료구조 구현 클래스

2) Set 클래스

: 비선형 자료구조 구현 클래스

• Set 자료형의 특징2) 정렬 지원
• 1) 중복 허용 X

🟨 TreeSet 개념

• 이진탐색트리 형태로 데이터 저장하는 컬렉션

🟨 TreeSet 선언

TreeSet<자료형> 변수면 = new TreeSet<>();

🟨 TreeSet 정렬

1) 오름차순 [기본]

TreeSet<자료형> 변수 = new TreeSet<>();

2) 내림차순 : reverseOrder() 용

TreeSet<자료형> 변수 = new TreeSet<>(Collections.reverseOrder());

[자주 사용하는 함수]

//내부 원소 제거 
remove( ); 

//원소의 개수
size(); 

//첫 원소 | 최대 최소일 때 사용 O
 1) 기본 오름차순일 때 : 최솟값 뽑음
 2) 내림차순 정렬 시 : 최댓값 뽑음 
first(); 

//마지막 원소 | 최대 최소일 때 사용 O
 1) 기본 오름차순일 때 : 최댓값 뽑음
 2) 내림차순 정렬 시 : 최솟값 뽑음
last();

4-5. k번째 큰 수 (TreeSet 사용)

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

/* 04-05. k번째 큰 수 
[입력]
첫 줄에 자연수 N(3<=N<=100)과 K(1<=K<=50) 입력되고, 그 다음 줄에 N개의 카드값이 입력된다.
[출력]
첫 줄에 K번째 수를 출력합니다. K번째 수가 존재하지 않으면 -1를 출력합니다.
*/
public class Main3 {
    //솔루션 함수 
    public int solution(int n, int k, int[]arr) {
        int answer= -1;
        //TreeSet을 내림차순 정렬 
        TreeSet<Integer> Tset = new TreeSet<>(Collections.reverseOrder());

        //n개의 카드 중 3장을 뽑는 것
        for(int i = 0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                for(int l = j+1; l<n; l++) {
                    //뽑은 3개 카드를 더해서 set에 추가
                    Tset.add(arr[i]+arr[j]+arr[l]);
                }
            }
        }
        int cnt = 0; //몇번째인지 누적
        //TreeSet 내부에서 k번째 큰 수 탐색
        for(int x : Tset) {
            cnt++;
            if(cnt == k) return x;
        }

        return answer;
    }
    //메인 실행 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        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(n, k, arr));
    }
}