프로그래머스 LV 2 큰 수 찾기

문제 알고리즘 유형 : 정렬 

https://school.programmers.co.kr/learn/courses/30/lessons/42746

프로그래머스

1. 문제 해결 방법 

시간초과 풀이 및 Feedback

1) 첫 번째 풀이 방법 : 순열 사용 

첫 번째 방식으로는 순열 방법을 사용 했다.  먼저 numbers를 문자로 바꿔주고 이를 순열 처리 하면

('6' , '10' , '2' ) , ('6' , '2', '10')  이런 식으로 나온다. 그래서 join으로 합쳐준 뒤 숫자로 바꿔줘서 최댓값을 찾고

문제에서 요구한대로 문자로 다시 바꿔줘서 answer에 넣어주었다. 

순열 사용 코드

테스트는 통과 그러나 결과는 실패

시간복잡도가 O(N!) 나올 정도로 크기 때문에 실패했던 것 같다. 순열 처리로 쉽게 풀릴 거라 생각했던 터라 멘붕이 와서

고민하던 중 문자열끼리 비교를 어떻게 해야 할 지 모르겠어서 찾아본 결과 ASCII 코드로 크기를 비교하기 때문에 이 부분을 좀 더 생각해야 했다.

ex) [6 , 10 , 2]  문자로 변환 --> ['6',  '10' , '2']  --> ASCII 코드로 비교 , ( '6'[0] , '10'[0] , '2'[0] ) 이렇게 같은 인덱스 끼리 비교

 

그렇기 때문에 같은 인덱스끼리 비교해주는 과정을 위해 문제 요구사항에서 numbers 입력값은 1부터 1000이라 되어있으므로 문자열을 세 번 반복 해주고 비교 한다.  

['666' , '101'('101010') , '222'] 순으로 비교 할 수 있게 되었다. 이 방법을 생각한 사람들이 대단한 것 같다..! 

 

2) 두 번째 풀이 방법 : 문자열 반복 사용 

- lambda로 함수를 한 줄로 간결하게 해주었다. lambda에 대해서 많이 잊어먹은 상태이므로 다시 한 번 복습했다.

lambda 매개변수 : 표현식

>>> map(lambda x: x ** 2, range(5))             # 파이썬 2
[0, 1, 4, 9, 16]  
>>> list(map(lambda x: x ** 2, range(5)))     # 파이썬 2 및 파이썬 3
[0, 1, 4, 9, 16]

- sort로 내림차순 정렬 해주었다. sort(원본 변형)와 sorted(원본 변형 X) 모두 key와 parameter를 가지고 있다. 

key 값에는 정렬을 목적으로 하는 함수 값을 넣을 수 있다. lambda를 사용할 수 있음. 

parameter 값은 boolean 값이고 reverse=False(오름차순)가 기본값이다. reverse=True로 내림차순을 만들어줬다.

 str_numbers.sort(key=lambda x: x*3, reverse=True)

 그 후 그대로 int 형으로 바꿔주고 마지막 문제 요구사항에 맞춰서 다시 문자열로 바꿔주는 과정을 거쳤다. 

3. 최종 풀이 

최종 풀이

4. 느낀 점 

: 나는 생각보다 쉽게 순열로 푸는 방법을 생각했고 테스트도 통과해서 자신만만했는데 시간초과 이후로 어떻게 대처해야 할 지를 몰랐다. 사람들 풀이를 보고나서 깨달았는데 참 대단한 것 같다..ㅠ

: lambda와 sort에 대해 다시 한 번 배울 수 있는 시간을 가질 수 있었다. 

: 시간복잡도는 sort를 사용했으므로 퀵 정렬 방식인 O(NlogN)을 따라갈 것이며 공간복잡도는 N개의 숫자가 str_numbers에 문자열로 저장되므로 O(N)을 따라 갈 것이다. 

 

 

5. 참고 출처

: https://liveloper-jay.tistory.com/138

[프로그래머스] 가장 큰 수(python)

: https://ooyoung.tistory.com/59

파이썬 정렬 함수 sort, sorted _ key = lambda, function / reverse= 파라미터 이용 방법 (Python)

: https://wikidocs.net/64

3.5 람다(lambda)