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

문제

출처 : www.acmicpc.net/problem/5052

5052번: 전화번호 목록

 

 

전화번호 목록을 입력받았을때, 그 목록이 일관성이 있나 없나 구하는 문제다.

예를들어

 

A = 911

B = 9123

C = 91 1234

를 입력받았을때, C에게 전화할려고 전화번호를 누르면 911을 누르는순간 A에게 전화가 가므로 일관성이없는 목록이다.

풀이

Trie알고리즘을 배우고 풀었는데, 새로운 알고리즘이라기 보다 구조체를 응용하는 느낌이였다.

 

구조체를 선언하고 그 구조체에 자판 배열을 할당한다. (자판은 0~9까지 있으니 배열의 크기는 10이상으로 잡아야한다.)

 

struct Number{

    int rock;

    int num;

    struct Number *next_number[15];

};

이런식으로...

(어떤 번호가 123 이라면, 1주솟값에 선언된 next_number[2]에 1에 연결된 2의 주솟값이 들어갈것이다.)

rock은 0으로 초기화 되어있는데, rock이 -1이라면 해당 숫자가 어떤 번호의 마지막 이라는것 이다.

num은 해당 주솟값에 저장된 숫자이다.

 

주솟값으로 전화번호목록을 만듦과 동시에 탐색을 하는데, 입력하는 동안 자기가 저장될 주솟값이 어떤 번호의 마지막 주솟값 이라면, 일관성이 없다고 판단해준다.

예를들어

911 이 저장되어있고

91 1345를 저장해야 한다면,

91 1345의 세번째 1을 저장하려고 할때 일관성이 없다고 판단한다. 

 

이때, 반례를 없앨려면 저장된 입력을 sort시켜줘야한다. 

sort없이 

123 45 67

123 45

를 입력한다면, 프로그램은 일관성이 있다고 판단한다. 왜냐하면, 두번째 숫자의 마지막인 5를 입력할때 그 주솟값이 다른 번호의 마지막이 아니기 때문이다.

이를 해결하기위해 길이가 가장 짧고, 번호가 가장 작은숫자부터 입력을 해줘야한다. (sort 사용이유)

 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/5052%20%EC%A0%84%ED%99%94%EB%B2%88%ED%98%B8%20%EB%AA%A9%EB%A1%9D/main.cpp

devxb/JJUNalgo