[프로그래머스 / 해시 / 자바(JAVA)] 전화번호 목록

코딩테스트 - 프로그래머스/JAVA

[프로그래머스 / 해시 / 자바(JAVA)] 전화번호 목록

읁; 2024. 5. 9. 17:50

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

[ 요약 ]

시작 시각 : 16:09

종료 시각 : 17:14

소요 시간(분) : 65분

도전 횟수 (제출 횟수) : 10...^^

로직 및 풀이 참고 여부 : X

[ 풀어보기 ]

▶ 정답 풀이로 바로가기◀

오답 풀이 1

📌 로직

phone_book 을 처음부터 끝까지 순회하는 확장 for문을 이중으로 만든다.
- 겉 for문의 요소는 String a에 하나씩 담고, 속 for문의 요소는 String b에 하나씩 담는다.
- 만약, b와 a + b.replace(a,"") 가 같으면 false를 반환한다.
- 끝까지 다 돌고나서는 true를 반환한다.

📌 코드

class Solution {
    public boolean solution(String[] phone_book) {

        for(String a : phone_book) {
            for(String b : phone_book) {
                if(a.equals(b))
                    continue;
                if(b.equals(a + b.replace(a,"")))
                    return false; 
            }
        }
        
        return true;
    }
}

📌 채점 결과

정확성  테스트
테스트 1 〉	통과 (1.41ms, 70.5MB)
테스트 2 〉	통과 (1.88ms, 79.3MB)
테스트 3 〉	통과 (1.42ms, 72.3MB)
테스트 4 〉	통과 (1.17ms, 76MB)
테스트 5 〉	통과 (1.56ms, 78.6MB)
테스트 6 〉	통과 (1.69ms, 73.3MB)
테스트 7 〉	통과 (1.53ms, 73.2MB)
테스트 8 〉	통과 (1.32ms, 75.8MB)
테스트 9 〉	통과 (1.31ms, 71.2MB)
테스트 10 〉	통과 (1.92ms, 73MB)
테스트 11 〉	통과 (1.88ms, 77.6MB)
테스트 12 〉	통과 (1.58ms, 73.5MB)
테스트 13 〉	통과 (2.08ms, 75.8MB)
테스트 14 〉	통과 (165.95ms, 103MB)
테스트 15 〉	통과 (76.92ms, 94.5MB)
테스트 16 〉	통과 (288.75ms, 158MB)
테스트 17 〉	통과 (361.13ms, 229MB)
테스트 18 〉	통과 (426.00ms, 312MB)
테스트 19 〉	통과 (460.88ms, 356MB)
테스트 20 〉	통과 (505.22ms, 367MB)

효율성  테스트
테스트 1 〉	통과 (13.55ms, 57.2MB)
테스트 2 〉	통과 (15.62ms, 58MB)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)

채점 결과
정확성: 83.3
효율성: 8.3
합계: 91.7 / 100.0

오답 풀이 2

📌 로직

replace를 쓰지 말고 substring을 써볼까?
- b를 0 ~ a.length() 까지 자르고,
- 이걸 a와 비교하자!
그러려면 a.length() < b.length() 여야 하니까 phone_book을 길이순으로 정렬하자.

📌 코드

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {

        Arrays.sort(phone_book, (x1, x2) -> x1.length() - x2.length());
        	// 길이순으로 정렬하기

        for(int i=0; i<phone_book.length; i++) {
            int lth = phone_book[i].length();
            
            for(int j=i+1; j<phone_book.length; j++) {
                if(phone_book[i].equals(phone_book[j].substring(0, lth)))
                    return false;
            }
        }
        
        return true;
    }
}

📌 채점 결과

정확성  테스트
테스트 1 〉	통과 (0.51ms, 78MB)
테스트 2 〉	통과 (0.49ms, 71.8MB)
테스트 3 〉	통과 (0.39ms, 73.6MB)
테스트 4 〉	통과 (0.50ms, 76.2MB)
테스트 5 〉	통과 (0.46ms, 74.2MB)
테스트 6 〉	통과 (0.70ms, 76.6MB)
테스트 7 〉	통과 (0.45ms, 81.4MB)
테스트 8 〉	통과 (0.43ms, 76.1MB)
테스트 9 〉	통과 (0.56ms, 74.9MB)
테스트 10 〉	통과 (0.44ms, 75MB)
테스트 11 〉	통과 (0.47ms, 75.6MB)
테스트 12 〉	통과 (0.44ms, 71.6MB)
테스트 13 〉	통과 (0.71ms, 74.9MB)
테스트 14 〉	통과 (25.90ms, 95MB)
테스트 15 〉	통과 (33.77ms, 104MB)
테스트 16 〉	통과 (20.99ms, 77.5MB)
테스트 17 〉	통과 (24.23ms, 81.8MB)
테스트 18 〉	통과 (75.46ms, 128MB)
테스트 19 〉	통과 (131.15ms, 142MB)
테스트 20 〉	통과 (157.26ms, 209MB)

효율성  테스트
테스트 1 〉	통과 (9.71ms, 56.5MB)
테스트 2 〉	통과 (14.98ms, 56.4MB)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)

채점 결과
정확성: 83.3
효율성: 8.3
합계: 91.7 / 100.0

오답 풀이 3

📌 로직

substring 말고 startsWith를 사용하자.
길이 순 정렬말고, 그냥 정렬을 해버리자.
- {"234", "567", "1234", "12", "123"} 을 정렬하면
- {"12", "123", "1234", "234", "567"} 이 되므로, 접두어인 경우를 더 빨리 찾을 수 있을거야.

📌 코드

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {

        Arrays.sort(phone_book);

        for(int i=0; i<phone_book.length; i++) {
            for(int j=i+1; j<phone_book.length; j++) {
                if(phone_book[j].startsWith(phone_book[i]))
                    return false;
            }
        }
        
        return true;
    }
}

📌 채점 결과

정확성  테스트
테스트 1 〉	통과 (0.26ms, 76.2MB)
테스트 2 〉	통과 (0.24ms, 83.5MB)
테스트 3 〉	통과 (0.19ms, 73.7MB)
테스트 4 〉	통과 (0.31ms, 76.6MB)
테스트 5 〉	통과 (0.33ms, 71.6MB)
테스트 6 〉	통과 (0.22ms, 76.1MB)
테스트 7 〉	통과 (0.61ms, 76.3MB)
테스트 8 〉	통과 (0.26ms, 74.4MB)
테스트 9 〉	통과 (0.19ms, 77.1MB)
테스트 10 〉	통과 (0.17ms, 83.3MB)
테스트 11 〉	통과 (0.30ms, 78.7MB)
테스트 12 〉	통과 (0.28ms, 75.8MB)
테스트 13 〉	통과 (0.19ms, 74.9MB)
테스트 14 〉	통과 (15.14ms, 70.7MB)
테스트 15 〉	통과 (12.50ms, 78.4MB)
테스트 16 〉	통과 (18.38ms, 77.4MB)
테스트 17 〉	통과 (19.55ms, 81MB)
테스트 18 〉	통과 (38.85ms, 87.1MB)
테스트 19 〉	통과 (17.49ms, 86.3MB)
테스트 20 〉	통과 (58.11ms, 92.6MB)
효율성  테스트
테스트 1 〉	통과 (17.77ms, 56.7MB)
테스트 2 〉	통과 (17.98ms, 56.1MB)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
채점 결과
정확성: 83.3
효율성: 8.3
합계: 91.7 / 100.0

정답 풀이

📌 로직

먼저, phone_book을 정렬한다.
- {"234", "567", "1234", "12", "123"} 을 정렬하면
- {"12", "123", "1234", "234", "567"} 이 된다.
이렇게 정렬해줬기 때문에
phone_book[i] 로 시작하는 가장 가까운 다른 요소는 phone_book[i+1] 이 된다!
1. phone_book[i+1]이 phone_book[i]로 시작하지 않는다면,
  그 뒤 다른 요소들 또한 당연히 phone_book[i]를 접두어로 가지지 않는다.
그러므로 phone_book[i+1] 이 phone_book[i] 로 시작하는지 startsWith를 통해 알아내면 된다.
- 오답풀이 3에서는 이중 for문을 써서, phone_book[i] 로 시작하는 phone_book[j]가 있는지 없는지 전체를 순회했다. 그럴 필요가 전혀 없었던 것!

📌 코드

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++) {
            if(phone_book[i+1].startsWith(phone_book[i]))
                return false;
        }
        
        return true;
    }
}

📌 채점 결과

정확성  테스트
테스트 1 〉	통과 (0.28ms, 70.9MB)
테스트 2 〉	통과 (0.24ms, 75.2MB)
테스트 3 〉	통과 (0.28ms, 77.4MB)
테스트 4 〉	통과 (0.25ms, 71.4MB)
테스트 5 〉	통과 (0.32ms, 85MB)
테스트 6 〉	통과 (0.21ms, 66.6MB)
테스트 7 〉	통과 (0.20ms, 75.9MB)
테스트 8 〉	통과 (0.28ms, 70.9MB)
테스트 9 〉	통과 (0.20ms, 70.7MB)
테스트 10 〉	통과 (0.17ms, 78.5MB)
테스트 11 〉	통과 (0.25ms, 74.2MB)
테스트 12 〉	통과 (0.22ms, 74.2MB)
테스트 13 〉	통과 (0.22ms, 75.6MB)
테스트 14 〉	통과 (2.40ms, 74.1MB)
테스트 15 〉	통과 (3.21ms, 68.3MB)
테스트 16 〉	통과 (3.00ms, 77.2MB)
테스트 17 〉	통과 (3.79ms, 72.9MB)
테스트 18 〉	통과 (3.86ms, 76.8MB)
테스트 19 〉	통과 (5.82ms, 84.7MB)
테스트 20 〉	통과 (5.23ms, 84.9MB)

효율성  테스트
테스트 1 〉	통과 (19.79ms, 57.8MB)
테스트 2 〉	통과 (19.17ms, 57.7MB)
테스트 3 〉	통과 (409.29ms, 97.7MB)
테스트 4 〉	통과 (798.12ms, 96.6MB)

채점 결과
정확성: 83.3
효율성: 16.7
합계: 100.0 / 100.0