일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 지능형 기차2
- imeOptions
- BFS
- EditorInfo
- hilt
- 완전탐색
- 약수 구하기
- 백준
- EditText
- 스카이라인 쉬운거
- 자바
- 최단경로
- 프로그래머스
- java
- val
- 시뮬레이션
- Android
- BuildConfig
- Parcelize
- 순열
- 백준 퇴사
- 순수함수
- dfs
- 2501
- 조합
- Kotlin
- SWEA
- Parcelable
- 오르막수
- 백준 14501
- Today
- Total
안드 공부를 해볼까?
[Java] 프로그래머스 전화번호 목록 본문
1. 문제 분석
전에 풀었던 완주하지 못한 선수와 비슷한 문제다.
하지만 이번 문제의 키워드는 접두어다. 필자도 접두어를 무시하고 그냥 구현했는데 계속 오류가 났다.
이번에도 해시를 사용하지 않아도 해결이 가능하지만 우리는 해시를 사용해보자(카테고리가 해시니깐..)
먼저 이번에도 고정되어야 하는 값을 찾아보자.
사실 이 문제는 어느 부분을 해도 상관이 없다고 생각한다. 접두어를 포함하는 것이니 contains를 사용할 것 이다.
HashMap은 containsKey와 containsValue가 존재하기 때문에 이번 문제는 어느부분을 넣어도 상관없다.
(사실 이렇게 되면 왜 HashMap을 써야하나 싶다. 2중 포문이라 시간 복잡도가 정말 나쁜데..)
접두어가 되니 앞글자 부터 하나씩 봐야한다. 만약 자신을 제외하고 나머지만 포함하는지 찾으면 어떻게 될까?
"1234"와 "11113321234"가 있다고 하자. 이렇게 되면 contains는 true가 나오게 된다.
우리가 찾고자 하는 것은 접두어다. 맨 앞에 오는 숫자이므로 subString으로 앞에서 부터 찾아보면 된다.
"119"와 "1193858343"를 보자. "119"를 기준으로 "1193858343"를 보면 앞에서 부터 1 -> 11 -> 119로 찾게 된다.
그러므로 true를 return한다. 이번 문제도 정말 쉽다.
2. 구현
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 (String s : phone_book) {
for (int j = 0; j < s.length(); j++) {
//데이터의 자릿수를 늘려가며 검색(9, 97, 976 ... 97674223)
if (map.containsKey(s.substring(0, j))) {
return false;
}
}
}
return answer;
}
}
먼저 HashMap에 데이터를 넣어주었다. 그 다음 phone_book의 데이터를 사용해서 subString을 사용한다.
앞에서 부터 한자리씩 나오면 되는 것이니 subString(0,j)를 사용했다.
subString의 작동방식이 이해되지 않는다면 밑의 링크를 보고 다시 해결해보자.
https://moonbari.tistory.com/21
3. 마무리
풀면 풀수록 이걸 왜 해시로..? 라는 생각이 든다.
그래도 HashMap을 좀 더 능숙하게 사용할려면 해야되나 싶기도 하고..
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[Java] 프로그래머스 피로도 (1) | 2022.09.21 |
---|---|
[Java] 프로그래머스 소수찾기 (1) | 2022.09.21 |
[Java] 프로그래머스 완주하지 못한 선수 (0) | 2022.05.14 |
[Java] 프로그래머스 큰 수 만들기 (0) | 2022.05.14 |
[Java] 프로그래머스 섬 연결하기 (0) | 2022.05.12 |