[Java] 전화번호 목록

allzeroyou·2025년 1월 18일
0

Java-Algorithm

목록 보기
3/26

https://school.programmers.co.kr/learn/courses/30/lessons/42577?language=java

  • 풀이를 위해 생각한 점

전화번호가 다른 전화번호의 시작번호라면 -> false 반환
없으면 true 반환

  1. 오름차순 정렬
  2. 첫번째 요소 -> n-1까지 요소까지 돌면서 접두어 있는지?
  • 피드백

자바에서 문자열 처리 시 phone_book[i+1][j] 이렇게 접근할 수 없고, String에서 특정 문자에 접근하려면 charAt() 메서드를 사용한다.
이때, 문제처럼 문자열의 접두어인지 아닌 지 확인하려면 startsWith() 메서드가 더 효율적임.

1차 시도: CharAt() 사용 (정답)


import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        
        
        // 1. 정렬
        Arrays.sort(phone_book);
        // 2. for문 순회하면서 접두어 탐색
        for (int i=0; i<phone_book.length -1; i++){
            String cur = phone_book[i];
            String nxt = phone_book[i+1];
            
            // 만약 다음 문자열이 더 짧다면 접두어 불가
            if(nxt.length() < cur.length()){
                continue;
            }
            // charAt()으로 문자열 인덱스 비교
            boolean answer = true;

            for(int j=0; j<cur.length(); j++){
                if(cur.charAt(j) != nxt.charAt(j)){
                    answer = false;
                    break;
                }
            }
            if(answer){
                return false;
            }
        }
        return true; // 접두어 아니라면 true 반환
    }
}

2차 시도: startsWith() 사용 (정답)

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        // 1. 오름차순 정렬
        Arrays.sort(phone_book);
        
        for(int i=0; i<phone_book.length -1; i++){
            if(phone_book[i+1].startsWith(phone_book[i]))
                return false;
        }
        return answer;
    }
}

3차 시도: HashMap 사용 (정답)

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        // HashMap 사용
        HashMap<String, Integer> map = new HashMap<>();
        
        // 1.전화번호부 만들기
        for(int i=0; i<phone_book.length; i++){
            map.put(phone_book[i], 1);
        }
        
        // 2.현재 전화번호의 접두어가 map 에 있는지 체크.
        for(int i=0; i<phone_book.length; i++){
            // 접두어의 길이 결정
            for(int j=1; j<phone_book[i].length(); j++){
                // 전화번호에서 접두어가 포함되는지 체크: substring
                if(map.containsKey(phone_book[i].substring(0,j))){
                    return false;
                }
            }
            
        }
         
        return answer;
    }
}

문제풀이

  1. 전화번호부에 대한 HashMap을 만든다.
    가령, ["119", "97674223", "1195524421"] 라면 {"119"=1, "97674223"=1, "1195524421"=1} 이
    렇게!
  2. for문을 돌면서 현재 전화번호의 접두어가 map에 있는지 체크한다.
    이때, 확인할 현재의 접두어 길이만큼 체크하기 위해 내부 for문(j)을 돈다.
  3. map에서 현재 접두어가 포함되는지(substring(0,j))로 확인한다.
profile
모든 건 zero 부터, 차근차근 헛둘헛둘

0개의 댓글