[Java] 전화번호 목록 Lv2
전화번호 목록
문제 프로그래머스 FAQ 내용을 보니 카카오나 기업의 문제들은 저작권이 있으니 풀이를
github나 개인블로그에 올리지 말라고 되어 있어서 링크로 대체합니다.
출처: Programmers
전화번호 목록
문제의 이해
Lv2부터는 은근히 어려운 문제들이 많아서 문제를 이해하는 것 부터가 점점 머리 아파지는 것 같다. 그래도 이 문제는 어느정도 이해는 하기 쉬웠다. 주어진 문자열 배열에서 어떤 한 문자열 배열이 다른 문자열의 접두사일 때 false를 반환하고 모든 문자열을 검사했는데 접두사가 아니면 true를 반환한다. 처음에는 문제를 보고 String.contains 를 쓰면 쉽겠구나 하고 도전했다가 다양한 문제에 직면을 했다. 첫번째는 contains는 같은 문자열을 찾는 거지 접두어(내가 찾는 문자열이 제일 왼쪽에 존재하는지)는 찾을 수 없었고 두번째는 하나의 문자열이 전체 문자열을 검색하기 때문에 자기 자신과 만날 수도 있는데 자기 자신을 만나면 무조건 false를 리턴하기 때문에 그 부분을 체크 해줘야했고 세번째는 까먹었다.
내가 생각한 풀이 방법
- 아마도 이중 반복문으로 무식하게 풀면 효율성에서 답이 없을거라는 생각에 2차원 ArrayList로 첫번째 숫자를 기준으로 10개의 list로 관리해서 한번 전체 순회를 할때 나온 문자열의 첫 숫자가 1이면 1을 모아놓은 list로 가서 그 부분만 찾도록 했다.
- 그리고 모아놓은 리스트들을 정렬함으로써 최대한 빠르게 false를 찾을 수 있도록 했다.
- 그리고 비교하는 부분에서 contains를 이용해서 풀었는데 답이 틀리게 나와서 내가 간과한 조건이 무엇인지 생각했는데 2가지였다.
- contains는 접두사인지(맨 처음에 동일한 부분이 있는지) 알수 없으니 indexOf를 이용해서 해당 문자열을 제일 처음 발견하는 부분이 0인지 추가로 확인했고, 다른 하나는 자기자신과의 비교는 무조건 false를 리턴하므로 자기 자신일때는 비교하지 않게 코드를 수정했다.
풀이
첫 번째 풀이
여러가지 조건을 추가한 결과 정확성은 통과했지만 효율성 3,4 번을 통과할 수 없었다. 2중 for문이긴 하지만 그래도 최대한 map 비슷하게 사용하려고 했고 배열을 숫자별로 나눠놓아서 효율성이 나올지도 모른다고 생각했는데 효율성은 처참히 실패했다. 다시 짜면 되지만 어떤 방식으로 짜야할지 내 머리속으로 떠오르지가 않았다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.ArrayList;
import java.util.Comparator;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
ArrayList<String>[] arr = new ArrayList[10];
int firstValue = 0;
for(int i=0; i<10;i++) {
arr[i]=new ArrayList<String>();
}
for(int i = 0; i < phone_book.length; i++){
firstValue = Character.getNumericValue(phone_book[i].charAt(0));
arr[firstValue].add(phone_book[i]);
}
for(int i=0; i<10;i++) {
arr[firstValue].sort(Comparator.naturalOrder());
}
//System.out.print(phone_book[1]);
for(int i = 0; i < phone_book.length; i++){
firstValue = Character.getNumericValue(phone_book[i].charAt(0));
//이 아래 부분을 더 수정해야 할듯
for(int j = 0; j < arr[firstValue].size(); j++){
//System.out.print(arr[j].get(1));
if(!(arr[firstValue].get(j).equals(phone_book[i])) && arr[firstValue].get(j).contains(phone_book[i]) && (arr[firstValue].get(j).indexOf(phone_book[i])) == 0){
return !answer;
}
// if(!(arr[j].equals(phone_book[i])) && arr[j].contains(phone_book[i])){ //contains로 검사하면 같은 값을 찾는 것이지 문제의 조건인 접두어를 찾는게 아니다.
// //현재 코드는 arraylist에 phone_book[i] 있는지를 검색하는데 이게 아니고 arraylist에 있는 요소를 꺼내와서 phone_book[i] 와 겹치는 부분이 있는지를 검사해야 접두어 검사가 된다.
// return !answer;
// }
}
}
//내가 생각한 조건
//1. 같은 전화번호도 검사하는 코드니까, 같은 전화번호 일때는 검사를 하지 않음
//2. 비교해서 같은 부분이 첫 글자인지가 중요하다. 이거 까먹고 있던 듯
return answer;
}
}
두 번째 풀이
도저히 머리속으로 고민해도 답이 나오는 상황이 아니어서 https://programmers.co.kr/questions/25120 질문하기에 있는 고수분의 도움말대로 해보기로 했다. 다만 정렬해서 index와 index+1을 비교하는 것은 알거 같은데 만약 false가 나오는 문자열이 index+8 처럼 저 멀리 있는 문자열이면 오류가 나지 않나? 라고 생각했는데, 정렬을 값우선, 길이차선을 기준으로 정렬하면 값이 최대한 같은 문자열끼리 뭉치게 되어있다. 예를 들어서 “12” “12345” “9” “125” 이렇게 입력값이라면 내가 처음 예상한것은 “12” “125” “12345” “9” 이렇게 정렬 되는 것을 예상했는데 실제로는 “12” “12345” “125” “9” 이렇게 정렬이 된다. 그래서 index와 index+1만 계산을 해줘도 원하는 값을 구할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.ArrayList;
import java.util.Comparator;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
ArrayList<String> arr = new ArrayList();
int firstValue = 0;
for(int i = 0; i < phone_book.length; i++){
arr.add(phone_book[i]);
}
arr.sort(Comparator.naturalOrder());
//System.out.print(arr);
for(int i = 0; i < arr.size() - 1; i++){
if(arr.get(i + 1).contains(arr.get(i)) && (arr.get(i + 1).indexOf(arr.get(i))) == 0){
return !answer;
}
}
//내가 생각한 조건
//1. 같은 전화번호도 검사하는 코드니까, 같은 전화번호 일때는 검사를 하지 않음
//2. 비교해서 같은 부분이 첫 글자인지가 중요하다. 이거 까먹고 있던 듯
return answer;
}
}
역시 Lv1을 넘어서니 이제 점점 효율성이 압박으로 다가온다. 알고리즘 공부를 다시 해야겠다.
Leave a comment