강의로 돌아가기
한장호

java - Arrays.sort에 관하여

안녕하세요!
Map 카테고리에 있어서 당연히 Map으로 풀어야지! 하는 생각에 Map을 사용하여 어찌 저찌 풀긴 했습니다.
근데 다른사람의 풀이를 보고 띠용 해버렸어요

  • 이중 포문으로 startsWith 메서드를 쓴 11줄 짜리 풀이 였는데,, 당연히 제 풀이가 빠를줄 알았는데 아니었습니다.

비교를 해보면 저의 풀이는

  • Arrays.sort => nlogn
  • 2중 for문 => n*20
  • nlogn + 20* n = nlogn

11줄짜리 풀이

  • 2중 for문 => n(n-1)/2
  • n^2

이렇게 시간복잡도를 계산해 보면 저의 풀이가 더 빨라야 할 것 같은데 (효율성 테스트 23.61 ms), 11줄짜리 풀이(효율성테스트 1.58ms)가 압도적으로 빠르더군요..

뭐가 문제일까.. 보다가 Arrays.sort를 빼버리니 시간이 확 줄어들더라고요(23.61 ms => 1.35 ms).(물론 test case를 100%로 통과하진 못했습니다.)

Arrays.sort가 그렇게 시간이 많이 걸리나요? 시간복잡도를 보면 nlogn이라 느린게 아닌데.... 2중포문으로 도는것 보다 느린 이유를 알고싶습니다..

보다가 보다가 이해가 안되서 질문글을 올려봅니다.(11줄 코드가 훨씬 깔끔하고 잘짠것 같아서 부들부들하며;;)

제가 잘못알고 있어서그런건가요??
지나가던 고수님 가르침을 주시기 바랍니다! 복받으세요!!

작성중인 코드―Solution.java
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
import java.util.*;

class Solution {
    Map<Character, Object> phoneMap2 = new HashMap<>();

    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book, Collections.reverseOrder());

        for(String phoneNumber : phone_book){
            boolean flag = false;
            Map<Character, Object> tmpMap = phoneMap2;
            for(int i = 0; i < phoneNumber.length(); i++){
                char tmp = phoneNumber.charAt(i);
                if(tmpMap.get(tmp) == null){
                    tmpMap.put(tmp, (Object)new HashMap<Character, Object>());
                    flag = true;
                }
                tmpMap = (HashMap)tmpMap.get(tmp);
            }
            if(flag == false) return flag;
        }

        return answer;
    }
}
  • 한인규
    소팅 보다는 전화번호들의 각 문자들을 체크하는 코드 땜에 시간에 걸리는것 같아요. for(int i = 0; i < phoneNumber.length(); i++) 요 부분 때문에 걸리는것 같아요 한인규 2019.03.28 19:56
0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.