lango

찍먹? 부먹?
난 부먹 개발자.

1 minute read



입출력 예시

Input-1
phone_book = [“119”, “97674223”, “1195524421”]
Output-1
false

Input-2
phone_book = [“123”,”456”,”789”]
Output-2
true

Input-1
phone_book = [“12”,”123”,”1235”,”567”,”88”]
Output-1
false


문제 풀이

이 문제는 처음엔 이중 반복문으로 풀어봤는데 효율성 테스트에서 시간초과가 발생되어 반복문을 한 번만 돌려서 해결해야 했다.
또한 phone_book의 각 원소들의 접두사 포함여부를 검증하기 위해 contains나 indexOf를 사용하려 했는데, String 관련 함수중 startsWith 함수를 찾게 되었다.

1. 오름차순 정렬

먼저 이중 반복문 없이 하나의 반복문 만으로 어떻게 각 단어들의 접두어를 확인할까? 바로 오름차순 정렬을 활용하면 된다.
예를 들어 phone_book 배열이 [“6”, “12”, “6789”] 원소를 가지고 있다고 한다면, “6”과 “6789”의 접두어가 같기에 두번 비교해야 한다. 그런데, 오름차순 정렬을 하게 되면 [“6”, “6789”, “12”]가 되고, “6”과 “12”는 서로 접두어로 시작하지 않기에 마지막 원소까지 비교할 필요가 없어진다. 단지 현재 원소와 다음 원소의 접두어만 비교하면 된다.

2. startsWith 함수 활용

하나의 반복문을 돌면서 현재 문자열의 접두어가 다음 문자열의 접두어가 되는지 확인하기 위해 startsWith() 함수를 활용하자.

startsWith()
startsWith() 함수는 대상 문자열이 특정 문자 또는 문자열로 시작하는지 즉, 접두사가 되는지 체크하는 함수이다.
해당 문자열로 시작되는지 여부를 확인하고 boolean 에 맞춰 true/false 값을 리턴한다.

이제 오름차순 정렬과 startsWith 함수를 활용해 코드를 작성해보자.

1
2
3
4

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

phone_book 배열을 오름차순으로 정렬하고 for문에서 현재요소의 접두어가 다음 요소의 접두어가 되는지 확인하면 된다.


작성 코드

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

import java.util.Arrays;

class Solution {
    public static void main(String[] args) {
        String[] phone_book = {"119", "97674223", "1195524421"};
        // String[] phone_book = {"AA","BB","CC","DD","DDEE","FF"};
        // String[] phone_book = {"123","456","789"};

        long start = System.currentTimeMillis();
        solution(phone_book);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }

    public static boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);

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

        return answer;
    }
}

회고

  • 효율성을 높이기 위해선 이중 반복문을 최대한 지양해야 한다는 것이 중요하다 느낄 수 있었고, 한번의 정렬만으로 불필요한 반복과 비교를 줄일 수 있었다.
  • String 관련 함수중 startsWith()와 endsWith() 에 대해서 공부할 수 있었다.

You may also enjoy