Java HashMap, TreeSet 알고리즘2

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

문제4 :

첫 줄에 첫 번째 문자열 s (길이 10,000이하)가 입력되고,

두 번째 줄에 문자열 t (문자열s보다 길이 작거나 같다.)이 입력된다.

s단어에 t문자열과 아나그램이 되는 부분문자열 개수를 출력하라/

부분문자열은 연속된 문자열이여야 한다.

입력예제

bacaAacba

abc

출력예제

3

설명 :

bac, acb, cba 이렇게 총 3개의 문자열이 abc 문자열과 아나그램이다. 따라서 3이 출력된다.

 

소스코드 :

import java.util.*;
class Main {
	public int solution(String s, String t) {
		int answer = 0;
		HashMap<Character, Integer> mapS = new HashMap<>();
		HashMap<Character, Integer> mapT = new HashMap<>();
		for(char x : t.toCharArray()) {
			mapT.put(x, mapT.getOrDefault(x, 0) + 1);
		}
		for(int i=0; i<t.length()-1; i++) {
			mapS.put(s.charAt(i), mapS.getOrDefault(s.charAt(i), 0) + 1);
		}
		int lt = 0;
		for(int rt=t.length()-1; rt<s.length(); rt++) {
			mapS.put(s.charAt(rt), mapS.getOrDefault(s.charAt(rt), 0) + 1);
			if (mapS.equals(mapT)) answer++;
			mapS.put(s.charAt(lt), mapS.get(s.charAt(lt)) - 1);
			if (mapS.get(s.charAt(lt)) == 0) mapS.remove(s.charAt(lt));
			lt++;
		}
		return answer;
	}

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

 

풀이 :

해쉬와 투포인터 그리고 슬라이딩 윈도우 알고리즘을 통해 문제를 해결하였다.

 

 

 

TreeSet

객체를 중복해서 저장할 수 없고 저장 순서가 유지되지 않는다는 Set의 성질을 가지고 있다.

하지만 HashSet과는 달리 TreeSet은 이진 탐색 트리 구조로 이루어져 있다.

생성을 위해서는 java.util.TreeSet 클래스를 import 한다.

내림차순을 위해 Collections을 사용하려면 java.util.Collections를 import 한다.

 

TreeSet 선언하기

// 오름차순 정렬
TreeSet<Integer> Tset = new TreeSet<>();
// 내림차순 정렬
TreeSet<Integer> Tset = new TreeSet<>(Collections.reverseOrder());

 

 

TreeSet 값 추가하기

Tset.add(2);

만약 내림차순 정렬로 선언하고 1, 2, 3, 4, 5를 차례대로 넣으면 5, 4, 3, 2, 1로 출력된다.

 

TreeSet 값 삭제하기

// 특정 값 삭제
Tset.remove(2);
// 첫 데이터 삭제
Tset.pollFirst();
// 마지막 데이터 삭제
Tset.pollLast();
// 전체 삭제
Tset.clear();

 

TreeSet 크기 구하기

Tset.size();

 

TreeSet 출력

// 첫 번째 수 출력
Tset.first();
// 마지막 수 출력
Tset.last();

TreeSet 출력을 위해선 향상된 for문을 이용하거나 iterator를 이용하면 된다.

 

 

문제5 :

첫 줄에 자연수 n(3<=n<=100)과 k(1<=k<=50)이 입력되고, 그 다음 줄에 n개의 카드값이 입력된다.

n장의 카드 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려고 하는데,

3장을 뽑을 수 있는 모든 경우의 수를 기록하고, 기록한 값 중 K번째로 큰 수를 출력하는 프로그램을 작성하시오.

만약 12 12 9 9 8 6 처럼 입력되었다면 3번째로 큰 수는 8이 출력된다.

입력예제

10 3

13 15 34 23 45 65 33 11 26 42

출력예제

143

 

소스코드 :

import java.util.*;
class Main {
	public int solution(int n, int k, int[] arr) {
		int answer = 0;
		TreeSet<Integer> Tset = new TreeSet<>(Collections.reverseOrder());
		for(int i=0; i<n; i++) {
			for(int j=i+1; j<n; j++) {
				for(int t=j+1; t<n; t++) {
					Tset.add(arr[i] + arr[j] + arr[t]);
				}
			}
		}
		int cnt = 0;
		for(int x : Tset) {
			cnt++;
			if (cnt == k) return x;
		}

		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		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.println(T.solution(n, k, arr));
	}
}

 

풀이 :

3장을 선택해서 뽑기 때문에 3중 for문을 이용하였다.

TreeSet은 중복을 제거하기 때문에 TreeSet에서 바로 k번째 수를 찾아서 출력하면 된다.