[프로그래머스][Java] 전화번호부 - 문제 풀이 및 팁

https://programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

 

문제요약

리스트에 주어진 어떤 한 전화번호가 다른 전화번호의 prefix에 포함되는지 여부를 반환

 

풀이

1. 전화번호부 정렬

2. 다음 전화번호와 비교

접두어를 포함(false)면 break

 

소스코드

https://github.com/999inim/Algorithm/blob/main/programmers/PS40.java

---

API정리 및 팁

1. 제한 사항의 의미

"phone_book의 길이는 1 이상 1,000,000 이하"

2중 for문으로 순회하면 시간복잡도 O(1,000,000^2)으로 시간초과를 예상해야함

 

---

2. 문자열 정렬

Arrays.sort의 정렬하는 요소가 문자열인 경우 아스키코드 순서대로 정렬됨

그 덕분에 이중 for문을 없앨 수 있었음.

아스키코드 표

 

3. 문자열을 char 배열로 변경

char[] cArr = 문자열.toCharArray();

 

4. 문자열 찾기 (contains vs indexOf vs startsWith)

대상문자열.contains("찾는문자열");
// 대상문자열에 찾는문자열이 포함되어있는지 여부를 확인. 대소문자를 구분

대상문자열.indexOf("찾는문자열");
//대상문자열에 찾는문자열이 포함된 위치(인덱스) 확인. 없으면 -1 반환.

대상문자열.startsWith("특정문자열");
//대상문자열이 특정문자열로 시작하는지 여부 반환.

 

endsWith, matches(정규식) ...

---

느낀점

- 해시 유형이었던 문제 ...

- 최적화된 풀이방식 ~ 떠오른 아이디어로 바로 풀기

- 아이디어가 멤도는 단계에서는 가능하면 코드구현 지양 -> 구체화 시간 할당