[프로그래머스] 전화번호 목록(C++)

[Level2, 해시]

문제 설명

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

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

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

제한 사항

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

---

 

1차 시도

#include <string>
#include <vector>
#include <iostream>
#include <cstring>

using namespace std;

bool solution(vector<string> phone_book)
{
  bool answer = true;
  for (int i = 0; i < phone_book.size(); i++) {
    for (int j = i + 1; j < phone_book.size(); j++) {
      if (phone_book[i].length() < phone_book[j].length()) {
        if (strncmp(phone_book[i].c_str(), phone_book[j].c_str(), phone_book[i].length()) == 0) {
          answer = false;
          break;
        }
      }
    }
    if (answer == false)
      break;
  }
  return answer;
}

결과

생각이 안나서 일단 for문으로 무작정 다 돌려봤다.

효율성테스트는 이중 for문을 쓴 이상 어차피 안될거라고 생각했는데 정확도에서도 떨어진 걸 보니 뭔가 로직에 문제가 있는 건가 싶었다.

해쉬를 쓰라는 걸 보니 해쉬를 써봐야 할 것 같다.

 

그런데 map으로 해도 어떻게 해야할지 잘 감이 오진 않는다.

전화번호를 key로 해두면, 결국 모든 key값을 서로 비교해야 하는건데, for문을 돌리는것과 큰 차이 없을 것 같다.(속도는 빠를 수도 있지만,,, 로직상,,?)

for문에서 정확도 틀렸던 부분의 반례를 찾았다. 위 예시처럼 긴 게 먼저 나올 경우, 즉 정렬이 안되어있을 때 틀리게 나온다.

#include <string>
#include <vector>
#include <iostream>
#include <cstring>

using namespace std;

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

  for (int i = 0; i < phone_book.size(); i++) {
    for (int j = 0; j < phone_book.size(); j++) {
      if (phone_book[i].length() < phone_book[j].length()) {
        if (strncmp(phone_book[i].c_str(), phone_book[j].c_str(), phone_book[i].length()) == 0) {
          answer = false;
          break;
        }
      }
    }
    if (answer == false)
      break;
  }

  return answer;
}

안쪽 for문의 시작 조건을 i+1 이 아닌 0으로 해주니 정확도는 다 맞았는데, 효율성 테스트 3, 4에서 실패했다.

 

전화번호 목록의 길이의 최대가 100만이니, 100만 * 100만 번 하면 1조라서,,,

 

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

using namespace std;

bool comp(string a, string b)
{
  if (a.size() == b.size())
    return a < b;
  return a.size() < b.size();
}

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

  std::sort(phone_book.begin(), phone_book.end(), comp);

  for (int i = 0; i < phone_book.size(); i++) {
    for (int j = i + 1; j < phone_book.size(); j++) {
      if (phone_book[i].length() < phone_book[j].length()) {
        if (strncmp(phone_book[i].c_str(), phone_book[j].c_str(), phone_book[i].length()) == 0) {
          answer = false;
          break;
        }
      }
    }
    if (answer == false)
      break;
  }
  return answer;
}

나름 정렬을 시킨 다음에 했는데도 시간 초과가 떠버렸다....

 

---

 

 

스터디하면서 풀이를 알았는데, 그냥 내가 C++의 정렬에 대해서 잘 모르고 있었다,

C++의 정렬을 그대로 사용하면 굳이 sort의 정렬 함수를 따로 작성하지 않아도 됐다.

 

정답 풀이

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

using namespace std;

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

    sort(phone_book.begin(), phone_book.end());
    
    for (int i = 0; i + 1 < phone_book.size(); i++)
    {
        if (phone_book[i] == phone_book[i + 1].substr(0, phone_book[i].size()))
            return (false);
    }
    return answer;
}