[코테준비] 입문자를 위한 알고리즘 해결전략 - 2

프로그래머스 > 해시 > 전화번호 목록

큰 그림

시간 복잡도 O(n^2) 테스트 1,5,6,7,11 실패 & 효율성 성공 => ["123", "01230"]에서
java.lang.StringIndexOutOfBoundsException: begin 0, end 5, length 3 에러가 뜬다. 왠지 소트를 할 때 기준을 문자열 자릿수가 아닌,
숫자 값으로 정수 비교를 한 것 같다...? 소팅 결과가 분명 01230, 123 이렇게 되었기 때문에 저 에러가 뜬 것이 분명하다.

 

벽을 넘자

그래서 sort를 문자열 길이 기준으로 할 수 있을까 생각을 해서 구글링을 해보았는데 compare로 사용자 정의 메서드를 이용해서 만들어야 해서 복잡해질뿐더러, 내가 원하는 기능을 추가하는 것이 제한시간 안에 구현하는 것은 손해라는 판단을 하였다. 그래서 다시 생각을 해보았다.
만약, 123, 01230이라는 문자열 두 개가 정렬을 통해서 내가 의도한 123, 01230 이 아닌 01230, 123 순으로 되었다고 가정을 해보는 거다. 저런 상황이 발생하는 경우는 아무리 생각을 해봐도 딱 한 경우이다. 바로 숫자의 가장 앞자리가 '0'인 경우이다. 즉, sort 함수가 문자열을 정렬할 때, 그 문자열의 자료형이 이처럼 정수인 경우에 앞에 자리가 0인 경우에 0을 제외한 나머지 값을 기준으로 정렬을 한다고 가정을 하게 되면, 저런 식으로 01230, 123 이런 식으로 되려면 무조건 결국 앞에 오는 애가 뒤에 오는 숫자보다 1230>123 이런식으로 큰 숫자일 수밖에 없다. (더 이상 설명이 불가능하다.. 머리로는 직관적으로 한 번에 이해가 되는데 말로 설명하기가 애매... 아직 표현력이 머리를 못 따라오는 느낌이다..)

그래서 나는 위의 코드에서 보듯이 @1 조건을 추가하여 해당 경우를 완전히 배제해 버렸다. 왜냐하면, 앞에서 설명했듯이 이 경우는 뒤에 오는 문자열이 앞에 오는 문자열의 접두어가 될 수 없는 상황이기 때문이다.
이렇게 세팅을 하고 다시 제출을 해본 결과 정답이 떴다.

 

<효율성 테스트 결과 - 1>

 

 

😂총 38분 경과... 해결 완료! 978점 획득!! 

 

깨달음

처음에 10분 정도 스케치한 큰그림 방식인 저 설계방식이 시간복잡도가 O(n^2) 이어서 분명 효율성테스트에서 떨어질 것이라고 예상했다.
그리고 10분정도 더 효율적인 시간 복잡도를 가지는 설계 방식을 고안해 보았지만, 딱히 떠오르는 방식이 없었다. 그래서 남은 40분 동안 목표로 한 큰 그림만이라도 구현해야겠다는 생각으로 손으로 백지장에 의사 코드를 짠 후, 그 후에 substring, str.length 등 세부적인 코드를 완성하였다. 실패한 테스트 케이스에 대해 '질문'란을 찾아보며 테스트 케이스를 추가했고, 여기서 문제점이 뭔지 발견하라 수 있었다.(String array 개수 exception)  다른 사람의 풀이(해시를 이용한 풀이)를 보며 더 공부를 해야겠다.

 

🏃‍♂️일단 러닝을 하고 와야겠다🏃‍♂️

 

[러닝일지] 러닝 복귀 6일차

 

 

5/08 추가
다른 풀이를 찾아보았다.. 

 

sort 사용 + for문 1개 풀이 시간복잡도 O(n) 

5/09 에 다시 보니 이해가 갔다. 시간복잡도가 O(n) 인 풀이이다. 처음에 sort 를 했기 때문에, sort를 한 후의 인접한 두 문자열이 반드시 앞에 문자 1개이상이 같다(조금만 생각을 해보면 알 수 있다).

 

sort + startWith 를 사용한 풀이 시간복잡도 O(n) 가장 효율적

<효율성 테스트 결과 - 2>

<효율성 테스트 결과 - 1> 보다 훨씬 효율이 높아진 것을 확인 할 수 있다. 왜냐하면 시간복잡도가 O(n^2) 에서 O(n)이 되었기 때문이다. 이 풀이는, 바로 앞의 풀이와 startWith 메서드를 결합하여 내가 새로 만들어낸 풀이이다.

 

 

 

5/09 복습

String sort 원리 깨달음

위의 코드를 보면 알 수 있듯이, String 을 sort로 정렬할 때에는, 최상단 숫자부터 하나씩 비교해 나가는 것을 알 수 있다. 그래서 운이 좋게도 접두어를 골라내기 편한 구조로 변경되었던 것이다.