[Programmers 문제풀이 JAVA] Level 2 전화번호 목록

 

📄 전화번호 목록

🔗 문제 풀러가기

---

문제는 String 배열만을 사용해서 해결하였습니다. 먼저 이번 풀이는 제가 처음 접근했던 방법들과 접근하던 도중 발생했던 오류(런타임 에러) 에 대한 개인적인 생각과 해결과정을 함께 포함시켜 풀이를 해보겠습니다. 최종 소스코드만 보고싶으신 분들은 최종 소스코드만 보기를 클릭하셔도 됩니다. 글의 순서는 다음과 같습니다.

1. 첫 번째 접근 방식과 에러
2. 두 번째 접근 방식과 에러
3. 런타임 에러가 발생하는 이유(개인적인 생각)
4. 런타임 에러를 해결한 방법(최종 소스코드)

---

첫 번째 접근 방식

첫 번째로 접근했던 방법은 HashMap을 이용해서 문제를 접근하였습니다. 모든 전화 번호 목록을 Map에 입력 후 검사 대상인 전화번호를 제외하고 Map의 모든 값들을 확인하였습니다.

확인하는 방법은 value.subString(0, targetLength).equals(targetString) 으로 접근하였습니다. 하지만 런타임 에러가 발생하였고 전화번호 목록의 최대 크기가 1,000,00 이기 때문에 메모리 초과가 발생한다고 생각해 Map을 사용하지 않기로 하였습니다. 또한 굳이 Map으로 접근할 이유가 없었는데 왜 이렇게 접근했었는지 의문입니다.

---

두 번째 접근 방식

두 번째로 접근했던 방법은 전화번호 목록을 정렬(오름차순) 하고 모든 문자열을 탐색하며 검사 대상 전화번호로 시작하는지 여부를 판단하였습니다. 모든 전화번호를 검사해야 하기 때문에 2중 for문으로 작성하였고 이 방법 또한 subString을 사용하여 문제를 풀었습니다. 하지만.... 돌아온건 역시나 런타임 에러였습니다. 작성했던 코드는 아래와 같습니다.

🌱 런타임 에러를 내뿜는 Solution 함수

public boolean solution(String[] phone_book) {
    Arrays.sort(phone_book);

    int len = phone_book.length;
    for (int targetIndex = 0; targetIndex < len - 1; targetIndex++) {
        int targetLen = phone_book[targetIndex].length();
        for (int searchIndex = targetIndex + 1; searchIndex < len; searchIndex++) {
            if (phone_book[searchIndex].substring(0, targetLen).equals(phone_book[targetIndex])) {
                return false;
            }
        }
    }

    return true;
}

 

프로그래머스에서 제공한 테스트케이스와 제가 임의로 설정한 테스트케이스 모두 통과를 하며 전혀 이상이 없으거라 생각했던 코드가 실제 코드 채점에서 런타임 에러를 내뿜었습니다. 여기서 유심히 봐야 할 사항은 시간초과는 없고 실패 케이스 모두가 런타임 에러라는 사실입니다. 보통 런타임 에러는 메모리 초과에서 나타납니다.

---

런타임 에러가 발생하는 이유

그렇다면 Map을 사용하지도 않았는데 메모리 초과는 대체 어디서 발생하는 것일까? 라고 생각하였습니다. 결론부터 말씀드리면 subString에 문제가 있었습니다. 문제가 발생하는 부분을 추측한 결과 subString이 의심스러웠습니다. String을 다룰 때에는 항상 조심하며 새로운 String객체를 생성하는 것때문에 메모리 효율성이 안좋아지는 점을 고려하라는 글들을 많이 접했기 때문입니다. 그래서 subString이 과연 어떻게 동작하는지 궁금해져 직접 들여다 보았습니다. subString의 구현은 아래와 같습니다. (IntelliJ 에서 구현 함수로 이동하는 단축키 : Ctlr + B)

💡 String Class의 subString 함수

public String substring(int var1, int var2) {
    if (var1 < 0) {
        throw new StringIndexOutOfBoundsException(var1);
    } else if (var2 > this.value.length) {
        throw new StringIndexOutOfBoundsException(var2);
    } else {
        int var3 = var2 - var1;
        if (var3 < 0) {
            throw new StringIndexOutOfBoundsException(var3);
        } else {
            return var1 == 0 && var2 == this.value.length ? this : new String(this.value, var1, var3);
        }
    }
}

주어진 범위가 유요한지 확인하는 부분은 제외하고 주요하게 봐야 할 부분은 바로 결과를 반환하는 부분인 return var1 == 0 && var2 == this.value.length ? this : new String(this.value, var1, var3) 입니다. 결과적으로 온전한 문자열이 아닌 부분 문자열 이라면 새로운 String객체를 반환하고 있습니다. 런타임 에러의 주범이 여기 있었습니다. (제 생각은 이부분 때문이라고 생각합니다.)
이게 문제가 되는 이유는 문제를 해결하며 모든 전화번호 목록을 검사할 때 subString을 사용하므로 문제에서 최악의 케이스의 경우 1,000,000개 이상의 새로운 String 객체가 생성이 되기 때문입니다. 이는 메모리 측면에서 아주 비효율적입니다. 또한 메모리 제한이 있는 알고리즘 문제에서 메모리 초과를 발생시킬 수 있습니다.

 

---

최종 소스코드

그렇다면 이 문제를 어떻게 해결을 할까? 라고 물음을 했을 때 찾은 함수가 startsWith(String prefix) 입니다. 이 함수는 문자열이 파라미터로 주어진 prefix로 시작하는지 검사하며 prefix로 시작시 true, 시작하지 않을 시 false를 반환하는 함수입니다.

📓 startsWith 시그니처

public boolean startsWith(String prefix)
public boolean startsWith(String prefix, int offset)

 

그리고 전화번호 목록을 정렬(오름차순) 했을 때 성능을 조금이라도 향상시키기 위해 고민해 본 결과 전화번호 목록이 오름차순으로 정렬 되어 있기 때문에 2중 for문을 사용하지 않고 단일 for문으로 i + 1번째 번호가 i번째 번호로 시작하는지만 확인하여 최종적으로 전화번호 목록을 정렬하는 시간인 nlogn으로 문제를 해결할 수 있습니다. 전화번호 목록 정렬과 i + 1번째 번호가 i번째 번호로 시작하는지만 확인하는 부분은 조금만 고민해보면 이해하실 수 있습니다. 최종 Solution함수는 아래와 같습니다.

🌱 Solution 함수

public boolean solution(String[] phone_book) {
    Arrays.sort(phone_book);

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

    return true;
}

 

제가 생각한 부분이 정답이 아닐 수 있습니다. 다른 생각을 가지고 계신 분, 잘못된 부분을 찾은 분 등 여러 의견 댓글로 남겨주시면 감사하겠습니다. 함께 고민하면 더 좋은 결과를 얻을 수 있다고 생각합니다.

---

💡 Github에 더 많은 문제 풀이가 있습니다.

Programmers 문제 풀이

BaekJoon Online Judge 문제 풀이