(c++) 프로그래머스 코딩테스트 연습 - 전화번호 목록

programmers.co.kr/learn/courses/30/lessons/42577

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

[풀이]

모든 원소에 대해 다른 원소들의 접두어인지 확인하는 문제였다. 

길이가 더 짧은 원소의 인덱스값을 따라 같은 인덱스에 같은 값이 있는지 확인하였다.

아래와 같이 for문을 두 번 써서 풀었다가 계속 효율성에서 실패가 나왔다.

 

#include <string>
#include <vector>

using namespace std;

//접두어인지 확인
bool Check(string a, string b) {
	for (int i = 0; i < a.size(); i++) {
		if (a[i] != b[i])
			return true;
	}
	return false;
}

bool solution(vector<string> phone_book) {
	bool answer = true;
	int phone_cnt = phone_book.size();
	for (int i = 0; i < phone_cnt - 1; i++) {
		string a = phone_book[i];
		for (int j = 1; j < phone_cnt; j++) {
			//같은 원소는 비교하지 않음
			if (i == j)
				continue;
			string b = phone_book[j];
			//길이가 더 짧은 원소가 접두어인지 확인
			if (a.size() > b.size()) {
				if (!Check(b, a)) {
					answer = false;
					break;
				}
			}
			else if (!Check(a, b)) {
				answer = false;
				break;
			}
		}
	}
	return answer;
}

질문하기에 어떤 분이 phone_book을 정렬한 상태로 현재 번호가 바로 뒤의 번호의 접두어가 아니면 그 뒤로도 아니므로 패스할 수 있다고 올려주셔서 그대로 풀었더니 통과했다.

 

#include <string>
#include <vector>
#include <algorithm>//sort
#include <iostream>

using namespace std;

//접두어인지 확인
bool Check(string a, string b) {
	for (int i = 0; i < a.size(); i++) {
		if (a[i] != b[i])
			return true;
	}
	return false;
}

bool solution(vector<string> phone_book) {
	bool answer = true;
	int phone_cnt = phone_book.size();
    sort(phone_book.begin(),phone_book.end());
    for(int i=0;i<phone_cnt;i++)
        cout<<phone_book[i]<<' ';
	for (int i = 0; i < phone_cnt - 1; i++) {
		string a=phone_book[i];
        string b=phone_book[i+1];
        if(a.size()<b.size()){
            if(!Check(a,b))
                return false;
        }
        else if(!Check(a,b))
            return false;
	}
	return true;
}