뚝딱뚝딱

***정렬을 이용한 c++ 코드가 필요하다면 아래의 블로그를 참고하세요***

2023.10.18 - [CO-TE/challenge] - [프로그래머스] JAVA / c++ LV2 전화번호 목록 / 해시알고리즘, SORT 풀이 (1)

이번에는 해시 알고리즘을 이용한 java 풀이법을 살펴보겠다.

💡 ''해시 알고리즘''??

해시(hash)는 임의의 데이터를 고정된 길이의 숫자나 문자열로 변환하는 과정이다.

HashMap
- 해시를 사용하는 자료 구조의 일종이다.
- HashMap은 키-값 쌍을 저장하고, 이러한 키-값 쌍에 대한 빠른 검색 및 검색을 지원합니다
- 문자열을 가지고, 해당 문자열이 HashMap에 있는지 바로바로 찾아주기 때문에 O(1)의 복잡도를 갖는다.

HashMap을 활용해서 HashMap에 전화번호 목록들을 키-값 쌍으로 저장하는 과정이 필요하다.

HashMap에 있는 값들은 이제 HashMap에서 지원하는 찾기 함수를 통해서 바로바로 찾아 낼 수 있다.

 java / HashMap 사용 

1. 먼저 HashMap을 Map<>을 통해서 생성하자.

• HashMap의 경우 java.util.HashMap에 정의되어 있으므로 import해준다.
• Map의 경우 java.util.Map에 정의되어 있으므로 import해준다.

import java.util.HashMap;
import java.util.Map;

• HashMap은 Map 인터페이스를 구현한 클래스로, Map<>의 객체에 HashMap의 생성자로 생성되도록 할 수 있다.
• 전화번호의 경우 String문자열로 되어 있기 때문에, <String, Integer>를 키-값 쌍으로 갖는 Map을 생성한다.
• 사실상 Integer(값)는 쓸 일이 없고, Map을 활용하기 위한 것이므로, 인덱스를 넣어주겠다.

Map<String, Integer> map = new HashMap<>();

2. HashMap에 phone_book에 있는 값들을 키로, 그리고 인덱스를 값으로 넣어준다.

for(int i=0; i<phone_book.length; i++){
            map.put(phone_book[i], i);
        }

• 여기서 주의할 점..phone_book의 배열 크기는 .length로 얻어 올 수 있다. (c++의 size()와 헷갈리지 말자)
• map에 요소를 넣을 때는 put을 사용하고, 지정해준 키-값 쌍을 인자로 넣어주면 된다.

3. 2중 for문을 통해서 phone_book에 있는 전화번호 각각의 접두어가 HashMap에 있는지를 확인한다.

for(int i=0; i<phone_book.length; i++){
            for(int j=0; j<phone_book[i].length(); j++){
                if(map.containsKey(phone_book[i].substring(0,j))){
                    return false;
                }

• 현재 가리키는 전화번호의 0부터 j번 까지의 문자열이 HashMap의 키를 통해 검색한 결과에 있으면, j번까지의 접두어로 존재하는 전화번호가 있다는 의미이기 때문에, false를 반환하도록 한다.
• 이때 사용하는 map의 함수가 containsKey()로, 검색하고자 하는 값을 인자로 넣어주면 된다.
• 자바에서 String의 substring()함수는 자르고자 하는 문자열의 시작 인덱스와 끝인덱스를 인자로 넣어주고, 만약 인자를 하나만 적는다면 해당 시작부터 끝까지 잘라준다.
• string의 쓰임같은 경우 c++에서와 헷갈리지 않도록 주의한다!!!
• 참고로 문자열의 길이를 반환할 때는 .length()이다! 

이렇게 해시를 이용하면 바로바로 문자열을 map의 함수를 통해 검색할 수 있으므로 효율성에서 높아진다.

전체코드는 아래와 같다.

//해시로 풀이
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        Map<String, Integer> map = new HashMap<>();
        
        for(int i=0; i<phone_book.length; i++){
            map.put(phone_book[i], i);
        }
        
        for(int i=0; i<phone_book.length; i++){
            for(int j=0; j<phone_book[i].length(); j++){
                if(map.containsKey(phone_book[i].substring(0,j))){
                    return false;
                }
                    //substring은 start index부터 end index까지
                    //java에서는 string size가 아니고 배열 크기는 length, 배열 안에서 문자열                        길이는 length() 
            }
        }
        
        
        return answer;
    }
}

