[프로그래머스] 전화번호 목록

---

프로그래머스 Lv2 - 전화번호 목록 문제

프로그래머스 알고리즘 고득점 Kit 카테고리의 해시 문제 중 레벨 2 전화번호 목록 문제를 풀이했다.
문제 카테고리는 해시로 등록되어 있긴 하지만, 정렬 후 그 다음 인덱스의 요소와 비교하는 방식으로 풀이했다.
처음에는 if문 부분을 이중 for문으로 풀이했더니, 효율성 검사에서 시간 초과가 발생했다.
시간 복잡도를 줄이고자 단일 for문으로 충분히 풀이할 수 있을 것 같아 변경하여 테스트를 통과했다.

문제 조건에서 인자로 주어진 배열이 최대 백만이였는데 이중 for문으로 풀이하면 시간 복잡도가 제곱이 되니 문제 조건을 잘 파악해야겠다!!

ContactList.java

package com.example.Programmers.Lv2;

import java.util.Arrays;

/**
 * 프로그래머스 Lv2 - 전화번호 목록
 */
public class ContactList {
    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;
    }
}

ContactListTest.java

package com.example.Programmers.Lv2;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import org.junit.Test;

public class ContactListTest {
    @Test
    public void contactListTest() {
        ContactList c = new ContactList();

        boolean result1 = c.solution(new String[] { "119", "97674223", "1195524421" });
        boolean result2 = c.solution(new String[] { "123", "456", "789" });
        boolean result3 = c.solution(new String[] { "12", "123", "1235", "567", "88" });

        assertFalse(result1);
        assertTrue(result2);
        assertFalse(result3);

    }
}