[GDSC] 알고리즘 스터디 1주차 : 해시(Hash)

▼ What ?

1주차엔 커리큘럼대로 해시에 대해서 공부해보고, 해시와 관련된 알고리즘 문제를 해결한 후 관련 내용에 대해 정리해보려고 한다. 해시는 방학때 공부하기도 했었고 따로 정리도 해놨었기 때문에 해당 글을 보면서 복습하는 시간을 가졌다.

---

▼ 해시 (Hash)

 

해시 (Hash) ?

참고 자료 - [PCCP] 해시 테이블 (Hash table) & 충돌 해결 — Uykm_Note (tistory.com) 

[PCCP] 해시 테이블 (Hash table) & 충돌 해결

 

---

▼ 외톨이 알파벳

 

문제 정보

알파벳 소문자로만 이루어진 어떤 문자열에서, 2회 이상 나타난 알파벳이 2개 이상의 부분으로 나뉘어 있으면 외톨이 알파벳이라고 정의합니다.

문자열 "edeaaabbccd"를 예시로 들어보면,

• a는 2회 이상 나타나지만, 하나의 덩어리로 뭉쳐있으므로 외톨이 알파벳이 아닙니다.
  • "ede(aaa)bbccd"
• b, c도 a와 같은 이유로 외톨이 알파벳이 아닙니다.
• d는 2회 나타나면서, 2개의 부분으로 나뉘어 있으므로 외톨이 알파벳입니다.
  • "e(d)eaaabbcc(d)"
• e도 d와 같은 이유로 외톨이 알파벳입니다.

문자열 "eeddee"를 예시로 들어보면,

• e는 4회 나타나면서, 2개의 부분으로 나뉘어 있으므로 외톨이 알파벳입니다.
  • "(ee)dd(ee)"
• d는 2회 나타나지만, 하나의 덩어리로 뭉쳐있으므로 외톨이 알파벳이 아닙니다.
  • "ee(dd)ee"

문자열 input_string이 주어졌을 때, 외톨이 알파벳들을 알파벳순으로 이어 붙인 문자열을 return 하도록 solution 함수를 완성해주세요. 만약, 외톨이 알파벳이 없다면 문자열 "N"을 return 합니다.

 

PCCP 모의고사 1회 - [PCCP 모의고사 1] 1번 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

제한사항

• 1 ≤ input_string의 길이 ≤ 2,600
• input_string은 알파벳 소문자로만 구성되어 있습니다..

 

입출력 예

 

해결 코드 0

1. HashMap 객체 'map'에 알파벳(key)과 해당 알파벳의 개수(value)를 저장한다.
2. 'map'에서 key값을 하나씩 꺼내 해당 key에 매핑되는 value값이 2개 이상인 경우에 그 알파벳이 "외톨이 알파벳"인지 체크하고, "외톨이 알파벳"이면 StringBuilder 객체 'sb'에 해당 문자를 저장해준다.
3. 그렇게 "외톨이 알파벳" 체크가 끝난 후에, 'sb'가 비어있으면 "N"을 반환해준다.
4. 비어있지 않으면 배열로 변환해서 정렬해준 후에 다시 String 타입으로 변환해서 결과값으로 반환한다.

import java.util.HashMap;
import java.util.Arrays;

class Solution {
    public String solution(String input_string) {
        String answer = "";
        HashMap<Character, Integer> map = new HashMap<>();
        char[] chArr = input_string.toCharArray();
        
        for(char c : chArr) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        
        StringBuilder sb = new StringBuilder();
        for(char key : map.keySet()) {
            int value = map.get(key);
            
            if(value >= 2) {
                boolean isLoner = true;
                
                for(char c : chArr) {
                    if(c == key) {
                        isLoner = false;
                        value--;
                        continue;
                    } else if(c != key && value > 0 && value != map.get(key)) {
                        isLoner = true;
                        break;
                    }
                }
                
                if(isLoner) sb.append(key);
            }
        }
        
        answer = sb.toString();
        
        if(answer.equals("")) return "N";
        
        char[] tmpArr = answer.toCharArray();
        Arrays.sort(tmpArr);
        answer = String.valueOf(tmpArr);
        
        return answer;
    }
}

 

해결 코드 1

• HashMap 객체에 알파벳(key)과 알파벳 개수(value)를 저장하기 위해 문자열을 한 번 순회할 때 "외톨이 알파벳"도 같이 체크해주고, 이중 for문도 없애서 시간복잡도를 낮추고 싶어 리팩토링 해보았다. 

1. 문자열을 앞에서부터 탐색하다가 해당 알파벳이 새롭게(처음 X) 등장하는 횟수를 체크해서 value값으로 저장하는 것이 포인트이다!
2. 첫 번째로 등장한 알파벳은 미리 HashMap 객체 'map'에 value값을 1로 저장해둔다.
3. 그다음 문자열을 두 번째 알파벳부터 탐색하여, 다른 알파벳에서 해당 알파벳으로 바뀔 때마다 해당 알파벳과 매핑되는 key값에 1씩 더해준다
4. 모두 순회하고 나면 'map'의 key값을 하나씩 꺼내 value값이 2 이상, 즉 "외톨이 알파벳"인 key값을 추려내 StringBuilder 객체 'sb'에 저장해준다.
5. 이후는 리팩토링하기 이전 코드와 같다

import java.util.HashMap;
import java.util.Arrays;

class Solution {
    public String solution(String input_string) {
        String answer = "";
        HashMap<Character, Integer> map = new HashMap<>();
        
        map.put(input_string.charAt(0), 1);
        
        for(int i = 1; i < input_string.length(); i++) {
            char current = input_string.charAt(i);
            if(input_string.charAt(i-1) != current) 
                map.put(current, map.getOrDefault(current, 0) + 1);
        }
        
        StringBuilder sb = new StringBuilder();
        
        for(char key : map.keySet()) {
            if(map.get(key) >= 2) sb.append(key);
        }
        
        answer = sb.toString();
        
        if(answer.equals("")) return "N";
        
        char[] tmpArr = answer.toCharArray();
        Arrays.sort(tmpArr);
        answer = String.valueOf(tmpArr);
        
        return answer;
    }
}

 

---

▼ 정리

 

• 첫 코드와 리팩토링한 코드의 차이점은 HashMap의 value값을 어떤 것을 기준(알파벳의 개수, 알파벳이 새롭게 등장한 횟수)으로 할 것인지였던 것 같다.
  
  ➜ 굳이 2회 이상 나타난 알파벳을 따로 체크할 필요가 없었는데, 문제에서 "2회 이상 나타난 알파벳"라는 부분에 시선이 집중돼서 코드가 더 복잡해졌던 것 같다.
  
  
• String 타입과 다른 배열 타입(int[], char[], etc.) 간의 변환은 자주 활용되는 것 같으니 기억해두자 !
  
  
• String 타입의 객체에 무심코 등호 연산자(==)를 사용하기도 했는데, 문자열은 기본형 타입이 아닌 객체임을 잊지 말자 !