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

programmers.co.kr/learn/courses/30/lessons/42883

 

반복마다 허용 가능한 범위로 문자열을 잘라 그 범위 내에서 가장 큰 수를 구해 answer에 이어붙이며,

방금 구한 큰 수의 다음 인덱스 자리수부터 다시 큰 수를 찾는 식으로 답을 구했습니다.

 

이해를 돕고자 1829라는 숫자로 2자리 수의 가장 큰 수를 만드는 예시를 들어볼게요.

처음에는 182까지, 즉 [:-1] 까지의 수를 확인해야 합니다.

끝자리까지 검사해서 9를 max값으로 잡아버린다면 그 다음 자리수를 못 구하기 때문이에요.

 

이러한 방식으로 처음에 코딩을 했는데 테스트케이스 8번에서 틀리고, 10번에서 시간초과가 나서 고생했습니다.

 

테스트케이스 10번 시간초과 해결하기

일단 위에 기술한 방법이 O(N)이기에 여기에서 좀 더 그리디한 방법이 필요했습니다.

반복마다 구하는 문자열 범위 내에서 '9'를 만날 시, '9'보다 더 큰 수는 불가능하기에 반복을 break하여 10번 테스트케이스의 시간초과를 해결했습니다.

 

테스트케이스 8번 틀렸습니다 해결하기

반례부터 말씀드리자면 '0101'과 1입니다.

저같은 경우는 정답을 맞추기 전 maxNum 변수를 '0'으로 줬기 때문에

세번째 자리수 0101에서 maxNum이 0보다 큰 수가 아니여서 curIdx를 갱신하지 못한게 문제였습니다.

그래서 문자열 '0~9'보다 작게 나오는 '-'로 maxNum을 선언하여 8번을 해결했습니다.

 

def solution(strNum, k1):
    answer = ''
    maxNum = '-'
    nextNumIdx = 0
    curIdx = 0
    # 초기 endPoint 설정
    k2=len(strNum)-k1 # 반환해야할 자리수 계산
    endPoint = -k2+1
    if endPoint == 0:
        prev = strNum[:]
    else:
        prev = strNum[:endPoint]
    
    # answer의 길이가 k가 될때까지 반복
    while True:
        if len(answer) == k2:
            break
        
        for i in range(len(prev)):
            # 더 큰 수를 만나면 maxNum 교체
            if prev[i] > maxNum:
                maxNum = prev[i]
                curIdx = i # 현재 인덱스 저장
                if maxNum == '9':
                    break

        answer += maxNum
        maxNum = '-' # maxNumber 초기화
        nextNumIdx += curIdx + 1

        endPoint += 1
        if endPoint == 0:
            prev = strNum[nextNumIdx:]
        else:
            prev = strNum[nextNumIdx:endPoint]

    return answer

정답을 맞춘후 다른 코드들을 구경했는데 stack을 이용해 푸는 방법도 있었습니다.

코딩테스트 리뷰 첫 글인데 괜찮았나 모르겠네요.

조언과 지적은 환영이며 글이 도움이 되셨다면 댓글 한번 남겨주세요!