https://www.acmicpc.net/problem/5052
문제
전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자
- 긴급전화: 911
- 상근: 97 625 999
- 선영: 91 12 54 26
이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.
입력
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.
출력
각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.
9 | 1 | 1 | |||||
9 | 7 | 6 | 2 | 5 | 9 | 9 | 9 |
9 | 1 | 1 | 2 | 5 | 4 | 2 | 6 |
- 긴급전화: 911
- 상근: 97 625 999
- 선영: 91 12 54 26 의 경우에 상근은 선영에게 전화를 걸 수 없다 (전화를 걸면 긴급전화가 걸리기 때문)
91125426의 접두어 -> 911
처음 생각한 방법
->문자열 배열에 911,97625999,91125426을 모두 넣고 이중 for문 돌리면서 두 문자열이 같으면 일관성 X인 경우이므로 시도해봤지만 실패/..
구글링 후 정렬을 사용해야 한다는 사실을 알 수 있었다..!
시간복잡도에 안걸리는 방법->정렬을 사용한다..
기존의 긴급전화,상근,선영을 정렬한다면 (오름차순정렬)
9 | 1 | 1 | |||||
9 | 1 | 1 | 2 | 5 | 4 | 2 | 6 |
9 | 7 | 6 | 2 | 5 | 9 | 9 | 9 |
이렇게 바뀐다.
정렬 후 알수있는 사실은 문자열 A가 문자열 B의 접두사가 된다면 문자열 B는 문자열 바로 A뒤에 온다.
예를 들어 "abbb" , "abbbc", "abbbccd" 의 경우 정렬을 한다면
"abbb"
"abbbc"
"abbbccd" 이런 순으로 오게 되는데 "abbbc"가 "abbb"의 접두사가 된다면 "abbbc"는 "abbb"의 바로 뒤에 온다.
이렇게 정렬을 한 후
911,91125426,97625999를 for문 한번만 돌게 하면 된다.
배열의 i번쨰 문자열과 배열의 i+1 문자열을 비교하는데 오름차순 정렬이 된 후 이므로 배열의 i+1문자열을 i번째 문자열의 크기만큼 비교하면 된다.
새롭게 알게 된 사실: C++에서 문자열의 부분문자열을 추출할떄 substr을 사용하자.
string substr (size_t pos = 0, size_t len = npos) const
시작(pos)지점과 길이를 입력받아서 부분문자열을 리턴한다.
ex) (0~3)까지의 부분문자열을 리턴받고 싶을떄
string str = "Hello_world"
str.substr(0,3)
시간초과 코드
->
정답 코드->
'자료구조' 카테고리의 다른 글
STD::multimap (0) | 2022.03.19 |
---|---|
백준 1755 C++ (0) | 2022.03.19 |
백준 걸그룹 마스터 준석이 C++ (0) | 2022.03.12 |
백준 숫자 카드 2 C++ (0) | 2022.03.09 |
C++ Map사용법 [STL] + 백준 듣보잡 (0) | 2022.03.08 |