Java HashMap, TreeSet 알고리즘1

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) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

 

HashMap은 Key와 Value로 이루어진 자료구조이다.

key에 해당하는 value값 얻기 : map.get("key")

맵에 해당하는 키가 있는지 조사(있다면 true 리턴) : map.contaionsKey("key")

key값에 해당하는 아이템(key, value) 삭제 후 그 value값 리턴 : map.remove("key") // 삭제된 후 "key" 출력됨

Map의 갯수 리턴 : map.size()

맵의 모든 key 모아서 리턴 : map.ketSet()

 

 

문제1 :

기호 A, B, C, D, E 의 후보가 학급 회장 후보로 등록했다.

선생은 각 알파벳이 쓰여진 투표용지를 펼쳐 읽는다. 그 순서대로 문자열로 입력된다.

어떤 기호의 후보가 회장이 되었는지 출력하는 프로그램을 작성하시오.

첫 줄에는 반 학생수 n이 입력되고 두 번째 줄에는 선생이 발표한 순서대로 n개만큼 문자열로 입력된다.

 

소스코드 :

import java.util.*;
class Main {
	public char solution(int n, String str) {
		char answer = ' ';
		HashMap<Character, Integer> map = new HashMap<>();
		for(char x : str.toCharArray()) {
			map.put(x, map.getOrDefault(x, 0) + 1);
		}
		int max = Integer.MIN_VALUE;
		for(char key : map.keySet()) {
			if (map.get(key) > max) {
				max = map.get(key);
				answer = key;
			}
		}
		return answer;
	}

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

 

 

 

문제2 :

두 문자열이 아나그램(나열 순서가 다르지만 그 구성이 일치)일 경우 YES,

아닐 경우 NO를 출력하는 프로그램을 작성하여라

입력예제

DaRam

aRmaD

출력예제

YES

 

소스코드 :

import java.util.*;
class Main {
	public String solution(String str1, String str2) {
		String answer = "YES";
		HashMap<Character, Integer> map = new HashMap<>();
		for (char x : str1.toCharArray()) {
			map.put(x, map.getOrDefault(x,0)+1);
		}
		for (char x : str2.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) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		String str1 = sc.next();
		String str2 = sc.next();
		System.out.println(T.solution(str1, str2));
	}
}

 

 

 

문제 3 :

첫 줄에 n(5<=n<=100,000)과 k(2<=k<=n)가 주어진다.

두 번째 줄에 n개의 숫자열이 주어진다. 각 숫자는 500 이하의 음이 아닌 정수이다.

첫 줄에 k만큼 연속 k일 간의 숫자 종류를 구하시오.

예를 들면

입력예제

7 4

20 12 20 10 23 17 10

일 경우

[20 12 20 10]의 숫자 종류는 3, 그 다음 [12 20 10 23]의 숫자 종류는 4 , ....

해서 출력 예제는

3 4 4 3 이 된다.

 

소스코드 :

import java.util.*;
class Main {
	public ArrayList<Integer> solution(int n, int k, int[] arr) {
		ArrayList<Integer> answer = new ArrayList<>();
		HashMap<Integer, Integer> map = new HashMap<>();
		// 첫 번째 구간 종류 구하기
		for(int i=0; i<k; i++) {
			map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
		}
		answer.add(map.size());

		// 두 번째 구간부터 투포인터 + 슬라이딩 윈도우 알고리즘으로 종류 구하기
		int lt = 0, rt = k;
		while(rt < n) {
			map.put(arr[rt], map.getOrDefault(arr[rt], 0) + 1);
			map.put(arr[lt], map.get(arr[lt]) - 1);
			if (map.get(arr[lt]) == 0) map.remove(arr[lt]);
			answer.add(map.size());
			rt++;
			lt++;
		}
		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();
		}
		for(int x : T.solution(n, k, arr)) {
			System.out.print(x+" ");
		}
	}
}

 

사실 첫번째 구간을 i<k가 아니라 i<k-1로 넣고 슬라이딩 윈도우 알고리즘을 구현하는게 더 정석적이다.

그건 이후 [문제4] 에서 구현하도록 하겠다.