![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
ํธ๋ ๋์ ์ฌ๊ณ ๊ณผ์ ๋ฐ ๊ฐ์ ์
์ฒ์์ ์ง์ง ๊ฐ์ด ์์กํ๋ค. ์ ๋์ด ์ฒ๋ฆฌ๋ฅผ ํด์ contains๋ฅผ ํ๋ฉด ๋ ๊ฒ ๊ฐ์๋ฐ, ์ด๊ฒ Hash๊ฐ ๋ง๋?? ์ด๋ฐ ์๊ฐ์ด ๋จธ๋ฆฌ ์์ ๋งด๋์๋ค.
import java.util.*; class Solution { public boolean solution(String[] phone_book) { boolean answer = true; TreeSet<String> ts = new TreeSet(); for(String phone: phone_book){ ts.add(phone); } // ๊ฐ ์ ํ๋ฒํธ์ ๋ชจ๋ ์ ๋์ด๋ฅผ ํ์ธ for (String phone : phone_book) { for (int i = 1; i < phone.length(); i++) { // ๊ธธ์ด๋ 1์ด์ String prefix = phone.substring(0, i); if (ts.contains(prefix)) { answer = false; } } } return answer; } }
2์ค ํฌ๋ฌธ์ ์ด์ฉ ์ ์๋ ๊ฒ ๊ฐ๋ค. ๊ทธ๋๋ contains๋ก ํด์ ์กฐํ ๋ O(1)์ ํด์ค์ ์ข ๋น ๋ฅธ ๊ฒ ์๋๊น
์ค๋ณต๋ ๋ฒํธ๊ฐ ์์ผ๋๊น HashSet์ ๋ฃ์ด์ ์กฐํ ์ฑ๋ฅ์ ์ฌ๋ ค์ฃผ๊ณ , ๊ฐ ๋ฒํธ๋ฅผ ๋๋ฉด์ substring์ ์๋ผ ์ด๊ฒ HashSet์ ์กด์ฌํ๋ ๊ฒ์ธ์ง ์ฐพ๋๋ค. ์ด๋ฌ๋ฉด ์กด์ฌํ ๊ฒฝ์ฐ ์ ๋์ด๊ฐ ์๋ Set์ด ๋๋ค.
# ์ถ๊ฐ ๊ณต๋ถ
substring์ [ startIndex, endIndex )
๋ค. ์ด์, ๋ฏธ๋ง์ด๊ธฐ ๋๋ฌธ์ ์ฃผ์ํด์ผ๋๋ค.
๋์์ด ๋๋ค๋ฉด ๋๊ธ์ด๋ ๊ณต๊ฐ ๋ฒํผ ํ ๋ฒ์ฉ ๋๋ฅด๊ณ ๊ฐ์ฃผ์ธ์!
'OJ๐ผ > Programmers ๊ณ ๋์ ํท' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[LV.2][JAVA] ์ฌ๋ฐ๋ฅธ ๊ดํธ (0) | 2024.08.28 |
---|---|
[LV.3][JAVA] ๋ฒ ์คํธ ์จ๋ฒ (0) | 2024.08.27 |
[LV.2][JAVA] ๋ ๋งต๊ฒ (0) | 2024.08.27 |
[LV.1][JAVA] ์์ฃผํ์ง ๋ชปํ ์ ์(feat. TreeMap) (0) | 2024.08.25 |
[LV.1][JAVA] ํฐ์ผ๋ชฌ(feat. TreeSet ์์๋ณด๊ธฐ) (0) | 2024.08.25 |