프로그래머스 전화번호 목록 c++,java (해시)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

 

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

---

알림

2021년 3월 4일, 테스트 케이스가 변경되었습니다. 이로 인해 이전에 통과하던 코드가 더 이상 통과하지 않을 수 있습니다.

 

풀이

문제 분류는 프로그래머스/해시/전화번호 목록이다.

해시를 응용해서 주어진 전화번호 중 임의의 전화번호가 다른 전화번호의 접두사가 될 수 있는지 확인하는 문제이다.

해시에 관한 기본 개념은 이전 포스팅에 있다.

https://ongveloper.tistory.com/71

프로그래머스 완주하지 못한 선수 c++,java (해시,map)

 

무작정 2중 for문으로 접두사를 찾게 된다면, 최대 입력이 1,000,000이기 때문에 시간 초과가 뜬다.

해시 자료구조인 map을 이용하여 전화번호들을 map에 저장해두고,

모든 전화번호에 대해서, 전화번호의 인덱스 0부터 마지막 인덱스를 제외한 부분 문자열인 전화번호가

map에 저장되어 있는지 확인하면 된다.

 

예를 들어 전화번호 목록 중에 전화번호가 1847인 전화번호가 있다고 하자.

이 전화번호의 부분 문자열인 1, 18, 184가 map에 저장되어 있는지 확인하고 있다면 false를 반환하면 된다.

 

예전에 java로 풀었던 문제인데, 그땐 아마 테스트케이스가 이중 for문으로 풀어도 시간 초과가 뜨지 않을 정도의

입력만 주어졌던 것 같다.
그래서 2021/3/4 기준으로 새로운 테스트 케이스가 추가되었으며 기존에 java로 제출했던 코드는 효율성 부분에서

시간 초과로 통과되지 않았다.

 

string을 sort하면 사전 순으로 정렬되는 것을 이용해 인접 원소만 비교하여 접두사를 찾는 방법도

for문을 하나만 사용하기 때문에 이 방법으로도 풀 수 있다.

시간 복잡도는 O(N+N)이다.

다만 문제 분류가 해시로 되어있기 때문에 문제에서 원하는 답은 map을 이용한 풀이일 것이다!

코드(c++/map)

#include <string>
#include <vector>
#include <map>
using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
map<string,int> ma;

    for(int i=0; i<phone_book.size();i++){
        ma[phone_book[i]]=1;
    }
    for(int i=0; i<phone_book.size();i++){
        string phone_number="";
        for(int j=0; j<phone_book[i].length()-1;j++){
            phone_number+=phone_book[i][j];
            if(ma[phone_number]){
                return false;

            }
        }
    }

    return answer;
}

코드(c++/sort)

#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()))
            return false;
    }

    return answer;
}

코드(java/효율성 시간초과)

import java.util.Arrays;
class Solution {
    public boolean solution(String[] phone_book) {
        for(int i=0; i<phone_book.length-1;i++)
        {
            for(int j=i+1; j<phone_book.length;j++)
            {
                if(phone_book[i].startsWith(phone_book[j])==true)
                    return false;
                if(phone_book[j].startsWith(phone_book[i])==true)
                    return false;

            }
        }
            return true;
    }
}