Menu

Subscribe

[JAVA/프로그래머스] 해시_전화번호 목록: 링크드리스트와 해시의 효율성 차이

HEESOO on Programmers

👊 첫 번째 도전

1. 설계

  1. 이중 for문을 사용하여 배열 phone_book의 원소를 두 개씩 비교한다.
  2. String 라이브러리의 startsWith메소드로 원소 i가 j의 접두사인지 확인한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 *
 * @author HEESOO
 *
 */
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        for(int i=0;i<phone_book.length;i++){
            for(int j=i+1;j<phone_book.length;j++){
                if(phone_book[j].startsWith(phone_book[i])){
                    return false;
                }
            }
        }
        return answer;
    }
}

3. 결과

실행결과 테스트 8, 9에서 실패하였다.

4. 문제점

phone_book=[“98765”,…,”98”]일 때, 위 코드를 실행했을 경우 마지막 원소 “98”이 0번째 원소인 “98765”의 접두사임을 찾지 못한다. 따라서 배열을 길이에 따라 오름차순으로 정렬한 후 if문을 체크해야한다.

👊 두 번째 도전

1. 설계

  1. phone_book을 sort한다.
  2. 이중 for문으로 접두사인지 체크한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import java.util.Arrays;
/**
 *
 * @author HEESOO
 *
 */
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);
        for(int i=0;i<phone_book.length;i++){
            for(int j=i+1;j<phone_book.length;j++){
                if(phone_book[j].startsWith(phone_book[i])){
                    return false;
                }
            }
        }
        return answer;
    }
}

3. 결과

실행결과 🤟 성공 🤟

👏 해결 완료!

문제가 해시 카테고리에 있는데도 구글링한 결과 해시로 푼 사람은 한명밖에 찾지 못했다.