99클럽 코테 스터디 5일차 TIL + 오늘의 학습 키워드

☑️ 문제: 전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

 

☑️ 설계 과정

phone_book에 있는 전화번호(문자열, String)가 다른 전화번호의 접두사가 되는 경우가 없다면 true, 있다면 false를 반환해야 한다.

그렇다면 접두사가 되는 경우를 반복문으로 탐색해서 false로 초기화 후 반복문을 탈출하면 될 것 같았다.

하지만 완전탐색으로 반복문을 실행(O(N^2))하면 효율성 테스트를 통과하지 못할 게 보였다.

phone_book의 최대 길이가 10^6이기 때문이다.

 

나는 고민하다가 접두사가 되기 위해서는 길이가 더 짧아야 된다는 사실을 떠올렸다.

예를 들어 word1, word2가 있을 때, word1의 길이는 3이고 word2의 길이는 4라고 하자.

word1은 word2의 접두사가 될 수도 있지만, 반대로 word2는 word1의 접두사가 될 수 없다.

 

그리고 phone_book 배열에 있는 전화번호(String, 문자열)를 Set에 저장하고,

phone_book 배열에 있는 전화번호 길이로 문자열의 앞 부분을 잘랐을 때

Set에 자른 문자열이 존재하지 않아야 접두사가 되는 전화번호가 없다고 할 수 있을 것이다.

이 때, 자를 수 있는 길이는 자기 자신의 길이 - 1까지일 것이다. (자기 자신과 같은 전화번호는 없으므로.)

 

위와 같이 생각한 뒤, 설계는 다음과 같이 하였다.

1. phone_book을 전체 탐색(O(N))해서 다음을 초기화한다.
   
   1. boolean[] existLen = new boolean[21] (전화번호의 최대 길이는 20)
   2. existLen[전화번호의 길이] = true로 초기화
   3. Set<String> set 선언
   4. set.add(전화번호)
2. phone_book을 전체 탐색(O(N))해서 existLen만큼 전화번호를 자른 문자열이 Set에 있는지(set.contains)로 확인한다. 존재할 경우, 다른 전화번호가 접두사가 될 수 있다는 뜻이므로 answer를 false로 할당해주고 반복문을 벗어난다.

import java.util.Set;
import java.util.HashSet;

class Solution {
    public boolean solution(String[] phone_book) {
        // 1. phone_book을 탐색하며,
        // (1) 존재하는 문자열의 길이 체크
        // (2) Set에 phone_book 문자열 저장        
        Set<String> set = new HashSet<>();
        boolean[] existLen = new boolean[21];
        
        for (int i = 0; i < phone_book.length; i++) {
            String number = phone_book[i];
            set.add(number);
            existLen[number.length()] = true;
        }
        
        // 2. existLen만큼 전화번호를 자른 문자열이 Set에 있는지 확인
        //    있다면, 그건 접두사가 되는 전화번호가 존재한다는 뜻이므로 false
        for (int i = 0; i < phone_book.length; i++) {
            String number = phone_book[i];
            for (int len = 1; len < number.length(); len++) {
                if (existLen[len] && set.contains(number.substring(0, len))) {
                    return false;
                }
            }
        }        
        return true;
    }
}

 

이렇게 하면 효율성 테스트 3, 4 결과가 다음과 같았다.

테스트 3 〉

70.09ms, 101MB

테스트 4 〉

103.73ms, 99.6MB

 

시간 내에 풀고 나니 아쉬운 점이 많이 보였다.

existLen을 int 배열로 쓰기보다는 다른 자료구조를 사용하는 게 좋지 않은지,

그 외 내가 모르는 메소드로 좀 더 코드 가독성을 높이거나, 간단하게 풀 수 있지는 않을까 하는 그런 생각이 들었다.

 

그리고 내가 한 풀이에서는 코드 이점을 모르겠어서 쓰지 않았지만,

한 단어가 다른 단어보다 짧아야 접두사가 될 수 있다면, Sort로 정렬 후에 탐색하는 방법도 있을 것 같았다.

 

☑️ 다른 사람 코드 참고

(일단 흡수가 가능한 부분까지만 참고)

boolean startsWith(String prefix) 사용하기

아니나 다를까 String 함수가 존재했다.

위를 사용해서 작성하면 다음과 같이 쓸 수 있다.

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book); // 자기 자신 이후의 단어만 탐색 가능해짐

        for (int i = 0; i < phone_book.length - 1; i++) {
            if (phone_book[i + 1].startsWith(phone_book[i])) {
                return false;
            }
        }
        return true;
    }
}

 

(참고로 현재 다른 사람 풀이에서 제일 첫번째로 나오는 startsWith을 사용하는 코드는 시간 초과가 난다. O(N^2)이기 때문이다.)

위 코드에서는 sort가 O(NlogN)이므로 시간 초과가 나지 않지만, 시간이 꽤 걸린다.

효율성 테스트 3, 4 결과는 다음과 같다.

테스트 3 〉

305.00ms, 97.1MB

테스트 4 〉

257.84ms, 96.8MB

 

---

---

☑️ 그 외 회고 및 주저리

• Android 15가 8월 중순, iOS 18이 9월 중 정식 배포
• iOS에서 Widget Extension을 만들면 Widget, LiveActivity(iOS 16.2+)관련 코드가 자동 생성된다. Widget을 만들면, 홈 화면에서 + 버튼으로 추가 가능하다. Widget에서 편집 허용을 했냐 안 했느냐에 따라 롱클릭했을 때 나오는 리스트 내용이 다르다.
• Issue와 잘 연결해놓은 커밋은 히스토리 찾는 입장에서 너무 감사하다.
• 현재 Recorder에서 상태 패턴을 사용 중인데 이를 분석 중. AudioSession은 프레임워크에서 싱글톤으로 사용하도록 만들어져 있구나.
• 오늘 책에서 읽은 자신이 흡수한 내용만 짧게 기록하고 복기해야 내 것으로 남는다는 문장이 인상깊었다
• 잠과 체력을 챙기자