오늘의 학습 키워드 및 문제
#문자열 #해시
[백준] 할리갈리
https://www.acmicpc.net/problem/27160
문제풀이
보자마자 HashMap으로 풀어야겠다고 생각했다.
정해진 과일에 해당 과일의 갯수가 다를 수 있으니 중복될 수 없는 key와 변경이 가능하고 중복된 값이 있어도 되는 value를 사용하는 HashMap이 적합하다고 생각했다.
- 입력 클래스 초기화, 과일과 과일의 갯수를 담을 HashMap 초기화, 결과값을 담을 String을 초기화
- 펼쳐진 카드의 개수 n을 입력
- n번의 반복문 시작
3-1. 카드의 정보 입력
3-2. HashMap에 입력받은 과일(key)이 있는지 확인
3-3. 있으면 기존의 key에 대한 value + 입력받은 value 저장
3-4. 없으면 입력받은 value 저장 - 반복문을 통해 HashMap에 저장된 과일이 5개인 데이터가 있는지 확인하여 있으면 "YES"
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
HashMap<String, Integer> map = new HashMap<String, Integer>();
String rtn = "NO";
int n = Integer.parseInt(br.readLine());
for(int i=0; i<n; i++) {
String[] s = br.readLine().split(" ");
if(map.containsKey(s[0])) {
map.put(s[0], map.get(s[0])+Integer.parseInt(s[1]));
} else {
map.put(s[0], Integer.parseInt(s[1]));
}
}
for(Map.Entry<String, Integer> m : map.entrySet()) {
if (m.getValue() == 5) {
rtn = "YES";
}
}
System.out.println(rtn);
br.close();
}
}다른방법
1. Set<Map.Entry<K,V>> 반복문 말고 values() 사용
HashMap의 values()는 저장되어있는 값들을 모두 Collection 타입으로 반환
Collection에는 해당 요소가 포함되어있는지 확인하는 contains()를 지원
반복문을 사용하지 않고 같은 과일 카드가 5장 있는지 확인 가능
가독성 굿
하지만 values()이 반환하는 Collection(List)은 map의 value들을 복사하여 새로운 객체로 만들고 entrySet()이 반환하는 Set은 HashMap의 내부 데이터를 직접 참조하여 동작하며 새로운 데이터를 복사하지 않는다는 점에서 entrySet()이 좀 더 성능 좋은 코드라고 볼 수 있을 것 같다.
(성공)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
HashMap<String, Integer> map = new HashMap<String, Integer>();
int n = Integer.parseInt(br.readLine());
for(int i=0; i<n; i++) {
String[] s = br.readLine().split(" ");
if(map.containsKey(s[0])) {
map.put(s[0], map.get(s[0])+Integer.parseInt(s[1]));
} else {
map.put(s[0], Integer.parseInt(s[1]));
}
}
if (map.values().contains(5)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
br.close();
}
}2. values().contains() 말고 containsValue() 사용
왜 이 생각을 못했니..(성공)
근데 제일 메모리사용 많이 함..0.0
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
HashMap<String, Integer> map = new HashMap<String, Integer>();
int n = Integer.parseInt(br.readLine());
for(int i=0; i<n; i++) {
String[] s = br.readLine().split(" ");
if(map.containsKey(s[0])) {
map.put(s[0], map.get(s[0])+Integer.parseInt(s[1]));
} else {
map.put(s[0], Integer.parseInt(s[1]));
}
}
if (map.containsValue(5)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
br.close();
}
}3. HashMap 대신 배열 사용
과일이 4 종류로 고정되어있으니 과일에 대한 갯수를 인덱스에 접근하여 저장 가능
요소에 빠르게 접근하고 수정할 때 배열이 더 빠른 것 같지만 아마 데이터가 더 늘어나면 조회하는 데에 시간복잡도가 달라져 배열이 느려질것
(성공)
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 4개의 과일을 인덱스로 매핑
int[] fruitCounts = new int[4];
String[] fruits = {"STRAWBERRY", "BANANA", "LIME", "PLUM"};
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
String[] s = br.readLine().split(" ");
String fruit = s[0];
int count = Integer.parseInt(s[1]);
// 과일 이름에 따라 배열 인덱스에 값 추가
for (int j = 0; j < 4; j++) {
if (fruit.equals(fruits[j])) {
fruitCounts[j] += count;
break;
}
}
}
// 5개가 있는지 확인
for (int count : fruitCounts) {
if (count == 5) {
System.out.println("YES");
br.close();
return;
}
}
System.out.println("NO");
br.close();
}
}공부한 내용정리
- 배열이 더 빠르더라도 아래의 상황일 때에는 HashMap이 더 유리
- 키 기반의 빠른 데이터 검색이 필요할 때
- 데이터의 크기와 위치를 사전에 알 수 없을 때
- 키가 숫자가 아닐 때 - HashMap의 values()는 Collection을 리턴하기에 contains() 사용 가능
Please, Steadily