[ 알고리즘 ] 프로그래머스 - 전화번호 목록

 

 

 작성한 코드 

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        HashMap<String,Integer> map = new HashMap<>();
        
        for(String str : phone_book) {
            map.put(str, 1);
        }
        
        for(String str : phone_book) {
            for(int i=1; i < str.length(); i++) {
                String prefix = str.substring(0, i);
                
                if(map.containsKey(prefix)) {
                    return false;
                }
            }
        }
    
        return answer;
    }
}

 

 

 한줄씩 해석해보기 

answer는 true로 초기화

 

HashMap은 key(String) , value(Integer) 형태로 만든다

 

배열 phone_book의 각각을 str이라고 하자 {

     map.put을 이용하여, 모든 str을 추가함 (value는 1)

}

 

배열 phone_book의 각각을 str이라고 하자 {

     i는 1부터 str의 길이만큼 i++ {

          prefix 에는 subString을 이용해서 str의 모든 글자를 담음 (이때, i는 1부터 str의 길이만큼)

          

          만약, map의 key중에서 prefix를 포함한다면 {

                 false를 반환하여 반복문 중단

           }

     }

}

return answer;   (if조건이 끝까지 성립하지 않는 경우는 true를 반환)

 

 

---

 

 틀렸던 방식 

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        HashMap<String,Boolean> map = new HashMap<>();
        
        for(String str : phone_book) {
            for(int i=0; i <= str.length(); i++) {
                String prefix = str.substring(0,i);
                
                if(map.containsKey(prefix) && !prefix.equals(str)) {
                    answer = false;
                }
            }
            answer = true;
        }

        return answer;
    }
}

 

 

 수정한 부분 

(중략)

if(map.containsKey(prefix) && !prefix.equals(str)) {
	answer = false;
    }
}
answer = true;

 

1) 결과값이 true로 고정되어버리는 문제

if문을 이용해서 기껏 false로 적용했는데

다시 answer = true 때문에 반복문을 이어가면서 모든게 true로 바뀌어버렸음

 

 

2) 반복문이 끊기는 문제

또한, 반복문을 통해서 계속해서 비교를 해야하기 때문에

만약 i번째의 str이 접두어가 아니더라도, (= 결과가 true라고해도)

다음을 또 비교하기 위해서 map.put 을 이용하여 추가해줘야함(대신, true로 추가)

 

-> 처음부터 map의 value를 Integer형태로 1로 초기화해버리자.

중간에 또 put하는게 비효율적인듯 

 

 

 

3) if문에 걸리지 않는다면, true를 반환

굳이 answer에 true를 대입하지 않아도 괜찮은 이유는 !

answer의 초기값이 true이고,

맨 마지막 문장에 의하여 answer를 return하기 때문이다

 

 

4) false조건이 성립한다면 반복중지.

false일 경우에는 더이상 반복하지 않아도 되니까 그냥 바로 return false

 

 

5) 어차피 HashSet의 key값은 중복불가능