본문 바로가기
Java/Java 알고리즘 인프런

[리뷰] 해결 못한 알고리즘 다시 풀기 -2

앤 썸 2022. 7. 8. 16:22
반응형

1. 학급회장 map

package hashtree.ch04;

import java.util.*;

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('C'));
		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.println(T.solution(n, str));
	}
}

 

2. 아나그램 map

package hashtree.ch04;

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

public class Hashtree02_1 {
	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) {
		Hashtree02_1 T = new Hashtree02_1();
		Scanner kb = new Scanner(System.in);
		String a = kb.next();
		String b = kb.next();
		System.out.print(T.solution(a, b));
	}
}

 

3. 매출액의 종류 hash / sliding

map에서 빼는 방법 - map.put()으로 -1 한 후, map.get()==0 이면, map.remove();한다.

  map.put(arr[i], map.get(arr[i]) - 1);
			if (map.get(arr[i]) == 0)
				map.remove(arr[i]);
                
  map.put(arr[i-m], map.get(arr[i-m])-1);
      		if(map.get(arr[i-m])==0)
      			map.remove(arr[i-m]);
package hashtree.ch04;

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

public class Hashtree03 {
	// 매출액의 종류
	// N일 매출기록, 연속된 K일 동안 매출액의 종류를 구간별로
	// N일 중, 연속 K일 간 매출액이 다른 경우의 종류의 수 출력
	// 첫 줄에 N일, K일 주어진다.
	// 두 번째 줄에 N개의 숫자열 주어지고, 500이하 음이 아닌 정수
	// 첫 줄에 각 구간의 매출액 종류의 개수 순서대로 출력
	public ArrayList<Integer> solution(int n, int k, int[] arr) {
		ArrayList<Integer> answer = new ArrayList<>();
		// 매출액 리스트 객체 생성(중복허용)
		HashMap<Integer, Integer> HM = new HashMap<>();
		// n일, k일로 이루어진 자료구조 -> N일에 대해 K일 동안의 매출액

		// N일에 대해 K일 동안의 매출액 중에서, 같지 않은 매출액의 개수

		// K일까지의 매출액 구하기
		for (int i = 0; i < k - 1; i++) {
			// 0부터 k일보다 하루적을때 즉, k일동안
			HM.put(arr[i], HM.getOrDefault(arr[i], 0) + 1);
			// 맵에 처음부터 i번째 키에, 해당 키의 값이 있으면 +1, 없으면 0을 넣는다.
		}

		// K일부터 매출액 구하기
		int lt = 0;
		// 순서대로 세는 변수에 0으로 초기화
		for (int rt = k - 1; rt < n; rt++) {
			// K일부터 세는 변수로 초기화 [0부터 세기 때문에 k-1] -> N일까지의 K일 동안의 매출액 개수
			HM.put(arr[rt], HM.getOrDefault(arr[rt], 0) + 1);
			// 맵에 뒤에서부터 rt번째 키에, 해당 키의 값이 있으면 +1, 없으면 0을 넣는다.
			answer.add(HM.size());
			// 매출액의 개수를 출력리스트에 추가

			HM.put(arr[lt], HM.get(arr[lt]) - 1);
			// 같은 매출액이 있으면 -1
			if (HM.get(arr[lt]) == 0)
				// 매출액의 개수가 0이면
				HM.remove(arr[lt]);
				// 해당 매출액을 없앤다.
			lt++;
			//순서대로 세는 변수에 +1
		}
		return answer;
	}

	public static void main(String[] args) {
		Hashtree03 T = new Hashtree03();
		Scanner kb = new Scanner(System.in);

		int n = kb.nextInt();
		int k = kb.nextInt();
		int[] arr = new int[n];
		// 인트 배열 arr을 n개의 배열로 초기화
		for (int i= 0; i < n; i++) {
			arr[i] = kb.nextInt();
		}
		for (int x : T.solution(n, k, arr))
			System.out.print(x + " ");
		kb.close();
	}

	
}

 

4. 모든 아나그램 찾기 hash / sliding

package hashtree.ch04;
// #모든 아나그램 찾기

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

