파이썬_고득점키트_문제풀이(3)

3. 정렬 대표 문제 풀이 : 가장 큰 수

정렬 . sorting 문제
sort를 할 때, 수의 대소 관계, 문자열의 사전 순서가 아니라. 우리가 정한 기준에 의해 배열을 정렬할 수 있으면 해결 가능한 문제
0 또는 양의 정수가 주어졋을 때, 정수를 이어 붙여서 만들 수 있는 가장 큰 수를 알아내라.
[6,10,2]라면 10이 가장 큰 수 이지만, 10부터 1062보다 쓰는 것 보다 문자열로 판단하면 6210로 붙여서 리턴하도록 한다.
제한사항에 보면, 정답이 너무 클 수 있으니, 문자열로 바꾸어 return 해야한다.
원소는 0부터 시작해서 1000이하다. 즉 길어봐야 4글자다.

문제의 해결방법

빈 문자열로 수를 초기화한다.
가장 크게 만들 수 있는 수를 고른다.
그 수를 현재 수에 이어 붙인다.
모든 수를 다 사용할 때까지 반복하낟.

예제의 적용
[3,30,34,5,9]
””
“9”
“95”
“9534”
“95343”
“953430”
각 단계에서, 목록 안에 들어있는 것 중에 가장 수를 크게 만들 것을 고르는 작업이.
목록의 길이에 비례한다.
그리고 그 단계를 목록 안에 들어있는 수의 갯수만큼 실행해야 한다.
주어진 수가 n이라면, n^2의 복잡도를 가진다.
문제의 제목에서 알 수 있듯이, 이 때 할 수 있는 방법이 -> 정렬.

조금 나은 문제의 해결 방법

빈 문자열로 수를 초기화한다.
수의 목록을 (크게 만드는 것 우선으로) 정렬한다.
목록에서 하나씩 꺼내어 현재 수에 이어 붙인다.
모든 수를 다 사용할 때까지 반복한다.

n*logn의 복잡도를 가진다.
문제는, 수의 목록을 정렬할 때, 작은 것으로부터 큰 것, 혹은 큰 것부터 작은 것들로 정렬한다.
여기서는 그 기준이 정수의 대소관계가 아닌, 결과의 수를 크게 만드는 것 우선으로 정렬 해야한다.
정렬에 사용되는 기준을, 문자열로 취급했을 때, 이어 붙이면 앞에 나와서 결과의 수를 크게 만들 것의 기준을 적용해야 한다.

“크게 만드는 수”의 기준

3
32
33
34
네 개의 수가 주어져 있다고 가정.
수가 길이가 같으면, 큰 게 우선이다.
한글자 짜리 3과 32,33,34를 비교할 때는?
3 vs 32 : 332 vs 323. 즉 3을 골라야 한다.
3 vs 33 : 333 vs 333 -> 같다.
3 vs 34 : 334 vs 343 -> 34가 더 크다.
길이가 모두 같으면 큰 수를 고르면 되지만, 앞자리가 똑같을 때는 어디를 골라야 할까?
34
342
343
344
34 vs 343 : 34343 vs 34334 -> 34를 골라야 한다.
34의 경우에는 결과의 수를 가장 크게 만드는 것 우선으로, 정렬이 다 되어 있다고 가정하면, 34보다 뒤에 올 수 있는 건 커 봐야 34를 넘지 못한다.
343434343434343434 …
343343343343343343 …
길이를 어디까지 비교해봐야 하나 ?
문제의 제약사항에서 길어봐야 4글자까지다.
python 정렬 알고리즘에서 key를 무엇을 ? 이 방법을 사용하려고 한다.

알고리즘의 설계 -> 구현

nlogn의 복잡도를 가지는 정렬 알고리즘 구현.
정렬의 기준 필요
대소 관계 비교를 위한 기준을 마련
이것을 이용하여 주어진 배열을 정렬
정렬된 배열을 이용하여 문자열 표현을 완성

Python 풀이 예제보기

