[프로그래머스] 🔢 큰 수 만들기 / python

반응형

🔢 큰 수 만들기

😃 나의 코드

def solution(number, k):
    length = len(number)
    if length > k:
        m = 0
        for cnt in range(k):
            for idx in range(m, length-1):
                if number[idx] < number[idx+1]:
                    number = number[:idx] + number[idx+1: ]
                    length -= 1
                    if idx > 0:
                        m = idx-1
                    break
            else:
                number = number[:length-k+cnt]
                break
        return "".join([str(i) for i in number])
    else:
        return "0"

탐욕법^Greedy 알고리즘에 해당하는 문제입니다.

하지만, 탐욕법을 적용하고도, 특정 케이스(특히 10번 케이스)에서 시간 초과로 오류가 나 특정 예외 케이스를 찾아내는 것이 아닌 시간을 최대한 줄여야하는 문제입니다. 이 문제에서 가장 복잡도가 큰 예제는 다음과 같습니다.

number = "1234567890"*100000
k = 999999

처음에는 숫자를 비교하는 것이 빠르겠지라는 생각과 pop을 이용하는 것이 빠르겠지라는 생각에 [int(i) for i in number] 로 시작하고 list 는 pop 하는 방식으로 코드를 짰습니다.

하지만, 아무리 최적화를 해도 일정 시간 이하로 줄어들 지 않았습니다. ( 사실 핵심을 찾아내지 못하면 이런 최적화는 아무리해도 시간낭비입니다. )

결국 다른 풀이를 보았고, 결론을 말하자면 list의 길이가 무수히 길어지면, 숫자로 변환해서 숫자를 비교하는 것보다 문자를 비교하는 것이 더 빠릅니다. 심지어 문자열은 slicing과정까지 포함되었지만, 그걸 하고서도 이 전에 숫자로 변환한 케이스보다 시간이 약 2배 빨랐습니다.

하지만 Problem Solving 문제의 목적에 맞추려면 제가 한 최적화 정도에서는 답으로 처리하는 게 맞다고 생각합니다. 또한, 제가 생각한 예외 케이스도 테스트 케이스로 들어가지 않아서 문제에 개선이 좀 필요하다고 느껴집니다.

반응형

'Algorithm > Problem Solving' 카테고리의 다른 글

[프로그래머스] 🔢 큰 수 만들기 / python  (0)	2019.05.08
[프로그래머스] 🖨 프린터 문제 / python  (0)	2019.02.18
[프로그래머스] 👨‍💻 기능 개발 / python  (2)	2019.02.18
[프로그래머스] 👷‍♀️ 타일 장식물 / python  (0)	2019.02.18
[프로그래머스] 👨‍🏫 정수 삼각형 / python  (0)	2019.02.18
[프로그래머스] ⚾ 숫자 야구 / python  (4)	2019.02.15