[JAVA] 알고리즘 문제풀이 기초 - HashMap, TreeSet -1
HashMap, TreeSet
기본 함수
- Map이름.getOrDefault(a,b) = 키가 a인 vaule가 있으면 가져오고 없으면 b 호출
- Map이름.containsKey(a) = a라는 키가 있는지 boolean 형으로 반환
- Map이름.size = key의 갯수
- Map이름.remove(a) = a 키를 삭제함 (삭제하면서 value를 리턴함)
- Map이름.keySet() = key의 집합
학급 회장(해쉬) (4-1)
-
설명 : 학급 회장을 뽑는데 후보로 기호 A, B, C, D, E 후보가 등록을 했습니다. 투표용지에는 반 학생들이 자기가 선택한 후보의 기호(알파벳)가 쓰여져 있으며 선생님은 그 기호를 발표하고 있습니다. 선생님의 발표가 끝난 후 어떤 기호의 후보가 학급 회장이 되었는지 출력하는 프로그램을 작성하세요. 반드시 한 명의 학급회장이 선출되도록 투표결과가 나왔다고 가정합니다.
-
입력 : 첫 줄에는 반 학생수 N(5<=N<=50)이 주어집니다. 두 번째 줄에 N개의 투표용지에 쓰여져 있던 각 후보의 기호가 선생님이 발표한 순서대로 문자열로 입력됩니다.
-
출력 : 학급 회장으로 선택된 기호를 출력합니다.
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
String str = scan.next();
System.out.print(t.solution(str, num));
}
public char solution(String str, int num){
char result=' ';
HashMap<Character, Integer> map = new HashMap<>();
for (char c : str.toCharArray()) {
map.put(c, map.getOrDefault(c, 0)+1);
}
int max=0;
for (Character key : map.keySet()) {
if(map.get(key)>max) {
max = map.get(key);
result = key;
}
}
return result;
}
}
- 특징
- 문자열을 toCharArray로 변환하여 하나씩 map에 담기
- 이 때 map.getOrDefault(x, 0)+1를 이용해서 이미 담겨진 키는 +1씩 카운트
- 다시 반복을 돌면서 가장 max값을 찾아 반환
- 문자열을 toCharArray로 변환하여 하나씩 map에 담기
아나그램(해쉬) (4-2)
-
설명 : Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 합니다. 예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재 배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다. 길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세요. 아나그램 판별시 대소문자가 구분됩니다.
-
입력 : 첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다. 단어의 길이는 100을 넘지 않습니다.
-
출력 : 두 단어가 아나그램이면 “YES”를 출력하고, 아니면 ”NO”를 출력합니다.
-
작성 답안 (두개의 맵을 만들어 비교)
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.print(t.solution(str1, str2));
}
public String solution(String str1, String str2){
String result = "NO";
HashMap<Character, Integer> map = new HashMap<>();
for(char c1: str1.toCharArray()){
map.put(c1, map.getOrDefault(c1, 0)+1);
}
for (char c2: str2.toCharArray()){
if(map.containsKey(c2)){
map.put(c2, map.get(c2)-1);
if(map.get(c2)==0) map.remove(c2);
}
}
if(map.size()==0) result="YES";
return result;
}
}
- 풀이 답안
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.print(t.solution(str1, str2));
}
public String solution(String str1, String str2){
String result = "YES";
HashMap<Character, Integer> map = new HashMap<>();
for(char c1: str1.toCharArray()){
map.put(c1, map.getOrDefault(c1, 0)+1);
}
for (char c2: str2.toCharArray()){
if(!map.containsKey(c2) || map.get(c2)==0) return "NO";
map.put(c2, map.get(c2)-1);
}
return result;
}
}
- 특징
- str1의 키와 카운트 값을 모두 맵에 담아두로
- str2를 돌며 첫번째로 containsKey() 진행
- 두번째로 카운트 감소. 0카운트가 되면 remove
- 맵 사이즈가 0이되면 YES 처리
- str1의 키와 카운트 값을 모두 맵에 담아두로
매출액의 종류 (4-3)
-
설명 : 현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 매출액의 종류를 각 구간별로 구하라고 했습니다. 만약 N=7이고 7일 간의 매출기록이 아래와 같고, 이때 K=4이면 20 12 20 10 23 17 10 각 연속 4일간의 구간의 매출종류는 첫 번째 구간은 [20, 12, 20, 10]는 매출액의 종류가 20, 12, 10으로 3이다. 두 번째 구간은 [12, 20, 10, 23]는 매출액의 종류가 4이다. 세 번째 구간은 [20, 10, 23, 17]는 매출액의 종류가 4이다. 네 번째 구간은 [10, 23, 17, 10]는 매출액의 종류가 3이다. N일간의 매출기록과 연속구간의 길이 K가 주어지면 첫 번째 구간부터 각 구간별 매출액의 종류를 출력하는 프로그램을 작성하세요.
-
입력 : 첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다. 두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.
-
출력 : 첫 줄에 각 구간의 매출액 종류를 순서대로 출력합니다.
-
작성 답안
import java.util.*;
public class Main {
public static void main(String[] args) {
Main t = new Main();
Scanner scan = new Scanner(System.in);
int v = scan.nextInt();
int d = scan.nextInt();
int[] arr = new int[v];
for(int i=0; i<v; i++){
arr[i] = scan.nextInt();
}
for (int i : t.solution(arr, d)) {
System.out.print(i+" ");
}
}
public ArrayList<Integer> solution(int[] arr, int d){
ArrayList<Integer> result = new ArrayList();
int lt=0;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i=0; i<d-1; i++){
map.put(arr[i], map.getOrDefault(arr[i], 0)+1);
}
for(int rt=d-1; rt<arr.length; rt++){
map.put(arr[rt], map.getOrDefault(arr[rt], 0)+1);
result.add(map.size());
map.put(arr[lt], map.get(arr[lt])-1);
if(map.get(arr[lt])==0) map.remove(arr[lt]);
lt++;
}
return result;
}
}
- 특징
- 투포인트 형식과 HashMap을 같이 사용
- 최대범위보다 적은 배열인덱스값들은 미리 map에 셋팅. 최대범위부터 rt 진행
- map추가 후 사이즈를 리스트에 추가함
- lt를 지움. 단 lt가 0인 경우에는 key를 삭제해줌
- 그리고 다시 rt를 한칸 나아가 3번 반복
- 투포인트 형식과 HashMap을 같이 사용