programmers 전화번호 목록
알고리즘 수업시간에 다룬 내용입니다. 이 문제는 크게 3가지 방법(정렬, 해시, 트라이)으로 풀 수 있는데요. 트라이를 제외한 정렬, 해시로 구현한 방법을 살펴보겠습니다.
소스코드에 앞서 알고리즘 문제를 풀 때는 문제가 요구하는 바를 정확히 파악하고 문제를 단순하게 하는 작업이 필요한 것 같습니다. 이 문제의 경우 문제 상황 자체는 복잡하지만 결국 요구하는 것은 '특정 문자열이 다른 문자열의 substring으로 들어있는 것이 있나' 입니다. 이렇게 단순화하면 방향이 좀 더 명확하게 보일 수 있습니다.
정렬
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
List<String> phoneBook = new ArrayList<>(Arrays.asList(phone_book));
Collections.sort(phoneBook);
for (int i = 1; i < phoneBook.size(); i++) {
String back = phoneBook.get(i);
if(phoneBook.get(i).length() > phoneBook.get(i-1).length()) {
back = phoneBook.get(i).substring(0, phoneBook.get(i-1).length());
}
if(back.equals(phoneBook.get(i-1))){
answer = false;
}
}
return answer;
}
}
정렬에서 이용하는 것은 우선 받은 문자열 배열을 정렬한다음 앞에 문자열이 뒤의 문자열의 substring인가라는 것입니다. 비교는 if(back.equals(phoneBook.get(i-1)))
로 표현될 있습니다. 다만 주의할 점은 앞의 문자열이 뒤의 문자열보다 긴 경우입니다. 예를들어 [12, 134, 242424, 25]가 있을 때 무조건 뒤의 경우가 앞의 경우보다 길다고 생각하면 substring()
을 사용할 때 오류가 발생합니다. 잘라라고 하는 길이보다 실제 길이가 작기 때문이죠. 이 경우 if
문을 통해 뒤의 길이가 앞의 길이보다 긴 경우에만 자르도록 따로 조건을 만듭니다.
해시
public class Main {
static Set<String> hash = new HashSet<>();
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int testCount = scan.nextInt();
for (int i = 0; i < testCount; i++) {
int phoneNumCount = scan.nextInt();
for (int j = 0; j < phoneNumCount; j++) {
hash.add(scan.next());
}
try {
phoneNumCheck();
System.out.println("YES");
} catch(IllegalArgumentException e) {
System.out.println("NO");
}
hash.clear();
}
}
private static void phoneNumCheck() {
for (String s : hash.toArray(new String[hash.size()])) {
String temp = s;
hash.remove(s);
for (int i = 0; i < temp.length(); i++) {
if(hash.contains(temp.substring(0, i + 1))){
throw new IllegalArgumentException();
}
}
hash.add(temp);
}
}
해시의 경우 Baekjoon Online Judge에서 풀어서 정렬로 풀때보다 소스코드가 더 깁니다. 왜냐하면 백준에서는 사용자가 직접 테스트 케이스를 입력하고 그에 대한 결과를 출력하는 구조이기 때문입니다.
해시의 경우 아이디어는 HashSet
에 입력받은 문자열을 모두 넣고 하나씩 꺼내어 각각 문자열의 substring이 HashSet
안에 있는지 조사하여 만약 있으면 "NO" 반환하는 것입니다. 여기에서 주의할 점이 있습니다. 자신을 찾는 경우를 제외하기 위해 hash에서 꺼낸 수를 remove()
를 사용하였다가 나중에 조사를 끝내고 add()
를 하는데요. 이렇게 반복문 돌릴 때 HashSet
으로 돌리면 안된다는 것입니다. 반복문 돌리는 중에 remove()
가 발생하면 오류가 뜨는데 그 이유는 반복문을 돌릴 때 순서대로 돌리는데 없애버리면 Index에 변화가 생겨 제대로 반복문을 돌리는데 어려움이 발생하기 때문입니다. 따라서 hash를 배열로 만들어(hash.toArray(new String[hash.size()])
) 이 배열의 순서대로 꺼내야 합니다.
트라이
트라이(Trie)는 이게 어떤 개념인지만 잠깐 알아보도록 하겠습니다. 예를들어 [12, 123, 1235, 567, 88]과 같은 전화번호가 있다고 생각해보겠습니다. 트라이의 경우 다음과 같이 나타낼 수 있습니다.
각 수를 한 자리씩 매달듯이 붙입니다. '12'의 경우 1을 먼저 매달고 1다음에 2를 매답니다. '123'의 경우는 기존 '1'이 있으니 거기로 가고 '2'도 있으니 갔다가 '3'은 없으니 새로 매답니다. 이런 식으로 구성하면 그림과 같이 표현될 수 있겠죠. 그럼 여기서 어떻게 substring을 판별하냐? 라고 물을 수 있을텐데요. 판별은 다음과 같습니다.
애초 각 수를 매달 때 마지막 수가 있는 곳, 그러니까 '12'의 2, '123'의 '3', '1235'의 '5'에 그 수가 종료되었다는 것을 표시해둡니다. 그림으로 표현할 때는 빨간색으로 표시해두었습니다. 그리고 매달러갈 때 종료시점을 만나면 기존에 이러한 substring이 있었다는 뜻이기 때문에 같은 substring이 존재한다고 판별하는 것입니다. 따라서 사실은 '전화번호 목록'을 풀 때 위의 그림이 다 그려질 필요도 없이 빨간색 '12'가 매달아지고 '123'에서 '12' 지나갈 떄 종료시점 표시를 보았으니 그 때 "NO"가 반환되어 종료되는 것입니다.
트라이의 경우 많은 문제에서 유용하게 사용될 수 있을 것 같은데요. 단점은 자바의 경우 직접 구현해야한다는 것입니다. 좀 더 트라이의 필요성을 절실히 느끼게 될 때 한번 구현해보고 싶네요.
'Algorithm > problem solving' 카테고리의 다른 글
Today's Algorithm(2018-10-25) (0) | 2018.10.25 |
---|---|
Today's Algorithm(2018-10-22) (0) | 2018.10.22 |
Today's Algorithm(2018-10-16) (0) | 2018.10.17 |
Today's Algorithm(2018-10-15) (0) | 2018.10.15 |
Today's Algorithm(2018-10-12) (0) | 2018.10.12 |