프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
이해하기
처음에는 너무 쉽지 않나? 하고 막~ 풀었는데 효율성 빵점 맞았다.
첫 풀이는 이중 for문 돌리면서 자신이 아닌 다른 문자열들을 .startsWith()로 검사했다.
결과는 실패, 시간 초과 ㅜㅅㅜ
제한 사항을 보니 phone_book의 길이가 최대 1,000,000 이라 이중 for문을 돌리면 너무 오래 걸리게 된다.
참고한 블로그⬇️
[프로그래머스] 전화번호 목록 (해시 Lv. 2) - 자바 Java
0. 동일 유형 문제 [프로그래머스] 완주하지 못한 선수 (해시 Lv. 1) [프로그래머스] 전화번호 목록 (해시 Lv. 2) [프로그래머스] 위장 (해시 Lv. 2) [프로그래머스] 베스트 앨범 (해시 Lv. 3) Youtube 영상으
coding-grandpa.tistory.com
- HashMap에 전화번호를 전부 저장한다.
- phone_book을 순회하며 접두어가 존재하는지를 map과 비교하여 찾는다.
예를 들어 {"119", "11954"} 라는 phone_book이 존재한다고 생각해보자.
HashMap에는 다음과 같이 저장될 것이다.
이제 phone_book을 순회하며 접두어의 존재 여부를 map과 비교한다.
"119"의 접두어를 찾는 방식은 다음과 같다.
앞에서부터 substring하며 해당 값이 map에 존재하는지 비교한다.
접두어이니 119 전체를 비교할 일은 없도록 해야하기에 "1", "11" 까지만 비교한다.
그 다음 "11954"를 가지고 접두어의 존재 여부를 확인해보자.
"1"은 map에 없고, "11"도 map에 없는데 "119"는 map에 존재한다.
접두어가 존재하는 것이라고 판단하면 된다.
문제풀이
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < phone_book.length; i++) {
map.put(phone_book[i], i);
}
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))) {
return false;
}
}
}
return answer;
}
}
이번에도 이중 for문이 있는데도 불구하고 시간초과가 나지 않는 이유는 1,000,000 * 1,000,000 이 아니라 1,000,000 * 20 만 하면 되기 때문이다.
(전화번호의 길이는 최대 20이기 때문)
'JAVA > Coding Test Study' 카테고리의 다른 글
[Lv.0] 프로그래머스 - ad 제거하기 : Java (0) | 2024.04.16 |
---|---|
[Lv.2] 프로그래머스 - 가장 큰 수 : Java (0) | 2024.04.16 |
[Lv.2] 프로그래머스 - 튜플 : Java (0) | 2024.04.15 |
[Lv.2] 프로그래머스 - H-Index : Java (0) | 2024.04.15 |
[Lv.3] 프로그래머스 - 단속카메라 : Java (0) | 2024.04.15 |