본문 바로가기
IT/Algorithm

해시 (Hash) - 전화번호 목록

by 신인용 2020. 2. 20.
반응형

전화번호 목록

 

 

문제 출저 - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/42577

 

 

 

 - 제한사항 분석

1. phone_book의 길이는 1 이상 1,000,000 이하입니다.

2. 각 전화번호의 길이는 1 이상 20 이하입니다.

  => 문제의 크기를 나타냅니다.

 

 

 

 

 

 - 이 문제에서 원하는 것은?

 phone_book의 각 요소들의 번호에 대한 를 기록하고 저장하는 구조 !!

=> 이름(Key), 이름에 대한 수(Value) 로 key value 쌍을 만들어야 하는데, key가 string이고 value는 int입니다.

   이렇게 정수 인덱스 말고 문자열 같은 다른 타입으로 찾아갈 수 있는 구조가 바로 해시입니다.

   (완주하지 못한 선수와 거의 동일합니다)

 

 

 

 

 

 - 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <string>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
bool solution(vector<string> phone_book) {
    bool answer = true;
    string str = "";
    unordered_map<stringint> d;
    
    for(auto& i : phone_book){
        str = "";
        for(int j=0; j<i.size(); j++){
            str += i[j];
            d[str]++;
        }
    }
    
    for(auto& i : phone_book){
        if(d[i] > 1){
            answer = false;
            break;
        }
    }
    return answer;
}
cs

 phone_book의 각 요소들을 불러와, 한 글자씩 붙여가면서 이 글자(key)에 대한 수(value)를 1씩 더해주었습니다. 마지막에 phone_book의 번호에 대한 수를 검사해 2이상이면, 다른 번호의 접두어가 된 의미이기 때문에 false를 return하였습니다.

 

ex)

phone_book = ["119", "97674223", "1195524421"]

 phone_book의 첫 번째 요소를 불러,

d["1"]++;

d["11"]++;

d["119"]++;

 두 번째 요소를 불러,

d["9"]++;

d["97"]++;

d["976"]++;

d["9767"]++;

.....

d["97674223"]++;

 세 번째 요소를 불러,

d["1"]++;

d["11"]++;

d["119"]++;

d["1195"]++;

...

d["1195524421"]++;

 

 이제 phone_book의 각 번호에 대한 value가 매핑되었습니다.

d["119"] = 2

d["97674223"] = 1

d["1195524421"] = 1

 

 마지막에 phone_book의 각 요소들의 value를 조사해, 1 초과이면 false를 리턴해줍니다.

 

 

반응형

'IT > Algorithm' 카테고리의 다른 글

선형 자료 구조 (동적 배열, 연결 리스트)  (0) 2020.08.17
탐욕법 - 도시락 데우기  (0) 2020.08.17
분할 정복 - 쿼드 트리 뒤집기  (0) 2020.08.05
해시 (Hash) - 완주하지 못한 선수  (0) 2020.02.20
해시 (Hash)  (0) 2020.02.18

댓글