[99클럽 코테 스터디 5일차 TIL] 프로그래머스 - 전화번호 목록

99클럽 코테 스터디 5일차 TIL 입니다.

[level 2] 전화번호 목록 - 42577

문제 링크

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119

• 박준영 : 97 674 223

• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.

  • 각 전화번호의 길이는 1 이상 20 이하입니다.

  • 같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

입출력 예 설명

입출력 예 #1 앞에서 설명한 예와 같습니다.

입출력 예 #2 한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3 첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

---

풀이 코드

import java.util.*;

class Solution {
    public boolean solution(String[] phoneBook) {
        Arrays.sort(phoneBook);
        for(int i = 0; i < phoneBook.length - 1; i++) {
            if (phoneBook[i + 1].length() < phoneBook[i].length()) continue;
            if (phoneBook[i + 1].substring(0, phoneBook[i].length()).equals(phoneBook[i])) return false;
        }
        return true;
    }
}

• Time: 323.87 ms

• Memory: 96.8 MB

풀이 과정

1. 문자열 배열 그대로 오름차순 정렬을 통해 접두어가 되는 문자가 있다면 순서대로 배치되도록 한다.

2. i 번째 문자열과 i + 1 문자열의 길이를 비교하여 i + 1 의 문자열의 길이가 더 짧다면 넘긴다. 접두어가 같을 경우, 문자열의 길이가 긴 문자가 무조건 i + 1 에 배치될 수 밖에 없다. (ex. { "2423390", "2420" } -> { "2420", "2423390" })

3. i + 1 번째 문자열을 i 번째 문자열의 길이만큼 자르고 동일한 문자인지 비교한다.

개선하기

import java.util.*;

class Solution {
    public boolean solution(String[] phoneBook) {
        Arrays.sort(phoneBook);
        for (int i = 0; i < phoneBook.length - 1; i++) {
            if (phoneBook[i + 1].startsWith(phoneBook[i])) return false;
        }
        return true;
    }
}

• Time: 337.13 ms

• Memory: 98.5 MB

앞선 풀이와 속도나 메모리 차이가 크진 않다. 해당 문제를 풀 때 IDE 의 도움없이 문제를 풀어봤는데 startsWith() 함수가 있다는걸 알았으나 startWith() 로 기억하고 있어서 해당 함수를 쓰질 못했다.

해당 함수를 활용한 풀이로 함수 이름이 매우 직관적이어서 코드의 간결함이나 가독성 면에서는 더 좋다고 생각한다.

다른 사람의 풀이

import java.util.*;

class Solution {
    public boolean solution(String[] phoneBook) {
        boolean answer = true;
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i < phoneBook.length; i++) {
            map.put(phoneBook[i], i); // key 에 전화번호를 할당
        }
        for (String s : phoneBook) {
            for (int j = 0; j < s.length(); j++) {
                /*
                전화번호를 문자 단위로 잘라서 맵에 있는지 확인
                j 까지만 잘라서 자기 자신을 비교하지 않도록 함
                */
                if (map.containsKey(s.substring(0, j))) {
                    return false;
                }
            }
        }
        return answer;
    }
}

• Time: 307.91 ms

• Memory: 226 MB

HashMap 을 사용한 풀이로 cotainsKey() 함수를 활용하고 j 길이까지만 잘라서 자기 자신은 포함되지 않게 하는 부분이 참신했다.

위 풀이에서 HashMap 의 value 값은 사용하지 않기 때문에 HashSet 으로도 풀어봤다.

다른 사람의 풀이를 개선하기

import java.util.*;

class Solution {
    public boolean solution(String[] phoneBook) {
        boolean answer = true;
        Set<String> set = new HashSet<>();
        Collections.addAll(set, phoneBook);
        for (String s : phoneBook) {
            for (int j = 0; j < s.length(); j++) {
                /*
                전화번호를 문자 단위로 잘라서 set 에 있는지 확인
                j 까지만 잘라서 자기 자신을 비교하지 않도록 함
                */
                if (set.contains(s.substring(0, j))) {
                    return false;
                }
            }
        }
        return answer;
    }
}

• Time: 282.45 ms

• Memory: 219 MB

메모리 사용량의 차이는 크지 않으나 속도는 유의미하게 감소했다. 시도한 풀이 방법 중 가장 빠르다.

---

돌아보기

이번에 풀어본 문제는 실제 코딩테스트 환경에 익숙해지기 위해 IDE(IntelliJ) 없이 프로그래머스 페이지에서만 풀어봤다. 앞서 언급했던 StartsWith() 함수가 있는건 알지만 철자가 틀려서 함수 사용을 하지 못하고 다른 방식의 풀이로는 풀질 못했다. 회사 동료가 힌트를 줘서 겨우 풀 수 있었다.

IDE에 생각보다 더 많이 의존하고 있다는 생각을 했다. 하나의 문제로 여러 풀이법을 알 수 있어서 재밌었다.

다음에는

• 앞으로도 IDE 없이 문제 풀어보기

• 경쟁심이나 열등감을 인정하기

---

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL