99클럽 코테 스터디 1일차 TIL + 해시/전화번호 목록

오늘은 99클럽 코테 스터디 첫날! 

매일 문제를 풀며 습관을 잡고자 신청했다. 

 

 

출제된 문제는 https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

프로그래머스-전화번호 목록 문제이다. 

 

카테고리에 해시라고 적혀있어서, 해시를 사용하여 풀어보려했으나 우선 생각한 방법으로 시도했다. 

 

처음 작성한 코드는 아래와 같았다. 이중 for문으로 startWith함수를 통해 접두어인지 확인한다. 

테스트 케이스는 통과했지만, 효율성 테스트를 통과하지 못했다. 예상한 결과였다. 

 

1)

import java.util.Scanner;
import java.util.Arrays;


class Solution {
    public boolean solution(String[] phone_book) {
        Scanner sc = new Scanner(System.in);
        
        Arrays.sort(phone_book); //sort 
        boolean answer = true;
        
        for(int i=0;i< phone_book.length-1; i++){
        
            for(int k=i+1; k<phone_book.length ;k++){
                
                if(phone_book[k].startsWith(phone_book[i])){
                    answer=false;
                    break;
                }
            }
        }
        
        return answer;
    }
}

 

O(n⋅m2) 복잡도! m<20이다 

 

 

그래서 해시맵을 통해 풀어보았다. 

 

 

---

MEMO

 

 

해시맵 HashMap 개념 

키:밸류

 

키는 중복이 불가. 

 

HashMap<String, String> map = new HashMap<String, String>(); // 해쉬맵 선언하기 

map.put(phone_book[i], i); // 해시맵에 원소 넣는 방법 

 

containsKey(key) 맵에 키가 있는지 반환하는 함수

 

substring (n, m) 문자열의 n부터 m까지를 잘라서 반환 

* length와 length()의 차이! 

• 배열: length 속성을 사용하여 배열의 길이를 구합니다.
• 문자열: length() 메서드를 호출하여 문자열의 길이를 구합니다.

 

---

2)

import java.util.HashMap;
import java.util.Map;



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

2

 

복잡도는 O(nm) (m<20)이므로 O(n ^2)보다 빠름 

 

 

 

둘다 이중 for문을 사용하고 접두어를 찾으려고 비교하는데 왜 효율성 통과에서 차이가 날까? 

 

https://school.programmers.co.kr/questions/39655

프로그래머스

 

이 글을 참고하였다. 

 

 

+추가

 

3)

import java.util.Scanner;
import java.util.Arrays;


class Solution {
    public boolean solution(String[] phone_book) {
        Scanner sc = new Scanner(System.in);
        
        Arrays.sort(phone_book); //sort 
        boolean answer = true;
        
        for(int i=0;i< phone_book.length-1; i++){
        
            if(phone_book[i+1].startsWith(phone_book[i])){ //이 부분! 
                    answer=false;
                    break;
                }
        }
        
        return answer;
    }
}

 

그런데 스터디에서 코드 풀이를 보다가, 1번 방법과 유사하게 푸셨는데 통과하셔서 한 번 살펴봤다. 

이중 for문에서 for문으로 줄었고, if부분 하나만 검사하게 된다. 

 

1번의 복잡도: O(n^2) 

2번의 복잡도: O(n*m^2) 

위의 복잡도: O(n*m) 복잡도! 

**** 문제를 분석해야한다.

 

ex) 12, 123, 1235, 567, 88케이스에서, 12를 접두어로 가진 것은 123과 1235 둘이지만, 둘 다와 비교할 필요가 없다. 하나라도 접두어라면 false가 되며, sort되면 string 오름차순대로 나열되기 때문에 바로 다음 것만 비교해주면 된다. 따라서 모두 비교할 필요가 없음! 

 

 

 

 

 

🥞문제풀이할때, 필요한 것들을 작성해보자! 

🥞해시와 친해지자! 

 

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL