일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- kakao
- 백준
- await
- linux
- typeorm
- tr명령어
- mutation
- vanila js
- 카카오
- REST API
- nestjs
- 코딩태스트
- RestAPI
- 자바스크립트
- typescript
- 피보나치 수
- Query
- graphql
- 프로그래머스
- javascript
- ROT13
- 코딩테스트
- node
- html
- JavaStritp
- Bandit
- 실패율
- js
- 자바스크립트의 역사
- 모던 자바스크립트
- Today
- Total
꿀 떨어지는 코딩 양봉장
프로그래머스_Level 2 큰 수 만들기 본문
1. 문제설명
문제: 큰수만들기
https://programmers.co.kr/learn/courses/30/lessons/42883
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
2. 제한 조건
- number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상 number의 자릿수 미만인 자연수입니다.
3. 입출력 예
number | k | return |
"1924" | 2 | "94" |
"1231234" | 3 | "3234" |
"4177252841" | 4 | "775841" |
📌나의 풀이
k개의 숫자를 제거한다는 개념을 이해하는데 상당한 시간이 걸렸다.
처음에는 for문을 이용하여 current가 current+1보다 작다면 current를 지우는 방식으로 풀었다.
하지만 이렇게 푼다면 테스트 케이스 10번에서 시간초과가 걸린다. 또 다양한 반례들을 생각했어야했다.
for문을 이용한 방법
function solution(number, k) {
var len = number.length-k;
number = number.split('').map((content)=>Number(content));
for(var i=0; i<number.length; i++){
if(k<=0)break;
//number[i]가 number[i+1]보다 작으면
//마지막 숫자를 삭제해야할 수 도 있기때문에 number[i+1]이 undefined일 때도
if((number[i]<number[i+1]|| number[i+1]===undefined)){
//number[i] 삭제
number.splice(i,1);
k-=1;
i=-1;
}
}
return number.join('');
}
for문을 돌면서 number[i]의 값이 다음값(number[i+1])보다 작다면 number[i]를 삭제하는 알고리즘이다.
일단 이 알고리즘은 테스트케이스 10번에서 시간초과 오류가 난다.
테스트케이스 10번은 단순히 엄청난게 긴 숫자이다. 시간 초과 오류를 나게 하지 않기 위해서는 다른 방법으로 접근해야한다.
stack을 이용한 방법
function solution(number, k) {
const stack = []; //글자들이 저장될 스택
let answer = '';
for(let i=0; i<number.length; i++){ //number의 길이만큼 돈다
const element = number[i];
//k가 0보다 크면서
//element가 stack의 마지막값 보다 크면
while(k>0 && stack[stack.length-1]<element){
stack.pop();//마지막 값을 뺸다.
k--;
}
stack.push(element);
}
//만약 같은 값이 연속으로 나올때를 위해서 splice사용
stack.splice(stack.length-k,k);
answer = stack.join('');
return answer;
}
시간초과를 해결하기 위해서는 stack을 사용해야했다.
for문을 돌면서 number[i]가 stack에 있는 마지막 값보다 크다면 stack의 가장 마지막 값을 뺸다.
k가 0보다 작거나 같아지거나 number[i]의 값이 stack의 마지막 값보다 작다면 스택에 number[i]를 push한다.
stack.splice(stack.length-k,k); 는 예를 들면 number이 '999999999' k가 3 같은 예제 때문에 있는 것이다.
중복된 값이 여러게라면 모두 stack에 push되기 때문에 splice를 통해 k만큼 제거해야한다.
💡배운점
- 다양한 방식으로 문제에 접근하는 방법을 배웠다.
- stack을 사용하여 문제를 해결하는 방법에 대해서 알게되었다
✔ 참고 자료
'알고리즘 > 프로그래머스' 카테고리의 다른 글
프로그래머스_Level.2[3차]압축 (0) | 2021.05.01 |
---|---|
프로그래머스_Levle.2 [3차] n진수 게임 (0) | 2021.04.30 |
프로그래머스_Level.2 땅따먹기 (0) | 2021.04.30 |
프로그래머스_Level.2 소수찾기 (0) | 2021.04.27 |
프로그래머스_Level.2 피보나치 수 (0) | 2021.04.27 |