.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Level 2 210923 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 함수를 완성하세요.
제한 조건
•
number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
•
k는 1 이상 number의 자릿수 미만인 자연수입니다.
입출력 예
My solution
주어진 number는 순서를 바꿀 수가 없다. 처음에 문제를 잘 이해 안되는 것은 이것 때문일 것이다. k개만큼 뽑고 "순서를 유지한 채로 만들어진 최댓값"을 return해야 한다.
입출력 예 1을 보면 1924이고 k가 2이다. number에서 k개 뽑으면 리턴값은 2자리 수가 된다.
체크 배열을 이용해서 선택한 인덱스 이전 인덱스까지 전부 체크해주는 방식으로 k개의 숫자를 뽑은 조합 중에서 숫자의 순서를 유지한 조합만 남길 수 있었다. 재귀의 깊이는 tmp가 number.length - k 개면 종료되도록 했고 주어진 세 개의 테스트케이스는 다 통과했다.
function solution(number, k) {
let answer = [];
let n = number.length
let ch = Array.from({ length: n }, () => 0);
let tmp = Array.from({ length: n-k }, () => 0);
function DFS(L) {
if (L === n-k) {
answer.push(tmp.slice().join(''));
} else {
for (let i = 0; i < n; i++) {
if (ch[i] === 0) {
for(let j=0; j <= i; j++){
ch[j] = 1; // 이 인덱스의 이전 인덱스들까지 차단
}
tmp[L] = number[i];
DFS(L + 1);
for(let j=0; j <= i; j++){
ch[j] = 0; // 이 인덱스의 이전 인덱스들까지 해제
}
}
}
}
}
DFS(0);
let max = Number.MIN_SAFE_INTEGER;
for(let x of answer ){
max = Math.max(max, Number(x))
}
return max.toString();
}
JavaScript
복사
헌데 정확도가 처참하다.
프로그래머스 런타임 에러를 검색해보니
6. 재귀 호출이 너무 깊어질 경우 3번과 비슷한 케이스인데 재귀 호출의 횟수가 스택 크기 제한을 넘어가는 경우 런타임 에러가 발생합니다. 출처:https://jaimemin.tistory.com/1522 [꾸준함]
아마도 재귀를 사용한 것도 그렇고 모든 값을 하나씩 탐색해서 범위조절이 필요할 것 같다. 범위를 어떻게 조절해줘야할지 생각해보니 최댓값이 되는 숫자를 뽑을 수 있는 자리가 k에 따라 달라진다는 걸 알 수 있었다.
체크배열에 넣어서 조건을 주었듯이 최댓값이 되는 숫자를 하나 뽑고 나면 그 다음 뽑을 숫자는 그 숫자의 다음의 인덱스부터 마지막 인덱스까지의 범위 내에서만 뽑을 수 있다.
유의해야할 것은 아무것도 뽑지 않았을 때 0번 인덱스 ~ n - k번 인덱스까지 확인한다는 것이고 이후 max 값이 찾아질 때마다 그 인덱스로 cur(커서)를 업데이트해준다. 이 cur 값을 처리하는 것이 중요하다. cur을 0으로 선언하여 j에 할당한 뒤 n-k번 인덱스까지 탐색하게 되면 그 다음 max 값을 만난 뒤 cur을 +1해서 업데이트해준다면 다음은 cur+1 인덱스부터 탐색해나갈 것이다. 그렇게 정해진 max값을 가지고 다음 루프로 가면 cur(선택된 max값의 인덱스)의 다음 값부터 max를 구해나갈 것이다.
위와 같이 구현해서 제출해보니 테스트케이스 10번이 시간초과가 났다.
반복문의 횟수를 많이 줄인 것 같은데 잘 모르겠어서 찾아보니까 number[j]가 9가 나오면 max를 찾기 위한 탐색을 더이상 하지 않게 해야된단다. 이 코드는 c나 c++같은 언어는 걸리지 않아서 추가적으로 시간을 단축하는 용도로 쓰라고 하던데 js는 여러모로 남다르다.
결국 아래의 코드로 통과했다.
소스 코드
function solution(number, k) {
let answer = "";
let cur = 0;
for (let i = number.length - k; i > 0; i--) {
let max = "0";
// console.log("i", i, cur);
for (let j = cur; j <= number.length - i; j++) {
// console.log("j", j, number[j]);
if (max < number[j]) {
max = number[j];
cur = j + 1;
if (number[j] == "9") break;
}
}
answer += max;
}
return answer;
}
test("solution", () => {
expect(solution("1924", 2)).toBe("94");
expect(solution("1231234", 3)).toBe("3234");
expect(solution("4177252841", 4)).toBe("775841");
});
JavaScript
복사
