TIL (2022.02.15)

➕ 오늘 푼 문제

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

➕ 아이디어

• 전화번호 목록을 문자순으로 정렬한다.
  • 문자순으로 정렬하는 이유는 바로 옆에 있는 숫자하고만 비교하기 위해서이다.
  • 만약에 접두어가 되는 관계가 있다면, 그 둘은 앞부분이 같기 때문에 정렬했을 때 바로 옆에 올 수 밖에 없다.
• 각자 바로 옆에 있는 전화번호와 비교하며, 한 번호의 접두어인지 확인한다.
  • 길이가 짧은 번호를 기준으로 모든 번호가 같다면, 그 번호는 다른 번호의 접두어이다.
  • 정렬될 때 접두어가 있다면, 긴 문장이 뒤로 간다. 그리고 접두어가 없다면 초반에 break 문에서 짤린다. 그래서 이 문제의 경우 i와 i+1 번째를 비교할 때, i를 짧은 번호로 봐도 무방하다.

➕ Java 코드

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        
        for(int i=0; i<phone_book.length-1; i++){
            int j = 0;
            for(j=0; j<phone_book[i].length(); j++){
                if(phone_book[i].charAt(j) != phone_book[i+1].charAt(j)){
                    break;
                }
            }
            
            if(j == phone_book[i].length()){
                return false;
            }
        }
        
        return true;
    }
}

➕ Python 코드

def solution(phone_book):
    phone_book.sort()
    
    for i in range(len(phone_book)-1):
        a = phone_book[i]
        b = phone_book[i+1]
        
        for j in range(min(len(a), len(b))):
            if a[j] != b[j]:
                break
        else:
            return False
                
    return True

➕ 궁금한 내용 및 소감

• 요새 매일 문제를 풀려고 노력하다보니, 간단하게 해결 아이디어가 떠올라 풀 수 있었다. 역시 알고리즘음 연습 만이 살길이라는 걸 다시 한번 느꼈다.
• 하지만 이 문제가 해시로 분류되어 있어, 해시로 푸는 방법도 생각해보면 좋을 것 같다.

➕ 참고 문헌

• 아이디어 - 해시 사용 방법
  • 참고 링크: [프로그래머스] 전화번호 목록 (해시 Lv. 2) - 자바 Java