public class Hashtree04_1 {
	public int solution(String str1, String str2) {
		int answer = 0;
		HashMap<Character, Integer> am = new HashMap<>();
		HashMap<Character, Integer> bm = new HashMap<>();
		for (char x : str2.toCharArray())
			bm.put(x, bm.getOrDefault(x, 0) + 1);
		int L = str2.length() - 1;
		for (int i = 0; i < L; i++) {
			// L전까지, 1개 빼고
			am.put(str1.charAt(i), am.getOrDefault(str1.charAt(i), 0) + 1);
			// str1의 i번� 문자를 넣는다.
		}
		int lt = 0;
		for (int rt = L; rt < str1.length(); rt++) {
			am.put(str1.charAt(rt), am.getOrDefault(str1.charAt(rt), 0) + 1);
			// rt값 카운팅
			if (am.equals(bm))
				answer++;
			// 키도 같고 값도 같다.
			am.put(str1.charAt(lt), am.get(str1.charAt(lt)) - 1);
			// lt가 가리키는 곳에서 하나를 �A다

			// 0일때 체크해서 뺀다/
			if (am.get(str1.charAt(lt)) == 0) {
				am.remove(str1.charAt(lt));
				lt++;

			}
		}

		return answer;
	}

	public static void main(String[] args) {
		Hashtree04_1 T = new Hashtree04_1();

		Scanner kb = new Scanner(System.in);
		String str1 = kb.next();
		String str2 = kb.next();
		System.out.println(T.solution(str1, str2));
	}

}

 

5. K번째 큰수 Treeset

package hashtree.ch04;

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

public class Hashtree05 {
	//#  K번째 큰 수
	// 1부터 100사이의 자연수의 중복 가능한 N장의 카드
	// 3장을 뽑아 각 카드의 적힌 수의 합 기록
	// 기록할 수 있는 모든 경우 중 K번째로 큰 수 출력
	// 첫 줄에 자연수 N과 K입력, 두 번째 줄에 N개의 카드값 입력
	// 첫 줄에 K번째 수 출력, 존재하지 않는다면 -1 출력

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

	public int solution(int[] arr, int n, int k) {
		int answer = -1;
		// 존재하지 않음으로 가정
		TreeSet<Integer> Tset = new TreeSet<>(Collections.reverseOrder());
		// TreeSet은 set 인터페이스에서 중복 허용하지 않고, 객체를 정렬할 수 있다. -> 범위 검색 및 정렬시 사용
		// 레드-블랙 트리

		// {Collections.sort(arrayList, reverseOrder()), Collections.sorts(), implements
		// Comparable<객체> - compareTo(객체)}
		// {ArrayList.sort(Comparator.naturalOrder()),
		// ArrayList.sort(Comparator.reverseOrder())}
		// Comparable : 기존 정의 로직대로 정렬
		// Comparator : 정의된 자료형의 정렬방식을 바꿀 때

		for (int i = 0; i < n; i++) {
			// N장의 카드 순서대로 0번째에서 끝까지 반복
			for (int j = i + 1; j < n; j++) {
				// 순서대로에서 +1 -> 이중 for문, 0번째 중 1번째에서 끝까지 반복
				for (int l = j + 1; l < n; l++) {
					// 순서대로 +2 -> 삼중for문, 0번째 중 1번째의 2번째에서 끝까지 반복
					Tset.add(arr[i] + arr[j] + arr[l]);
					// 각각 for문을 돌리면서 3개의 값의 합 -> reverse이므로 큰 수부터 정렬
				}
			}
		}
		int cnt = 0;

		Tset.remove(143);
		System.out.println(Tset.size());
		System.out.println("first : " + Tset.first());
		System.out.println("last : " + Tset.last());

		for (int x : Tset) {
			System.out.println(x);
			cnt++;
			// Tset을 돌면서 count 증가
			if (cnt == k)
				return x;
			// count와 k값이 같으면 값 x 반환
		}
		return answer;
		// count와 k값이 같지 않으면 값 -1 반환
	}
}

 

#Tset -> 오름차순 정렬 해주는 자료구조

