Life Engineering
[프로그래머스] 전화번호 목록 (C++) 본문
https://programmers.co.kr/learn/courses/30/lessons/42577
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
struct {
bool operator()(string &first, string &second){
return first.size() < second.size();
}
} cmp;
bool solution(vector<string> phone_book) {
bool answer = true;
map<string, int> m;
sort(phone_book.begin(), phone_book.end(), cmp);
for (string num: phone_book){
string s="";
for (int i=0; i<num.size(); i++){
s+=num[i];
if (m.find(s)!=m.end())
return false;
}
m[s]=1;
}
return answer;
}
map을 이용하는 문제.
내가 푼 방식은 이렇다.
- 길이 순으로 번호들을 정렬한다.
- 정렬한 list를 순회해 가면서, 한 번호를 (1자리, 2자리,... n자리) 씩 읽어들이고 만약 동일한 문자열이 map 내에 존재한다면(find 함수 이용) false를 리턴하고, 아닐 경우에는 쭉 돌다가 map에 그 문자열을 추가해준다.
다른 분들의 풀이를 보니, unordered map을 이용한다. unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)이다. unordered map에 번호들을 모두 다 넣어준뒤(map[문자열]=1 이런 형태로) , phone_book 리스트를 순회하면서 한 번호를 (1자리, 2자리,... n자리) 씩 읽어들이고, 동일한 문자열이 hashmap 내에 존재한다면 false를 리턴한다.
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 여행경로 (Python3) (0) | 2021.10.17 |
---|---|
[프로그래머스] 전력망을 둘로 나누기 (Python3) (0) | 2021.10.17 |
[BOJ 1197] 최소 스패닝 트리 (Python3) (0) | 2021.10.16 |
[BOJ 17417] 게리맨더링 (C++) (0) | 2021.10.16 |
[BOJ 16637] 괄호 추가하기 (C++) (0) | 2021.10.14 |