본문 바로가기

별걸다하는 IT/알고리즘 문제풀이

[프로그래머스 레벨2] 전화번호 목록 문제 풀이

[프로그래머스 알고리즘 Level 2]

오늘은 프로그래머스 코딩테스트 연습에 있는 Level 2 전화번호 목록 문제를 풀이해볼게요.

 

전화번호 목록

문제

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

 

구조대: 119

박준영: 97 674 223

지영석: 11 9552 4421

 

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

 

제한사항

phone_book의 길이는 1 이상 1,000,000이하입니다.

각 전화번호의 길이는 1 이상 20 이하입니다.

 

입출력 예제

phone_book return
["119", "97674223", "1195524421"] false
["123","456","789"] true
["12","123","1235","567","88"] false

 

기본 형태:

[Java]

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        return answer;
    }
}

[C++]

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

bool solution(vector<string> phone_book) {
    bool answer = true;
    return answer;
}

 

풀이

문제는 이해하기 어렵지 않아요 ㅎㅎ 아무래도 level 2라 그런가..

일단 어떤 번호가 다른 번호에 접두어가 되는지 확인하려면 전화번호목록을 확인해야하니까 O(N)이상 걸리겠네요.

어차피 각 전화번호의 길이가 20개 이하라 반복문을 두 번 돌려도 큰 시간을 차지할거같지는 않고..?
사전식처럼 앞만 보고 비교하는거라 정렬로 풀어도 될 것 같은데...?

해시 문제로 알고리즘이 분류되어 있지만 저번 문제처럼 해시로 풀 필요는 없는 문제같아요 ㅎㅎ

 

[C++]

오늘은 C++부터 ~~

사실 반복이 많이 되는게 좋은 건 아니지만 단순 반복문만큼 생각하기 쉬운 것은 없죠~ 단순반복문부터

최대 O(N^2)이 걸릴 수 있는 코드입니다.

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

bool solution(vector<string> phone_book)
{
    bool answer = true;
    for(string s1: phone_book){
        for(string s2: phone_book){
            if(s1==s2)
                continue;
            if(s1.length()>s2.length()){
                if(s2==s1.substr(0, s2.length()))
                    return false;
            }
        }
    }
    return answer;
}

반복문에서 s2가 작을 때만 비교를 한 것은 어차피 두 번 전체를 반복하기 때문에

s1에서 s2가 나와서 결국 그 string이 클 때도 비교를 해주기 때문입니다.

즉 s2가 "lion"이라고 하면 결국 같은 목록에서 차례대로 뽑는거기 때문에 s1이 "lion"일 때도 오기 때문임! 이해됐나요?ㅎㅎ

그래도 시간을 줄이고 싶다!! 정렬을 사용할 수 있겠네요 ㅎ 알고리즘 헤더 까먹지 말고 붙여줍시다.

#include <vector>
#include <string>
#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]

자바는 StartsWith라는 메서드가 있어서 좀 더 비교하기가 수월합니다. 

C++의 이중 for문을 C++의 substr대신에 StartsWith를 써봅시다. (물론 substring써도 됩니당)

이번에는 이중 반복의 시작을 i+1로 해서 지나왔던 것은 생략하는 대신, 두 경우 모두 비교해줬어요

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])) 
                    return false;
                if(phone_book[j].startsWith(phone_book[i])) 
                    return false;
            }
        }
        return true;
    }
}

정렬 후 그 바로 다음 것과 비교하기~!

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