TreeSet <Integer> Tset = new TreeSet<>();
//오름차순

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

Tset.first()
//오름차순 기준 최솟값, 내림차순 기준 최댓값

Tset.last()
//오름차순 기준 최댓값, 내림차순 기준 최솟값

 

# map에서 Value로 Key 찾기

 

Collections.max(map.entrySet(), Map.Entry.comparingByValue()).getKey());
//Value 최댓값의 key값

Collections.min(map.entrySet(), Map.Entry.comparingByValue()).getKey());
//Value 최솟값의 key값

 

package hashtree04_2;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Valuetokey {
	public void solution(int n, String str) {
		char[] arr = str.toCharArray();

		HashMap<Character, Integer> map = new HashMap<>();
		for (int i = 0; i < n; i++) {
			map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
		}

		// 1. Collections을 이용한 최댓값, 최솟값 키 찾기
		System.out.println("Collections 이용 : " + Collections.max(map.entrySet(), Map.Entry.comparingByValue()).getKey()
				+ " " + Collections.min(map.entrySet(), Map.Entry.comparingByValue()).getKey());

		// 2. Stream을 이용한 최댓값, 최솟값 키 찾기
		System.out.println("Stream 이용 : "
				+ map.entrySet().stream().max((entry1, entry2) -> entry1.getValue() > entry2.getValue() ? 1 : -1).get()
						.getKey()
				+ " " + map.entrySet().stream().min((entry1, entry2) -> entry1.getValue() > entry2.getValue() ? 1 : -1)
						.get().getKey());

		// value로 키 가져오기
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for (int y : map.values()) {
			min = Math.min(y, min);
		}

		for (int y : map.values()) {
			max = Math.max(y, max);
		}

		// 1. keySet()이용
		System.out.println("keySet이용");
		for (Character key : map.keySet()) {
			Integer value = map.get(key);
			System.out.print(key + " " + value + ", ");

			if (value == min) {
				System.out.println("keySet 이용한 min:"+key);
			}
			if (value == max) {
				System.out.println("keySet 이용한 max:"+key);
			}
		}

		System.out.println();
		
		// 2. entrySet() 이용
		System.out.println("entrySet이용");
		for (Map.Entry<Character, Integer> entry : map.entrySet()) {
			char key = entry.getKey();
			int value = entry.getValue();
			System.out.print(key + " " + value + ", ");

			if (value == min) {
				System.out.println("entrySet 이용한 min:"+key);
			}
			if (value == max) {
				System.out.println("entrySet 이용한 max:"+key);
			}
		}

	}

	public static void main(String[] args) {
		Valuetokey T = new Valuetokey();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		String str = kb.next();
		T.solution(n, str);

	}

}

 

# HashMap<String, Map<String, Integer>>로 구성된 map에 넣기

LinkedHashMap<String, LinkedHashMap<String, Integer>> map = new LinkedHashMap<>();
for(int i=0;i<arr.length;i++) {
LinkedHashMap<String, Integer> list = new LinkedHashMap<>();
String[] str = arr[i].split(" ");
if(map.containsKey(str[0])) {
    if(map.get(str[0]).containsKey(str[1])) {
        map.get(str[0]).put(str[1], map.get(str[0]).get(str[1])+1);
    }
    else {
        list=map.get(str[0]);
        list.put(str[1],1);
        map.put(str[0], list);
    }

}
else {
    list.put(str[1], 1);
    map.put(str[0], list);
}

 

반응형
저작자표시 비영리

'Java > Java 알고리즘 인프런' 카테고리의 다른 글

[Ch.09 - Greedy] 02. 회의실 배정  (0) 2022.07.15
[Ch.09 - Greedy] 01. 씨름 선수  (0) 2022.07.15
해당 날짜의 날씨보다 따뜻한 날씨가 오는데 걸리는 기간  (0) 2022.07.06
String에 char 추가하기  (0) 2022.06.30
[Ch.07 - Recursive] 03. 팩토리얼  (0) 2022.06.22

'Java/Java 알고리즘 인프런' Related Articles

티스토리툴바