전화번호 목록
문제 출저 - 프로그래머스
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<string, int> 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 |
댓글