***해시알고리즘을 사용한 java 코드가 궁금하다면 아래 블로그를 참고하세요***

2023.10.18 - [CO-TE/challenge] - [프로그래머스] java / c++ LV2 전화번호 목록 / 해시알고리즘, SORT 풀이 (2)

이 문제는 처음에 c++로는 2중 for문을 돌면서, 배열에서 첫번째 전화번호를 기준으로 시작하여, 다른 전화번호들 중 기준이 되는 전화번호보다 길이가 작으면 continue로 건너 뛰고, 그렇지 않으면, substr을 사용해 기준 전화번호 길이만큼 잘라서 비교한 후, 문자열이 동일하면 false를 반환하는 방식으로 접근했다.

이렇게 하면 테스트 케이스는 다 맞지만, 효율성에서 떨어지게 된다. 당연히 무식하게 2중 for문으로 일일이 확인하기 때문에 복잡도가 O(n^2)일 수 밖에 없다.

문제의 카테고리에서 주어진 방식대로 해시 알고리즘을 사용해서 풀면 효율성 문제를 해결할 수 있지만, 사실 해시 알고리즘을 어떻게 사용하는지 몰랐기 때문에, 다른 사람의 코드를 보고 참고하여 먼저 정렬을 이용해 더 쉽게 풀이하였다.

  c++ / sort 함수와 1중 for문으로 풀기 

string 타입의 배열 phone_book을 <algorithm> 헤더에 있는 기본 정렬 함수인 sort()를 통해 정렬한다.

숫자로 표현된 문자열의 경우 사전식으로, 각 문자열의 첫번째 값부터 비교한다. 

첫번째 값들이 다 동일하면 두번째 값을 비교한다.

즉 숫자 그 자체가 큰지가 아니라, 앞에 문자열부터 각 숫자가 작은 것 부터 정렬하는 방식이다

예) "12" "14" "112" 가 있으면, 112, 12, 14 순으로 정렬 된다.

첫번째 1은 모두 같고, 두번째 값이 1,2,4순이기 때문이다.

따라서 이렇게 정렬을 먼저 해 놓으면, 자연스럽게 접두사가 될 확률이 높은 문자열이 앞에 위치하게 되고, 해당 접두사를 가지는 문자열은 무조건 그 문자열의 다음에 정렬될 것이기 때문에, 이 방법은 1중 for문으로도 인접한 문자열에 대해 한번씩만 비교하면 된다. 

해당 코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    sort(phone_book.begin(), phone_book.end());
    
    for(int i=0; i<phone_book.size()-1; i++){
        string s = phone_book[i+1].substr(0, phone_book[i].size());
        if(phone_book[i]==s) {
            answer = false;
            break;
        }
    }
  
    return answer;
}

• sort함수에 배열의 첫번째 요소와, 배열의 마지막 요소를 인자로 넣어주면, 자동으로 정렬된다.
• 1중 for문을 통하여 string 문자열 s에는 현재 접근하는 phone_book의 전화번호 바로 다음에 위치한 전화번호를, 접두사 길이 만큼 잘라 (substr을 사용) 저장한다. 이때 c++에서는 substr(시작 인덱스, 자르고 싶은 만큼의 문자열 크기) 이므로 이에 유의한다. 
• 그래서 현재 접두사 후보의 값과 s가 일치한다면 false를 반환하도록 answer에 설정해준다.

사실상 해시 알고리즘으로 푸는 의도의 문제이긴 하지만, 실제 코테에서는 이 방법을 꼭 사용하라는 명시가 없기 때문에, 위와 같이 효율적인 코드가 생각이 난다면 당연히 사용해도 좋다.

그러나 해시 알고리즘을 이번 기회에 알고 넘어 가기 위해 java를 이용해서 한번 더 풀어보았다.

2탄에서 이어서...