def solution(numbers):
    numbers = [str(x) for x in numbers]  # 문자열로 취급을 하고 싶으니, numbers로 리스트 작성
    numbers.sort(key=lambda x: (x*4)[:4], reverse=True)
    answer = ''.join(numbers)  # join method를 통해 문자열을 이어붙인다
    return answer


print(solution([3, 30, 34, 5, 9]))

list comprehension을 이용하면 두줄을 한 줄로 바꿀 수도 있다.

 numbers = sorted([str(x) for x in numbers],
                     key=lambda x: (x*4)[:4], reverse=True)

위 코드를 실행하면, 테스트 케이스 마지막에서 실패한다.
마지막 제약 사항을 보면 numbers의 원소는 0이상 1000이하라고 했다.
만약, 0이 2개 이상 주어진 배열이라면, 이 때는, 그 0000을 리턴하면 답이 아니고, 0 한글자로 이루어진 문자열을 리턴해야 한다.
이를 조건으로 걸어줘야 한다.

def solution(numbers):

    numbers = [str(x) for x in numbers]  # 문자열로 취급을 하고 싶으니, numbers로 리스트 작성
    numbers.sort(key=lambda x: (x*4)[:4], reverse=True)
    if numbers[0] == "0":
        answer = '0'
    else:
        answer = ''.join(numbers)  # join method를 통해 문자열을 이어붙인다
    return answer

print(solution([3, 30, 34, 5, 9]))

python 코드의 복잡도도 살펴보자.
맨 먼저, solution 함수에 들어온 뒤에, list comprehension을 사용 numbers에 비례
그 뒤에 전체를 지배하고 있는 것은 number를 정렬하고 있는 부분
key를 무엇으로 지정했든 간에, 원소들의 대소관계를 이용해서 주어진 배열을 정렬하는데 쓰이는 시간복잡도는 nlogn이 걸린다.
if 조건이 참이면 대입이므로 상수시간
else 절에는 numbers라는 리스트의 모든 원소들을 조인해서 새로운 문자열로 만들어서 answer에 담고 있다. 이 또한 numbers에 들어있는 원소의 갯수에 비례한다. 결국은 numbers가 우리에게 인자로 주어졌을 때, 그 안에 수의 개수를 문제의 크기 n으로 정의할 수 있고 결국 n에 비례한다.

def solution(numbers):
    numbers = sorted(map(str, numbers),
                     key=lambda x: (x*4)[:4], reverse=True)
    if numbers[0] == "0":
        answer = '0'
    else:
        answer = "".join(numbers)
    return answer
print(solution([3, 30, 34, 5, 9]))

참고사항

lambda: 메모리를 아끼고 가독성 향상, 한번 쓰이고 나면 힙 메모리 영역에서 증발
map을 사용하면, 게으른 연산을 진행해서 메모리 크게 절약 가능
map은 iterator 객체를 반환한다.
게으른 연산이란 필요할 때, 가져다 쓴다 (ex: map 함수의 결과 객체)
iterator 객체 : next() method로 순차적으로 호출이 가능하다.
마지막 데이터까지 불러오면 다음은 stopiteration exception을 발생시킨다
iterable한 객체를 iterator로 변환하고 싶다면 iter()라는 내장 함수 이용
for문으로 looping 하는 동안 python내부에서는 임시로 list를 iterator로 자동 변환

# ex1.
li = [1, 2, 3]
result = map(lambda i: i * i, li)
next(result) # 1
next(result) # 4
next(result) # 9
next(result) # StopIteration 발생

# ex2.
>>> x = [1,2,3]
>>> type(x)
<class 'list'>
>>> y = iter(x)
>>> type(y)
<class 'list_iterator'>

조건이 3개일 경우에도 3항 연산자 사용 가능하다.
filter 함수 (함수, iterable): 반복가능한 자료형 요소들을 첫번쨰 인자 함수에 하나씩 입력하여, 참인 것만 묶어서 돌려준다.

참고자료 [프로그래머스]https://programmers.co.kr/learn/courses/9877 [iterator객체]https://wayhome25.github.io/cs/2017/04/03/cs-03/