programmers : https://programmers.co.kr/learn/courses/30/parts/12077
programmers 해시 level2 전화번호목록 문제입니다.
전체스트링 하나가 다른 스트링의 접두사가 되는 부분이 있는지 확인하는 문제입니다.
******
사실 이 문제는 .. 테스트케이스가 좀 부족한 문제이지 않나 싶습니다.
O(N^2) 코드가 O(N+NlogN) 코드보다 빠르게 정말 더빠르게 해결됨을 확인했습니다.
아마 N^2 의 완탐코드에서 정답이 빨리 찾아지는 테스트케이스만 모여있기 때문이 아닐까 추측해봅니다
******
예를 들어
12 13 124 2 52 라는 값이 있으면
12 가 124의 접두사가 되기 때문에 정답이 false 가 됩니다.
이 문제는 범위가 100만 이기 때문에 사실 N^2 의 복잡도로는 문제가 해결되지 않을줄 알았습니다.
다음은 O(N^2) 코드입니다.
|
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
28
|
#include <string>
#include <vector>
using namespace std;
bool solution(vector<string> phone_book) {
bool answer = true;
for(int i = 0; i<phone_book.size()-1; i++){
for(int j = 0; j<phone_book.size(); j++){
if(phone_book[i].size()>phone_book[j].size() || i==j) continue;
bool temp = true;
for(int k = 0; k<phone_book[i].size(); k++){
if(phone_book[i][k] != phone_book[j][k]){
temp = false;
break;
}
}
if(temp){
answer = false;
break;
}
}
if(!answer) break;
}
return answer;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
그런데 빠른시간내로 통과되더라구요? ??..
하지만 문제를 이런식으로 풀게 되면 분명 TLE를 받게될 경우들이 많아질 것이 분명합니다..
접두사를 좀더 빠르게 찾는 방법이 무엇일까요?
답은 정렬입니다.
위의 12 13 124 2 3 을 정렬하면
12 124 13 2 3 이라는 사전순서의 정렬이 됩니다.
그리고 O(N)으로 문제를 해결하면 됩니다.
접두사가 있는지 없는지는 현재위치와 다음위치만 비교해주면 되기 때문입니다.
다음은 정렬을 이용한 O(N)+O(NlogN) 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#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++)
{
if (phone_book[i] == phone_book[i + 1].substr(0, phone_book[i].size()))
{
answer = false;
break;
}
}
return answer;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm > programmers' 카테고리의 다른 글
| Programmers 라면공장(C++) (0) | 2020.07.02 |
|---|---|
| programmers N으로 표현 (0) | 2020.03.12 |
| programmers H-Index C++ (0) | 2020.03.10 |
| programmers 가장 큰 수 (0) | 2020.03.10 |
| programmers K번째수 (0) | 2020.03.10 |