이번 문제는 접두어 문제였습니다.
딱 생각난 아이디어가 이번에도 sort..여서 해시와는 거리가 좀 있습니다만 모로가도 서울만 가면 된다는 마인드(?)로 진행해보도록 하겠습니다.
0. 문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
- 구조대 : 119
- 박준영 : 97 674 223
- 지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
0.0. 제한 사항
- phone_book의 길이는 1 이상 1,000,000 이하입니다.
- 각 전화번호의 길이는 1 이상 20 이하입니다.
0.1. 입출력 예제
| phone_book | return |
| [119, 97674223, 1195524421] | false |
| [123,456,789] | true |
| [12,123,1235,567,88] | false |
0.2. 입출력 예 설명
입출력 예 #1
앞에서 설명한 예와 같습니다.
입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.
입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.
1. 풀이 과정
또 다시 sort를 사용했습니다. 이러면 안되는데 하면서도 강력한 유혹입니다 ㅋㅋㅋㅋ
먼저 phone_book을 sort하고, 앞과 뒤를 비교합니다.
만약 뒤의 길이가 더 짧다면 당연히 둘은 관계가 없을 것이고,
앞과 뒤를 비교했을 때 뒤가 앞을 포함하는 경우 false가 됩니다.
그렇기 때문에 for문을 통해 앞 문자열과 뒷 문자열을 비교해줍니다.
하나라도 접두어에 해당이 되는 순간 answer를 false로 만들고 return합니다.
비교를 할 때 앞에꺼랑 비교하기 떄문에 for문을 돌릴 때 조건식에 phone_book의 size가 아닌 size-1을 넣어줘야 잘못된 메모리를 불러오지 않을 수 있습니다! 주의하세요!!
2. 소스 코드
#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());
int size = phone_book.size();
for (int i = 0; i < size-1; ++i){ // size가 아니라 size-1임에 주의!!
for (int j = 0; j < phone_book[i].size(); ++j){
if(phone_book[i][j] != phone_book[i+1][j])
break;
if (j == phone_book[i].size()-1)
answer = false;
}
if (answer == false)
break;
}
return answer;
}
3. 후기
분명 이중for문을 사용해서 효율성이 꽉이겠거니 했는데 운이 좋게 효율성테스트에서 걸리지 않았습니다.
이렇게 불안에 떨기 싫다면 map이나 set에 더 익숙해 질 필요가 있어 보입니다 ㅋㅋㅋㅋㅋ
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
최근댓글