[level 2] Title: 전화번호 목록 코드 개선:: List -> Set

문제 링크 :

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

 

 

고득점 키트 해시 카테고리 문제 해설

https://sedate-nitrogen-21c.notion.site/4e2215495278436e905f4a4d181a2f20?pvs=4

고득점 키트 : 해시

 

 

문제 요약

해당 문제는 전화 번호부를 Stirng 배열 타입의 매개변수로 전달받아

접두사가 있는지 여부를 판단하는 문제 입니다.

있을 경우 FALSE 반환 , 없을 경우 TRUE 반환

 

 

 

시도

1. ArrayList 자료구조 활용

 

처음에 List로 하기 위해서 ArrayList 변수를 선언하여 시도하였으나, 잘되지 않았습니다.

이를 위해 정렬을 한 후, i번째 요소와 i+1번째 요소를 비교하였습니다.

 

Arrays.sort();

String.startsWith();

위의 메서드를 활용 하였습니다.

 

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        List<String> list = new ArrayList(Arrays.asList(phone_book));
        Collections.sort(list);
        
        for(int i=0; i<list.size()-1;i++){
            String num1 = list.get(i);
            String num2 = list.get(i+1);
            if(num2.startsWith(num1)) return false;
        }
        return true;
	}
}

 

>> 로직 설명

 

[119, 80922, 1192020, 110] 의 배열을 오름차순으로 정렬합니다.

결과 : [110, 119, 1192020, 80922] 

 

i+1번째 요소(1192020)가 i번째 요소(119)로 시작할 경우 접두사가 있는 리스트이므로, false를 반환합니다.

if 문안에 들어오지 않을 경우는 접두사가 존재하지 않는 것이므로, true를 반환합니다.

 

 

 

2. HashSet 자료구조 활용

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Set<String> setList = new HashSet<>();
        
        for(String book : phone_book){
            setList.add(book);
        }
        
        for(String book : phone_book){
            for(int i=1; i<book.length(); i++){
                if(setList.contains(book.substring(0,i))) return false;
            }
        }
        return true;
    }
}

 

>> 로직 설명

Set 자료구조를 활용하여 저장합니다.

해당 setList [119, 80922, 1192020, 110] 의 요소 하나씩 접근하여 접두사 여부를 검사합니다.

"119" 의 경우 substring()을 통해

1

11

값이 setList에 있는지 찾습니다. 해당 값이 있을 경우 false 반환합니다.

 

String[] 혹인 int[] 배열에는 contains() 메서드가 없기 때문에 이를 활용하기 위해 Collections 자료구조를 활용한 것.

 

 

 

?

좌측 : List,  우측: Set

 

여기서 의문인 점은,, List를 활용한 코드가 메모리 측면에서 더욱 효율적이였다. 

요소의 중복을 제거하기 위해 Set을 사용하는 것인가를 생각해보았으나, 아니다.

 

해당 문제를 잘 살펴보면 아래와 같은 제약 사항이 있다. 중복값은 애초에 존재하지 않는다는 전제이다.

 

 

 

중복을 제거해줄 필요가 없는데도 왜 HashSet을 써야 할까?

 

 

이것에 대해서는 아직 잘 모르겠습니다.

알아보는 대로 추가적으로 작성하겠습니다.