해시
다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑하는 것
데이터 값을 이용해 위치를 찾을 수 있다.
저장하거나 찾고자 하는 위치를 빠른 속도로 찾을수 있다.
HashMap
// 1. 선언
HashMap<String, Integer> hm = new HashMap<>();
// 2. key-value 넣기, 키 값 수정 가능
hm.put("java", 0);
// 3. 키로 값 가져오기
hm.get("java");
// 4. containsKey()로 존재유무 확인
if (!hm.containsKey("java")) hm.put("java", 1);
// 5. 특정 키가 없으면 값 설정, 있으면 기존 값 가져오는 함수
hm.put("java", hm.getOrDefault("java", 3);
// java 키가 없으면 java 키값 3으로 설정, java 키가 있으면
// java 키의 값을 가져옴
// 6. keySet() 함수로 맵 순회
for(String key : hm.KeySet()) {
hm.get(key);
}
//7. entrySet() 으로 키, 밸류 값 모두 사용해서 순회
//import java.util.Map.Entry 필요
for (Entry<String,Integer> e : hm.entrySet()){
e.getKey();
e.getValue();
}
//8. remove(key) 로 값 삭제
hm.remove("java");해시테이블은 값 접근, 삽입, 삭제, contains 모두 O(1)의 시간복잡도를 갖는다!!
문제
문제1
내 풀이
import java.util.HashMap;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
//HashMap을 이용하면 즉시 저장하고나 찾고자 하는 위치를 참조할 수 있어서 빠르다
HashMap<String,Integer> hm = new HashMap<>();
//완주자 해쉬맵 생성
for (String c : completion){
if (hm.containsKey(c)){
hm.put(c,hm.get(c)+1);
}else{
hm.put(c,1);
}
}
for (String p : participant){
if (hm.containsKey(p)){
if (hm.get(p)==0){
answer = p;
break;
} else {
hm.put(p,hm.get(p)-1);
}
} else {
answer = p;
}
}
return answer;
}
}처음에는 배열로 for문을 돌리면서 풀려고 했는데 효율성 테스트에서 떨어졌다.
찾아보니 HashMap은 값에 접근할 때 빠르게 접근 가능하다. (다른 자료구조는 선형시간이 걸림)
그래서 HashMap을 사용하는 방식으로 수정하자 통과했다.
참고할 사항 , 실수했던 것
- 탬플릿 객체 만들 때 Wrapper 클래스로 만들어야 함
- containsKey(key)로 키 존재 여부 확인
- remove(key)로 해당 키 삭제
- put(value)로 값을 넣는 것 뿐만 아니라 수정도 가능
다른 사람 풀이
import java.util.HashMap;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
HashMap<String, Integer> hm = new HashMap<>();
for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
for (String player : completion) hm.put(player, hm.get(player) - 1);
for (String key : hm.keySet()) {
if (hm.get(key) != 0){
answer = key;
}
}
return answer;
}
}HashMap 함수인 getOrDefault를 잘 활용했다.
getOrDefault(key,defaultValue)는 key에 해당하는 value 값이 존재하면 값을 가져오고 키 값이 없으면 defaultValue로 value 값을 설정한다.
또한 HashMap을 순회하기 위해 hm.keySet()을 활용했다. (키값을 이용해 HashMap 순회)
하지만 keySet()을 하고 나서 해당 키의 value 값을 알기 위해 for문 내에서 get(key)를 호출하고 있다. 이러면 비효율적이기 때문에 entrySet을 사용하는게 더 바람직하다.
import java.util.HashMap;
import java.util.Map.Entry;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
//HashMap을 이용하면 즉시 저장하고나 찾고자 하는 위치를 참조할 수 있어서 빠르다
HashMap<String,Integer> hm = new HashMap<>();
for (String s : participant){
//getOrDefault를 이용, 키값이 있으면 기존값+1, 없으면 0으로 세팅
hm.put(s,hm.getOrDefault(s,0)+1);
}
for (String s : completion){
//완주했으면 -1 해줌 (동명이인도 있을 수 있어서 이렇게 하는게 좋음)
hm.put(s,hm.get(s)-1);
}
for (Entry<String,Integer> e : hm.entrySet()){
if (e.getValue()!=0){
answer = e.getKey();
}
}Entry는 java.util.Map.Entry를 import 해줘야 사용가능하다.
entrySet()으로 HashMap에서 Entry 객체를 얻을 수 있다.
for문을 이용해 각 Entry에 대해 반복한다.
Entry.getValue()나 Entry.getKey()로 value나 key값을 참조할 수 있다.
문제2
내 풀이
import java.util.HashMap;
class Solution {
public int solution(int[] nums) {
int answer = 0;
int length = nums.length;
//해시맵 <포켓몬 종류,수> hm 초기화
HashMap<Integer,Integer> hm = new HashMap<>();
for (int pkm : nums){
//이미 있으면 1을 더하고 없으면 1로 설정
hm.put(pkm,hm.getOrDefault(pkm,0)+1);
}
//해시맵의 크기 = 포켓몬의 종류 (최소 1마리씩은 있음)
int size = hm.size();
//내가 골라야 하는 포켓몬의 수
int select = nums.length/2;
if (select<=size){answer = select;}
else {
answer = size;
}
return answer;
}
}내 풀이이고 getOrDefault를 사용하면 쉽게 풀 수 있다.
getOrDefault(key,value)는 해시맵에 key에 해당하는 키값이 있으면 그 값을 반환하고 없으면 put(key,value)와 같이 작동한다.
이 점을 이용해 hm.put(key,getOrDefault(key,1)+1)과 같이 코드를 작성했다.
key값이 있으면 키값을 가져와서 1을 더한다.
키값이 없으면 0으로 설정하고 1을 더해서 1로 설정한다.
문제 1과 getOrDefault의 활용방식이 비슷하다.
문제3
내 풀이
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
int length = phone_book.length;
int ilength = 0;
int jlength = 0;
String iString;
String jString;
for (int i=0;i<length;i++){
iString = phone_book[i];
ilength = iString.length();
for (int j=0;j<length;j++){
jString = phone_book[j];
jlength = jString.length();
if (ilength>=jlength){
continue;
}
if (jString.substring(0,ilength).equals(iString)){
answer = false;
}
}
}
return answer;
}
}테스트 케이스에 대해 모두 정답은 받았지만 효율성 면에서 탈락했다.
다른 풀이
import java.util.Arrays;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
Arrays.sort(phone_book);
for (int i=0; i<phone_book.length-1;i++){
if (phone_book[i+1].startsWith(phone_book[i])){
answer = false;
break;
}
}
return answer;
}
}import java.util.Arrays;를 해주고
Arrays.sort()를 이용해서 사전순으로 문자열을 정렬할 수 있다.
사전순으로 문자열을 정렬하면 "9" 8888" 를 정렬하면 9의 맨 앞자리가 사전순으로 8보다 커서 "8888" "9" 로 정렬된다.
따라서 만약 어떤 문자가 앞 문자의 접두어라면 나란히 정렬된다
"99" "11" "1112" 이렇게 정렬된다.
따라서 뒤의 것이랑만 비교하면 된다.
또한 stratsWith를 사용했다.
문제4
내 풀이
import java.util.HashMap;
import java.util.Map.Entry;
class Solution {
public int solution(String[][] clothes) {
int answer = 0;
HashMap<String,Integer> hm = new HashMap<>();
for (String[] row : clothes){
hm.put(row[1],hm.getOrDefault(row[1],1)+1);
}
int mul = 1;
for (Entry<String,Integer> e : hm.entrySet()){
mul*=e.getValue();
answer = mul-1;
}
return answer;
}
}HashMap으로 String은 옷의 종류 , Integer는 개수로 만들었다.
getOrDefault로 기본값 1 , 값 있을 경우 1을 더해줘서 값을 셌다.
기본값을 1로 한 이유는 해당 종류의 옷을 안입는 것까지 1을 더해서 곱해야 하기 때문에 기본값을 1로 했다
그리고 옷의 종류의 개수를 곱한 후 하나도 안입는 경우 1을 빼서 계산했다.
문제5
문제 링크
문제가 별로임 안풀래
