프로그래머스 - 전화번호 목록(Level 2)/Wanna Be 컴잘알

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

코딩테스트 연습 - 전화번호 목록 | 프로그래머스

 

-문제-

 

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

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

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

 

-접근법-

 

불필요한 반복횟수를 줄이기 위해서 vector <string> phone_book에 있는 문자열들을 문자열의 길이 기준 오름차순으로 정렬하였다. 정렬하는 방법은 sort함수에 새로운 정렬기준인 bool compare(string a, string b)를 만들어주었고 정렬을 한 뒤에 반복문을 이용하여 접두사체크를 순차적으로 진행해 주었다.

 

-코드-

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

using namespace std;

bool compare(string a, string b) { //길이기준 오름차순
	if (a.length() < b.length()) {
		return true;
	}
	return false;
}

bool strcheck(string cur, string next) { //접두사 체크
	for (int i = 0; i < cur.length(); i++) {
		if (cur[i] != next[i]) {
			return true;
		}
	}
	return false;
}

bool solution(vector<string> phone_book) {
	bool answer = true;
	sort(phone_book.begin(), phone_book.end(), compare);
	
	for (int i = 0; i < phone_book.size()-1; i++) {
		
		string curstr = phone_book[i];
		for (int k = i+1; k < phone_book.size(); k++) {
			if (!strcheck(curstr, phone_book[k])) {
				answer = false;
				return answer;
			}
		}
	}

	return answer;
}