[백준] 5052 전화번호 목록

March 23, 2021 ( last updated : March 23, 2021 )
문자열 알고리즘 algorithm

https://github.com/sneakstarberry/

Abstract

[백준] 5052번 전화번호 목록

[백준] 5052번 전화번호 목록

백준 5052번

알고리즘 유형

풀이 방법

내용을 먼저 이해해 보면 간단히 말해서 목적한 전화번호를 누르다가 목전한 번호가 아닌 전화번호로 전화가 가면 안된다는 것이다.

예) 119 1191
1191에 전화를 거는 것이 목적이라면 119까지 누르면 자동으로 119로 전화가 간다. 이러한 상황이 나타나선 안된다.

위의 예시 그대로 생각을 했다. 목적한 전화번호를 누른다면 하나씩 번호를 누를 것이다. 그렇다면 목적한 전화번호를 하나씩 추가하면서 기존의 전화번호들과 비교해보면 될 것이다.

하지만 이러한 방식에는 오류가있다. 바로 시간초과가 날 것이라는 것이다. 전체 전화번호를 눌러보면서 버튼 하나 누를 때마다 한번 씩 반복문을 돌게 되면 전체 전화번호들의 최대 값은 10000이고 전화번호는 10자리 숫자로 이루어져있다. 먼저 전화번호들을 한번씩 돌면서 번호 하나 씩을 눌러볼 것 이기 때문에 10000*10이다. 하지만 여기서 번호 하나를 누를 때 마다 전화번호들 전체를 탐색해야하기 때문에 10000*10*10000 번이 된다. 최대 10억 정도 되어버리기 때문에 1초라는 시간 안에 풀 수 없다.

여기서 map을 쓰게 되면 시간을 단축할 수 있다. map의 탐색 시간 복잡도는 O(1)이기 때문에 번호 하나를 누를 때 마다 전화번호를 탐색 할 때 1의 비용 밖에 들지 않는다. 따라서 10000*10*1이 되고 시간 내에 풀리게 된다.

map을 사용한 풀이법은 아래 내용을 참조하면 된다.

#include <iostream>
#include <unordered_map>
#include <vector>

#define endl '\n'

using namespace std;

int N;
vector<string> PHONE_BOOK;
unordered_map<string, int> IS_PHONE_NUMBER;

void solve();
void init();

int main() {
  int t;
  cin >> t;

  while (t--) {
    init();
    solve();
    PHONE_BOOK.clear();
    IS_PHONE_NUMBER.clear();
  }
}

void init() {
  cin >> N;

  for (int i = 0; i < N; i++) {
    string tmp;
    cin >> tmp;
    PHONE_BOOK.push_back(tmp);
  }
}

void solve() {
  for (int i = 0; i < N; i++) {
    IS_PHONE_NUMBER[PHONE_BOOK[i]] = 1;
  }
  for (int i = 0; i < N; i++) {
    string phone_number = "";
    for (int j = 0; j < PHONE_BOOK[i].length(); j++) {
      phone_number.push_back(PHONE_BOOK[i][j]);
      if (IS_PHONE_NUMBER[phone_number] && PHONE_BOOK[i] != phone_number) {
        cout << "NO" << endl;
        return;
      }
    }
  }
  cout << "YES" << endl;
  return;
}

Originally published March 23, 2021
Latest update March 23, 2021

Related posts :

{# #}