[문제 풀이] 프로그래머스 - Lv2 큰 수 만들기
9485 단어 알고리즘 문제 풀이알고리즘 문제 풀이
프로그래머스 - 여행경로
1. 문제
2. 고려할 사항
- number는 1자리 이상, 1,000,000자리 이하의 숫자로 문자열로 주어진다
- 제거할 수의 개수: k는 1이상 number의 자릿수 미만인 자연수
- 남겨야 할 자릿수: number의 길이 - k
- number 요소는 0부터 9까지 이다.. (최댓값을 초기화할 때 0으로 하면 최댓값의 인덱스를 찾을 수 없다.)
3. 풀이
전개 1 - 반복문과 인덱스를 활용한 풀이
- 특정 범위의 숫자 중 최댓값을 찾고, 매순간 최댓값을 결과에 더해주는 식으로 문제를 풀 수 있다.
- 특정 범위는 (시작 인덱스부터 k+1번째까지)를 말한다.
- 시작 인덱스는 반복문을 돌 때마다 (최댓값의 인덱스 + 1)로 업데이트되고, 직전 인덱스와 현재 시작 인덱스의 차이만큼 k가 줄어든다.
- k가 0이 되면 굳이 반복문을 돌 필요가 없으므로 나머지 값을 전부 결과에 더한다.
전개 2 - 스택을 활용한 풀이
- 스택 최상위 숫자가 새로 푸시될 숫자보다 작을 경우, 최상위 숫자를 팝하고 팝할 때마다 k에서 1을 빼준다.
- 최상위 숫자를 업데이트 해도 새로 푸시될 숫자보다 여전히 작다면, 반복문을 돌려 계속 팝한다.
- 반대로 최상위 숫자가 크거나 같을 경우, 스택에 푸시한다.
- 입력값이 한 개의 숫자로만 구성된 경우, 스택에는 모든 숫자가 푸시된다. 이를 대비해 마지막에 슬라이싱을 사용하여 필요한 만큼의 길이만 구하여 값을 반환한다.
4. 배운 점
- 불필요한 반복문은 돌지 말자.
- 방법 1에서 특정 범위의 최댓값이 9로 할당되면 이후 반복문을 돌지 않아도 된다!
- join 함수를 적절히 활용하자.
- 방법 1, 2에서 k가 0일 경우, 불필요한 반복문을 돌지 않고 나머지 숫자를 모두 결과에 더해주면 된다.
이 경우 반복문을 사용하는 것보다 join이 더 빠르게 실행된다는 점 참고하자.
- 슬라이싱은 되도록 지양하자.
- 알고리즘적으로 슬라이싱이 과연 필요할까? 고민해봐야 한다.
- 적절한 인덱싱만으로 문제를 해결할 수 있다.
- 스택 자료구조를 활용하면 생각보다 간단히 문제를 해결할 수 있다.
5. 풀이 코드
# 방법 1
# 반복문과 인덱스를 활용한 풀이 (시도해본 것중 가장 빠른 풀이)
def solution(number, k):
size = len(number)
start = 0
end = start + k
max_nums = []
while end < size:
if not k:
max_nums.append(''.join(number[start:]))
break
max_val = '-1'
max_idx = 0
for i in range(start, end + 1):
num = number[i]
if num > max_val:
max_val = num
max_idx = i
if max_val == '9':
break
max_nums.append(max_val)
k -= (max_idx - start)
start = max_idx + 1
end = start + k
return ''.join(max_nums)
# 방법 2
# 스택을 활용한 풀이
def solution_with_stack(number, k):
size = len(number)
max_nums = [number[0]]
idx = 1
while idx < size:
if not k:
max_nums.append(''.join(number[idx:]))
break
num = number[idx]
while max_nums and num > max_nums[-1] and k > 0:
max_nums.pop()
k -= 1
max_nums.append(num)
idx += 1
return ''.join(max_nums[:size - k])
if __name__ == '__main__':
number = "1231234"
number = "194154993"
number = "4177252841"
number = "99999"
number = "1924"
k = 2
print(solution(number, k))
print(solution_with_stack(number, k))
Author And Source
이 문제에 관하여([문제 풀이] 프로그래머스 - Lv2 큰 수 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@bky373/알고리즘-프로그래머스-큰-수-만들기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 방법 1에서 특정 범위의 최댓값이 9로 할당되면 이후 반복문을 돌지 않아도 된다!
- 방법 1, 2에서 k가 0일 경우, 불필요한 반복문을 돌지 않고 나머지 숫자를 모두 결과에 더해주면 된다.
이 경우 반복문을 사용하는 것보다 join이 더 빠르게 실행된다는 점 참고하자.
- 알고리즘적으로 슬라이싱이 과연 필요할까? 고민해봐야 한다.
- 적절한 인덱싱만으로 문제를 해결할 수 있다.
# 방법 1
# 반복문과 인덱스를 활용한 풀이 (시도해본 것중 가장 빠른 풀이)
def solution(number, k):
size = len(number)
start = 0
end = start + k
max_nums = []
while end < size:
if not k:
max_nums.append(''.join(number[start:]))
break
max_val = '-1'
max_idx = 0
for i in range(start, end + 1):
num = number[i]
if num > max_val:
max_val = num
max_idx = i
if max_val == '9':
break
max_nums.append(max_val)
k -= (max_idx - start)
start = max_idx + 1
end = start + k
return ''.join(max_nums)
# 방법 2
# 스택을 활용한 풀이
def solution_with_stack(number, k):
size = len(number)
max_nums = [number[0]]
idx = 1
while idx < size:
if not k:
max_nums.append(''.join(number[idx:]))
break
num = number[idx]
while max_nums and num > max_nums[-1] and k > 0:
max_nums.pop()
k -= 1
max_nums.append(num)
idx += 1
return ''.join(max_nums[:size - k])
if __name__ == '__main__':
number = "1231234"
number = "194154993"
number = "4177252841"
number = "99999"
number = "1924"
k = 2
print(solution(number, k))
print(solution_with_stack(number, k))
Author And Source
이 문제에 관하여([문제 풀이] 프로그래머스 - Lv2 큰 수 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bky373/알고리즘-프로그래머스-큰-수-만들기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)