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

/  제출 1  /

def solution(number, k):
    answer = ''
    i = 0
    final_len = len(number) - k
    
    while k > 0 and i < len(number) -1:
        if number[i] >= number[i+1]:
            answer += number[i]
            
        else:
            number = answer + number[i+1:]
            answer = ''
            k -= 1
            i = -1
        i += 1
    
    return number

채점 결과

정확성: 75.0

합계: 75.0 / 100.0

8, 10 시간 초과

12 실패

 

36분 소요.

 

흐으.. 풀 때도 인덱스를 약간 복잡하게 해서 푸는 느낌이어서 불안했는데 제출하니 역시 시간 초과에 실패도 뜨네요.

코드 문제점 찾고, 시간 초과 해결방안도 찾아보겠습니다.

 

오류 테스트케이스

입력값 〉	"3582912", 6
기댓값 〉	"9"
실행 결과 〉	실행한 결괏값 "92"이 기댓값 "9"과 다릅니다.

..? ㅎㅎ 거의 1분만에 오류 테스트케이스를 찾았습니다.

 

문제가 뭐였냐면, 종료 조건을 아래와 같이 줬는데,

왠만한 다른 테스트케이스는 k>0 조건으로 종료가 되었는데 해당 케이스는 k>0 조건 전에 i < len(number) -1 조건으로 종료가 되어버려 마지막 값을 확인을 못한 것입니다. 

while k > 0 and i < len(number) -1:

i < len(number) -1 조건을 준 이유는 i, i+1 검사 시에 마지막까지 갔을 때 빈 인덱스와 비교할까봐 그 제한 사항으로 넣어준건데 이렇게 문제가 꼬일 줄 고려 못했습니다.

수정해보겠습니다.

 

---

/  제출 2  /

 

def solution(number, k):
    answer = ''
    i = 0
    l = len(number) - 1
    
    while k > 0:
        if i >= l:
            number = answer
            break
        if number[i] >= number[i+1]:
            answer += number[i]
            
        else:
            number = answer + number[i+1:]
            answer = ''
            k -= 1
            i = -1
        i += 1
    
    return number

 

채점 결과

정확성: 83.3

합계: 83.3 / 100.0

 

12 실패 => 통과로 바뀌었습니다.

하지만 여전히 8, 10에서 시간초과가 나고

 

위에서 언급한 테스트케이스에서는 string index out of range가 나며 죽습니다.

 

---

/  퍼온 코드  /

def solution(number, k):
    answer = []
    
    for num in number:
        while k>0 and answer and answer[-1] < num:
            answer.pop()
            k -= 1
                    
        answer.append(num)
    
    answer = answer[:-k] if k > 0 else answer
    return ''.join(answer)

출처: https://velog.io/@soo5717/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%81%B0-%EC%88%98-%EB%A7%8C%EB%93%A4%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

Programmers | 큰 수 만들기 - Python

감사합니다.. 덕분에 공부합니다.

 

	answer = answer[:-k] if k > 0 else answer

이 부분이 예외처리로 꼭 예민하게 구현했어야하는 부분입니다. 

저도 이 부분에서 우연히 테스트케이스 찾아내서 으앗했습니다.

 

언제 연산을 종료하는지와 해당 연산이 어디까지 갔는지를 유념하며 이 부분 처리해줘야합니다.

---

풀이 시간도 오래 걸리고, 배울 것도 많은 문제였습니다.

새 라이브러리나 자료구조를 배웠다기보다는 로직을 어떻게 이해할 지에 대해서요.