큰 숫자를 만들다
문제 연결
프로그램 제작자
코드 중심 개발자를 고용하십시오. 배치 기반 위치 매칭. 프로그래머의 개발자별 프로필에 가입하고 기술 호환성이 좋은 회사와 연결하십시오.
Programmer.co.kr
문제 설명
우리는 숫자에서 k개의 숫자를 제거하여 얻은 가장 큰 숫자를 찾고 싶습니다.
예를 들어 숫자 1924에서 두 자리를 제거하면 ( 19, 12, 14, 92, 94, 24 )가 됩니다.
이 중 가장 큰 것은 94입니다.
해 함수의 매개변수로는 문자열 형식의 숫자 number와 제거할 숫자의 개수 k가 주어진다.
number에서 k개의 숫자를 빼서 만들 수 있는 숫자 중에서 가장 큰 숫자를 문자열 형태로 반환하는 solve 함수를 완성하세요.
제한
- 숫자는 2자리 이상 1,000,000자리 이하의 숫자입니다.
- k는 1보다 크거나 같고 숫자의 자릿수보다 작은 자연수입니다.
I/O 예시
| 숫자 | 케이 | 돌려 주다 |
| “1924” | 2 | “94” |
| “1231234” | 삼 | “3234” |
| “4177252841” | 4 | “775841” |
해산 과정
조합 기능을 사용하여 가능한 모든 조합을 확인합니다.
(python) 누적 합계/순열/조합(feat.itertools 모듈) Itertools, Itertools Itertools는 Python에 내장된 라이브러리입니다. aday.tistory.com
주요 기능에는 Python에서 반복 가능한 데이터를 처리하는 기능이 포함됩니다.
반복 가능한 데이터, 즉 데이터
“숫자의 길이”에서 “k를 제거할 수의 수”를 뺀 조합을 만들고 join 함수로 문자열로 변환한 후 max 함수로 최대값을 반환했습니다.
먼저 코드 제출
from itertools import combinations
def solution(number, k):
return max(list(( ''.join(i) for i in combinations(number, len(number)-k))))
위 코드의 경우 로직상 문제가 없기 때문에 자릿수가 적으면 해결이 되지만 자릿수가 많아지면 조합수가 많아져서 타임아웃이 발생하게 됩니다.
따라서 계산을 조금 더 줄여야 합니다.
최종 제출 코드
def solution(number, k):
# 스택 선언
stack = ()
# number의 길이만큼 for loop
for num in number:
# 1. 제거할 수 k가 남았고
# 2. 스택에 값이 있고
# 3. 스택의 마지막 값이 num보다 작다면
# 제거 후 제거할 수 k를 1씩 감소
while k > 0 and stack and stack(-1) < num:
stack.pop()
k -= 1
# 스택에 num 추가
stack.append(num)
# k가 남아있는 경우 - 테스트 케이스 number: "93939", k: 2, 출력: 999, 실제정답: 99
if k !
= 0:
stack = stack(:-k)
# 배열을 문자열로 바꿔주고 반환
return ''.join(stack)
1. 스택을 선언하고 개수만큼 for 루프를 반환합니다.
2. 아래 조건이 만족되면 while 루프가 반복되어 스택에서 마지막 값을 제거하고 k를 1씩 감소시킵니다.
- 제거할 수 있는 나머지 k 값이 있습니다.
- 스택이 비어 있지 않습니다.
- 현재 숫자가 스택의 마지막 값보다 작습니다.
3. k가 남아 있으면(0이 아닌 경우) k를 삭제하고 join 함수를 사용하여 문자열로 반환합니다.
의사 코드
입력 받은 numbers를 리스트로 저장
result = number의 첫번째 요소를 꺼내어 result에 저장
for n in number
if 이전 요소(result의 마지막 요소) 가 현재 요소보다 작다면
while 이전 요소가 남아있음 and 이전 요소(result의 마지막 요소)< 현재 요소 and 아직 k개의 수가 제거 안됨
결과의 마지막 요소 제거
k -= 1
elif 이미 k개의 수가 제거됨 또는 이전 요소(result의 마지막 요소)가 현재 요소보다 큼
결과에 현재 요소 추가
if 아직 k개의 수가 제거 안된 경우
result의 뒤 부터 제거
