[코딩테스트-JAVA]전화번호 목록 풀이 - 초보도 이해하는 풀이(프로그래머스)

안녕하세요

인포돈 입니다.

프로그래머스 전화번호 목록 풀이입니다. 

* 참고사항
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

프로그래머스 (전화번호 목록)

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

 

구조대 : 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

 

실패코드

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        int index = phone_book[0].length();
        
        for(int i = 1 ; i < phone_book.length ; i++){
            if(phone_book[i].substring(0,index).equals(phone_book[0]))
                return !answer;
        }
        
        
        return answer;
    }
}

해당 실패 코드는 정확도 + 효율성을 합한 점수에서 50점을 받았습니다. 해당 코드에서 제가 생각하지 못한 점은 바로 첫번 째 인덱스만 접두어로 확인했다는 점이었습니다. 해당 사항을 고려하지 않은 코드였기 때문에 오류가 났습니다.

 

성공코드

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

}

실패코드 작성 후 곰곰이 생각해보니 자바에는 접두어를 판별해주는 메서드가 있었다는 것을 알 수 있었죠. 중첩 반복문을 이용하여, 앞 뒤로 해당 전화번호부의 접두어를 판별해 주죠.

 

이제 실패 코드와 같이 성공코드의 흐름도와 여기서 사용된 기법들을 하나하나 설명해드리겠습니다~

---

알고리즘 흐름도

 

실패코드

첫 번째 인덱스의 값의 길이를 저잘

-> phone_book의 크기만큼 인덱스를 반복하면서, 같은 값이 있으면 false를 반환

 

성공코드

중첩 반복문을 사용

-> 중첩 문안에 i와 그 이후 인덱스들을 하나하나씩 비교하여 반환

---

STEP1 substring

실패 코드에서 쓰인 substring읜 문자열에 지정되어있는 메서드입니다.

if(phone_book[i].substring(0,index).equals(phone_book[0]))

해당 코드를 보면 phone_book [i] 인덱스에 들어있는 문자열을 0에서부터 index까지 자른다는 의미이죠.

 

만약 phone_book [i]에 123456789의 값이 들어있고, index의 값이 4라면, 1 2 3 4 5까지의 값이 잘려서 나오게 됩니다.

여기서 앞선 0의 값을 다르게 지정할 수도 있다는 사실을 알아두시면 됩니다~

---

STEP2. equlas와 ==의 차이

해당 스탭에서는 동등의 의미를 같은 두 가지를 알아보겠습니다.

 

글을 다 읽기 귀찮으시다면, 문자열은. equals를 이용하고 이외에는 ==을 이용한다고만 알아두시면 됩니다.

 

String s1 = "abcd";
        String s2 = new String("abcd");
		
        if(s1 == s2) {
            System.out.println("두개의 값이 같습니다.");
        }else {
            System.out.println("두개의 값이 같지 않습니다.");
        }

간단히 다음과 같은 코드가 있다면, 답은 "두 개의 값이 같지 않습니다."입니다.

 

equals는 값을 비교하고, ==은 주소 값을 비교하기 때문이죠.

 

일반적으로 int char와 같은 데이터 타입은 call by value형태로 바로 값을 반환합니다. 그렇기 때문에 ==을 사용하든 equals를 사용하든 값이 비교가 되죠

 

그러나 string의 경우 클래스로 정의되어 있고 클래스는 call by reference입니다. 여기서 reference는 주소! 로생 각하시면 됩니다. 즉, 반환되는 값은 주소 값이 됩니다.

 

아무리 값이 같아도 주소 값은 다르게 저장이 되죠. 이에 따라 해당 예제 코드의 두 값은 ==을 이용했기에 주소 값이 다라 "두 개의 값이 같지 않습니다."의 답이 출력되게 되는 거죠

 

즉 string의 값을 비교하고 싶을 때는 equlas를 이용해야 합니다

---

STEP 3 startWith

startWith는 정말 간단한 메소드 입니다.

 

String startsWithT = "자바 코딩 연습문제 ";

        System.out.println( startsWithT.startsWith("자바") );  // true

        System.out.println( startsWithT.startsWith("자바 ") );// true

        System.out.println( startsWithT.startsWith("자") );// true

        System.out.println( startsWithT.startsWith(" 자") );// false

해당 예제 코드와 같이 반환값은 boolean으로 true또는 false를 반환해 줍니다.

 

특정 문자 또는 문자열로 시작하는지 체크해주는 메서드 입니다. 따라서 시작하는게 자, 자바, 자바 , 자바 코, 자바 코딩, 자바 코딩 , 자바 코딩 연, 자바 코딩 연습, 자바 코딩 연습문, 자바 코딩 연습문제, 자바 코딩 연습문제 이렇게 모든 값을 넣어주어도 true가 반환되게 됩니다.