Hash

  • 데이터를 다루는 기법 중에 하나
  • 검색과 저장이 아주 빠르게 진행
  • 데이터를 검색할 때 사용할 key와 실제 데이터의 값이 (value가) 한 쌍으로 존재하고, key값이 배열의 인덱스로 변환
  • 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴

완주하지 못한 선수

1차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        
        Arrays.sort(participant);
        Arrays.sort(completion);
        int i;
        
        for ( i=0; i<completion.length; i++){

            if (!participant[i].equals(completion[i])){
                return participant[i];
            }
        }
        
        return participant[i];
    }
}

int i

바깥에 i를 선언하는 이유는 completion의 순서하고 participant순서가 똑같을 때(탈락자가 제일 마지막 일때) 처리를 하려고 바깥에 선언

문제 자체는 맞았지만 Hash를 사용하지 않았기 때문에 해당 문제에 관한 HashMap을 사용한 코드를 분석해보았습니다.

다른사람 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
    }
}

getOrDefault(player, 0)

getOrDefault를 넣어주지 않으면 중복 체크가 되지 않는다.
HashMap의 put은 key가 존재하면 value를 새로운 값으로 바꿔버리기 때문이다.
이미 등록된 동명이인이 있다면 hm.getOrDefault로 인해서 2라는 값이 들어가게 된다.

전화번호부

1차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        
        for(int i = 0; i<phone_book.length - 1; i++) {
        	if(phone_book[i+1].contains(phone_book[i])){
        		return false;
            }
        }   
        return true;
    }
}

문자열 포함여부 관련 함수

구분 설명 포함 미포함
contains 문자열에 검색하고자 하는 문자가 있는지 확인 true false
indexOf 문자열에서 검색하는 문자의 위치를 반환 문자 위치 -1
matches 정규식을 이용하여 문자열을 검색한다. true false

다른사람풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        
        for(int i = 0; i<phone_book.length - 1; i++) {
        	if(phone_book[i+1].startsWith(phone_book[i])){
        		return false;
            }
        }   
        return true;
    }
}

contains() 는 접두사가 아닌 내부의 요소도 비교하기 때문에 위에 답이 결과상으로 맞더라도 틀린답이다.

startsWith()

  • boolean startsWith(String prefix)

  • startsWith() 함수는 대상 문자열이 특정 문자 또는 문자열로 시작하는지 체크하는 함수이다.

  • 해당 문자열로 시작되는지 여부를 확인하고 boolean 에 맞춰 true/false 값을 리턴한다.

위장

1차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.HashMap;
import java.util.Set;

public class Solution {
    public int solution(String[][] clothes) {
        int answer = 1; 
        HashMap<String, Integer> clothesMap = new HashMap<String, Integer>();
        for(int i =0; i<clothes.length; i++){
           clothesMap.put(clothes[i][1], clothesMap.getOrDefault(clothes[i][1], 0)+1);
        }
        Set<String> keySet = clothesMap.keySet();         
        for(String key : keySet) {
        	answer *= clothesMap.get(key)+1; 
        }
        return answer-1;
    }
}

getOrDefault(Object key, V defaultValue)

찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환한다.

Set - 집합

  • 요소는 중복될 수 없다.
  • 순서가 있을 수도 있다.
  • 정렬될 수도 있다.
클래스 특징 성능
HashSet 순서가 필요없는 데이터를 hash table에 저장. Set 중에 가장 성능이 좋음
TreeSet 저장된 데이터의 값에 따라 정렬됨. red-black tree 타입으로 값이 저장. HashSet보다 성능이 느림
LinkedHashSet 연결된 목록 타입으로 구현된 hash table에 데이터 저장. 저장된 순서에 따라 값이 정렬. 셋 중 가장 느림