[Programmers] 전화번호 목록

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

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

 

분류에는 해시라고 적혀있지만 해시로 풀지 않았다.

 

접두사의 길이 < 접미사의 길이 라는 조건을 주고 문제에 접근했다.

 

문자열의 길이가 최대 20자이고 전화번호 목록의 최댓값이 100만개이다.

 

시간초과가 안날 거라고 확신했고 for문을 3개 이용해 풀었다.

 

#include <string>
#include <vector>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    bool flag = false;
    
    for(int i=0; i < phone_book.size() - 1; i++) {
        string head = phone_book[i];
        string tail;
        for(int j=i+1; j < phone_book.size(); j++) {
            if(head.length() > phone_book[j].length()) {
                tail = head;
                head = phone_book[j];
            }
            else tail = phone_book[j];
            
            flag = false;
            for(int k=0; k<head.length(); k++) {
                if(head[k] != tail[k]) {
                    flag = true;
                    break;
                }
                
            }
            if(!flag) {
                answer = false;
                break;
            }
        }
        if(!flag) break;
    }
    
    
    return answer;
}