NSH.coding

DP란?

DP = Dynamic Programming (동적 계획법)

복잡한 문제를 간단한 여러 개의 문제로 해결하는 알고리즘 설계 기법

각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다.

​

DP 적용 조건

1. Overlapping Subproblems(중복되는 하위 문제)
   • DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다.
   • 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
2. Optimal Substructure(최적 부분 구조)
   • 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다.
   • 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다.

​

문제 요구사항

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다.

이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자.

사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

​

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

​

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

​

입출력 예

• 사자가 0마리 일 때 경우의 수 1
• 사자가 1마리 일 때 경우의 수 8
• 사자가 2마리 일 때 경우의 수 18
• 사자가 3마리 일 때 경우의 수 12
• 사자가 4마리 일 때 경우의 수 2

​

첫번째 시도 - 구현 실패

일단은 생각나는 대로 코드를 작성해보았다.

1. 사자가 0마리 일 때에는 경우의 수가 항상 1이다
2. 사자가 1마리 일 때의 경우의 수는 전체 칸 수 이다
3. 사자가 2마리 일 때의 경우의 수는 1부터 N-1개의 홀수에 각각 2를 곱한뒤 더한다

하지만 이 이후로 알고리즘을 생각해내기가 어려웠다.

(N=3의 경우의 수) + (N=4만 가능한 경우의 수)가 답 인것 같은데, 그 로직이 떠오르지 않아 골머리를 앓았다.

혼자 2시간 쯤 고민을 하고 결국 GPT의 도움을 받았다.

​

성공 코드

1. 사자가 있는 우리를 배열로 나타내는게 아니라, i번째 줄에 사자가 없는 경우, 1마리씩 있는 경우를 배열로 나타낸다
   • dp[i][0] = i번째 줄에 사자가 없는 경우
   • dp[i][1] = i번째 줄 첫번째 열에 사자가 있는 경우
   • dp[i][2] = i번째 줄 두번째 열​에 사자가 있는 경우
2. 배열의 크기가 (N+1) * 3 인 배열을 만든다
   • 사실 배열의 크기가 Nx3 이어도 되는데, 가독성을 위해 0번째 행은 제외하고 생각한다.
3. dp[1][0], dp[1][1], dp[1][2] 는 모두 1이다
   • 1번째 줄에 사자가 없을 경우 1가지
   • 1번째 줄 첫번째 열에 사자가 있을 경우 1가지
   • 1번째 줄 두번째 열에 사자가 있을 경우 1가지
4. i번째 줄의 경우의 수는 아래와 같이 구한다
   • dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2])
     • i번째 줄에 사자가 없다면, i-1번째 줄에는 사자가 없어도 되고 있어도 되기에 모든 경우의 수를 더한다
   • dp[i][1] = (dp[i-1][0] + dp[i-1][2])
     • i번째 줄 첫번째 열에 사자가 있다면, i-1번째 줄에는 사자가 없거나, 두번째 열에 있을 수 있다
   • dp[i][2] = (dp[i-1][0] + dp[i-1][1])
     • i번째 줄 두번째 열에 사자가 있다면, i-1번째 줄에는 사자가 없거나, 첫번째 열에 있을 수 있다

​

위의 내용을 정리하면 아래 그림과 같다.

하위 → 상위 식으로 값이 누적되어 최종적으로는 N번째 줄의 모든 값을 더 하면 답이 된다.

function solution(N) {
    const mod = 9901;
    const dp = Array.from({ length: N + 1 }, () => Array(3).fill(0));
    
    // 초기값 설정
    dp[1][0] = 1;
    dp[1][1] = 1;
    dp[1][2] = 1;
    
    for (let i = 2; i <= N; i++) {
        dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % mod;
        dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % mod;
        dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % mod;
    }
    
    const result = (dp[N][0] + dp[N][1] + dp[N][2]) % mod;
    console.log(result);
}

​

처음 지피티의 코드를 보고 이해하기가 쉽지 않았다.

이해를 한 뒤에는, 이런식으로도 문제를 풀 수 있구나하는 생각에 뒤통수를 맞은 느낌이었다.

마냥 사자의 수와 우리에 얽매여 더 효율적인 프로세스를 생각하지 못한것이 안타깝다..🥲

문제 요구사항

프로그래머스 재귀 문제 Lv.1 소수 만들기

​

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다.

숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

​

제한 사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

​

입출력 예

약수에는 짝이 있기 때문에, 특정 수의 제곱이 num보다 작을 때까지 비교하며 특정 수가 약수인지 아닌지 찾는다.

Ex) 64 -> 64의 약수는 1 x 64, 2 x 32, 8 x 8 이므로 32까지 가지 않아도 2에서 약수가 있음이 검출된다.

​

2. 재귀 함수

// 조합을 재귀적으로 생성하고, 그 합이 소수인 경우를 계산하는 함수
    function findCombinations(index, selected, sum) {
        if (selected.length === 3) {
            if (isPrime(sum)) count++;
            return;
        }

        // 현재 전달 받은 index + 1, 현재 전달받은 배열에 현재 인덱스 값 추가해서 함수 호출
        // 전달한 배열의 길이가 3이면 return 되어 i가 더해짐
        for (let i = index; i < nums.length; i++) {
            findCombinations(i + 1, [...selected, nums[i]], sum + nums[i]);
        }
    }

index, selected, sum 세 개의 매개변수를 갖는다.

index -> 전체 nums의 인덱스 중 현재 가르키고 있는 인덱스

seleted -> 선택된 숫자들이 들어있는 배열

sum -> seleted 배열에 있는 숫자들의 합

​

seleted 안에 숫자가 3개라면 3개 숫자 합이 소수인지 아닌지 판별한다.

안에 들어있는 숫자가 3개가 아니라면, 다음 인덱스의 값을 추가하여 또 다시 함수를 호출한다.

이를 그림으로 정리해보면 아래 그림과 같다.

​

전체 코드

function solution(nums) {
    let count = 0;

    // 주어진 수가 소수인지 판별하는 함수
    function isPrime(num) {
        if (num <= 1) return false;
        for (let i = 2; i * i <= num; i++) {
            if (num % i === 0) return false;
        }
        return true;
    }

    // 조합을 재귀적으로 생성하고, 그 합이 소수인 경우를 계산하는 함수
    function findCombinations(index, selected, sum) {
        if (selected.length === 3) {
            if (isPrime(sum)) count++;
            return;
        }

        // 현재 전달 받은 index + 1, 현재 전달받은 배열에 현재 인덱스 값 추가해서 함수 호출
        // 전달한 배열의 길이가 3이면 return 되어 i가 더해짐
        for (let i = index; i < nums.length; i++) {
            findCombinations(i + 1, [...selected, nums[i]], sum + nums[i]);
        }
    }

    // 첫 번째 인덱스부터 조합 생성 시작
    findCombinations(0, [], 0);

    return count;
}

재귀를 생각해내기가 어려운 문제인 것 같다.

이해하고 나면 그렇게 어려운 알고리즘은 아니지만, 인적 사고로 바로 생각해내기에는 복잡함이 있다.

또한, 오히려 재귀를 쓰면 시간 초과가 되는 문제들이 있기 때문에 주어진 문제에 맞추어 알고리즘을 잘 선택해야할 것 같다.

​

특히, 프로그래머스의 모음 사전과 같은 문제는 재귀를 사용하기가 더욱 어려운 문제였고,

피보나치 수 문제는 재귀를 사용하면 시간 초과, for문을 사용해야 통과되는 경우가 있었다.

문제 요구사항

프로그래머스 Greedy Lv.2 큰 수 만들기

​

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

​

제한 조건

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

​

입출력 예

- 아래 2개의 테스트 케이스는 다른 분들이 제시한 테스트 케이스이다.

​

첫번째 시도 - 테스트 4번, 8번, 10번 실패

일단은 생각나는 대로 코드를 작성해보았다.

1. number를 배열로 바꾼다. -> array
2. 시작 인덱스를 정한다. -> startIndex
   • 한자리 수 중 최댓값은 9이므로 배열 앞자리에 9가 있으면 건너뛰고 시작 인덱스 설정.
3. startIndex부터 k + 1만큼 배열 앞부분을 잘라서 따로 저장한다. -> frontPart
   • k만큼 자르게되면 k가 1일 때 비교값이 사라지기 때문에 k+1만큼 자른다.
   • 만약, frontPart의 마지막 값이 array의 마지막 값이라면, frontPart 부분을 모두 잘라내고 while문 밖으로 나간다.
4. frontPart내에서 최댓값을 찾는다. -> max
5. array에서 frontPart 부분을 돌며 max보다 작은 값을 삭제하기 위해 deleteSet에 저장한다.
   1. deleteSet에 값을 저장할 때 마다 k를 감소시키고, k가 0이 되었다면 for문 밖으로 나간다.
   2. max와 같은 값과 만나면 for문 밖으로 나간다.
6. while문 마지막에서 filter를 이용해 deleteSet에 저장된 인덱스에 해당하는 값을 삭제한다.
7. while문이 끝난 뒤 array의 길이가 결과 길이보다 길면 뒤에서부터 값을 삭제한다.

function solution(number, k) {
    // number를 배열로 바꾼다
    let array = number.split('');

    // 시작 인덱스를 정한다.
    let startIndex = 0;
    // 초기 max값은 9로 정한다. 배열의 가장 앞부분에 9가 있으면 건너뛰기 위해서.
    let max = 9;

    while(k > 0){
        // max값보다 작은 값이 처음 나오는 곳을 시작 인덱스로 정한다. -> 999, 888 등 높은 숫자가 이어지는 것 건너뛰기
        for(let i = startIndex; i < array.length; i++){
            if(array[i] < max){
                startIndex = i;
                break;
            }
        }

        // startIndex부터 k + 1만큼 배열 앞부분을 잘라서 따로 저장한다.
        let frontPart = array.slice(startIndex, startIndex+k+1).map(Number);

        // 만약, frontPart의 마지막 값이 array의 마지막 값이라면, frontPart 부분을 모두 잘라내고 while문 밖으로 나간다.
        if(startIndex+k >= array.length){
            array = array.slice(0, startIndex);
            break;
        }

        // frontPart 내에서 최댓값을 찾는다.
        max = Math.max(...frontPart);

        // array에서 frontPart 부분을 돌며 max보다 작은 값을 삭제하기 위해 deleteSet에 저장한다.
        let deleteSet = new Set();
        for(let i = startIndex; i < startIndex + frontPart.length; i++){
            if(array[i] != max) { 
                // deleteSet에 값을 저장할 때 마다 k를 감소시키고, k가 0이 되었다면 for문 밖으로 나간다.
                deleteSet.add(i);
                k--;
                if(k == 0) break;
            }
            else{ 
                // max와 같은 값과 만나면 for문 밖으로 나간다.
                break;
            }
        }

        // while문 마지막에서 filter를 이용해 deleteSet에 저장된 인덱스에 해당하는 값을 삭제한다.
        array = array.filter((_, index) => !deleteSet.has(index));
    }

    // while문이 끝난 뒤 array의 길이가 결과 길이보다 길면 뒤에서부터 값을 삭제한다.
    while(array.length > number.length - k){
        array.pop();
    }
    
    return array.join('');
}

주어진 테스트케이스에서는 모두 통과를 하였지만, 막상 제출을 하니 4번은 실패, 8번은 시간 초과, 10번은 런타임 에러가 떴다.

그래서 질의응답 창을 보던 중 Stack을 사용하면 간단하다는 힌트를 보고 아래 코드를 구현했다.

​

두번째 시도 - "Stack"이라는 힌트를 얻어 성공 !

1. number를 배열로 바꾼다. -> array
2. 결과 값이 되어야하는 길이를 저장해둔다. -> finalLength
3. array의 가장 첫 숫자를 넣은 stack을 생성한다.
   • 가장 첫 숫자를 stack에 넣었기 때문에 시작 인덱스를 1로 정한다. -> index
4. index가 array를 벗어나지 않는 동안 while문을 돌린다.
   1. stack이 비어있거나, stack의 맨 위의 값이 현재 값보다 크면 현재 값을 stack에 넣는다. 값을 넣었기때문에 index는 다음으로 넘어간다.
   2. stack의 맨 위의 값이 현재 값보다 작으면
      1. stack의 맨 위의 값을 뺀다. 값을 뺐기 때문에 k를 감소시킨다.
         • index를 그대로 두는 이유 : 다시 while문이 돌아 왔을 때 또 맨 위의 값이 현재 값보다 작으면 빼야한다.
      2. 만약 k가 0이라서 값을 더 이상 빼지 않아도 된다면 그냥 값을 넣고 index를 다음으로 넘긴다.
5. while문이 모두 끝나서 array의 마지막 값까지 넣었다면 stack 길이를 finalLength와 맞춘다.
   • "9998888123"의 경우 마지막 3을 가리킬 때 1,2만 삭제하게 된다. 그렇게 되면 k가 0이 되기 전 while문이 끝난다.

function solution(number, k) {
    let array = number.split('');
    let finalLength = array.length - k;
    let stack = [array[0]];
    let index = 1;

    while(index < array.length){

        if((stack.length == 0 || stack[stack.length - 1] >= array[index])){
            stack.push(array[index]);
            index++;
        }
        else {
            if(k !== 0){
                stack.pop();
                k--;
            }
            else {
                stack.push(array[index]);
                index++;
            }
        }
    }
    while(stack.length > finalLength){
                stack.pop();
    }

    return stack.join('');
}

​

힌트를 얻어 코드를 작성하니 생각보다 간단하게 해결되었다. 처음에 너무 어렵게 생각한걸까...

Greedy 알고리즘은 너무 어렵다..🥲

문제 요구사항

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다.

어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

​제한사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

​

입출력 예

입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

​

------------------------------------------------------------

​

일단 이 문제의 큰 문제점은 이해하기가 어렵다는 것이다.

프로그래머스의 질의응답 게시판을 봐도 문제 이해가 안된다는 글이 대부분이다.

그래서 문제를 이해한 바탕으로 다시 설명해보자면,

​

"나머지 논문이 h번 이하 인용되었다면" 이 문구를 무시한다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이면 h의 최댓값이 이 과학자의 H-Index입니다.

즉, 논문이 인용된 횟수가 a번이라고 하면, a번보다 많이 인용된 논문의 개수가 a보다 크거나 같으면 된다.

여기서 중요한 점은, 입력값에 존재하지 않는 인용 횟수도 h값이 될 수 있다는 것이다.

​

위의 입출력 예시로 다시 설명해보면

• 0 -> 0번 이상 인용된 논문은 0, 1, 3, 5, 6 총 5개이다. 0 < 5 이므로 0은 H-Index의 후보값이 된다.
• 1 -> 1번 이상 인용된 논문은 1, 3, 5, 6 총 4개이다. 1 < 4 이므로 1은 H-Index의 후보값이 된다.
• 2 -> 2번 이상 인용된 논문은 3, 5, 6 총 3개이다. 2 < 3 이므로 2는 H-Index의 후보값이 된다.
• 3 -> 3번 이상 인용된 논문은 3, 5, 6 총 3개이다. 3 = 3 이므로 3은 H-Index의 후보값이 된다.
• 4 -> 4번 이상 인용된 논문은 5, 6 총 2개이다. 4 > 2이므로 4는 H-Index의 후보값이 될 수 없다.
• 5 -> 5번 이상 인용된 논문은 5, 6 총 2개이다. 5 > 2이므로 5는 H-Index의 후보값이 될 수 없다.
• 6 -> 6번 이상 인용된 논문은 6 총 1개이다. 6 > 1이므로 6은 H-Index의 후보값이 될 수 없다.

그럼 후보값 0, 1, 3 중에 가장 큰 값인 3이 H-Index가 된다.

​

다른 예시를 들어보면, [1, 10, 11] 이라는 세 값이 있을 때

• 1번 이상 인용된 논문은 1, 10, 11로 3개이다. 1 < 3이므로 1은 H-Index의 후보값이 된다.
• 2번 이상 인용된 논문은 10, 11로 2개이다. 2 = 2이므로 2은 H-Index의 후보값이 된다.
• 3번 이상 인용된 논문은 10, 11로 2개이다. 3 > 2이므로 3은 H-Index의 후보값이 될 수 없다.

그럼 우리는 세번의 시도 만으로도 답을 알 수 있다.

2가 H-Index 후보값이지만, 3이 H-Index 후보값이 아니라면, 3보다 큰 수 중에서는 H-Index의 후보값이 될 수 있는 값이 없다.

따라서 답은 2이다.

​

위의 방법으로 문제를 이해하고 문제를 풀어보았다.

​

코드

function solution(citations) {
    citations.sort((a, b) => b - a); // 내림차순 정렬

    let sValue = citations[0]; // H-Index는 최댓값이므로, 논문이 가장 많이 인용된 횟수를 시작 값으로 정한다.

    while(true){               // 최악의 경우, 논문이 인용된 횟수 중 최댓값 x citations 배열 길이만큼 돌아야하므로 while문 사용
        let cnt = 0;
        
        for (let i = 0; i < citations.length; i++) {
            if (citations[i] >= sValue) { // citations 배열을 훑으며 sValue보다 크거나 같은 값을 카운트
                cnt = cnt + 1;
            }
        }
        if(cnt >= sValue){     // sValue보다 크거나 같은 값이 sValue보다 많으면 그 값을 H-Index로 정한다.
            return sValue;
        }
        else{
            sValue--;          // 아니라면 기존 sValue에서 1을 뺀 값을 sValue로 정한다.

            if(sValue < 0){    // sValue가 음수 값이라면 citations 배열의 길이를 return한다.
                return citations.length;
            }
        }
        
    }
}

console.log(solution([3, 0, 6, 1, 5])); // return 3
console.log(solution([1, 10, 11])); // return 2
console.log(solution([0, 0, 0, 0, 0])); // return 0

while true 문을 사용하여, 메모리 복잡도가 걱정되긴하지만 이런 식으로 풀이하였다.

아마 더 간단한 풀이도 있을텐데, 문제 이해를 위하여 이렇게 늘여서 작성하였다.

​

두번째 시도

shift(), unshift()를 사용하지 않기 위해 addFront()와 removeFront()라는 함수를 만들었다.

새로운 배열을 생성하여 공간 복잡도가 높아질 수는 있지만, 백준에서는 시간이 항상 문제이기에 이렇게 작성하였다.

하지만 이번에도 시간 초과로 실패하였다.

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

function addFront(array, num){
    let newArray = [];
    if(array.length === 0){
        newArray.push(num);
    }
    else{
        newArray = array.map((_, i) => i === 0 ? num : array[i - 1]);
        newArray[newArray.length] = array[array.length - 1];
    }
    return newArray;
}

function removeFront(array){
    let newArray = [];
    if(array.length === 1){
        console.log(array[0]);
    }
    else{
        newArray = array.map((_, i) => array[i + 1]);
        newArray.pop();
        console.log(array[0]);
    }
    return newArray;
}

function solution(input) {
    let answer = [];
    for(let i = 1; i < +input[0] + 1; i++){
        if(input[i].length > 1){
            let array = input[i].split(' ');
            if(array[0] === '1'){        // 1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000)
                answer = addFront(answer, +array[1]);
            }
            else if(array[0] === '2'){   // 2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000)
                answer.push(+array[1]);
            }
        }
        else if(input[i].length === 1){
            if(['3', '4', '7', '8'].includes(input[i])){
                if(answer.length === 0){
                    console.log('-1');
                }
                else{
                    switch(input[i]){
                        case '3':               // 3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
                            answer = removeFront(answer);
                            break;
                        case '4':               // 4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
                            console.log(answer.pop());
                            break;
                        case '7':               // 7: 덱에 정수가 있다면 맨 앞의 정수를 출력한다. 없다면 -1을 대신 출력한다.
                            console.log(answer[0]);
                            break;
                        case '8':               // 8: 덱에 정수가 있다면 맨 뒤의 정수를 출력한다. 없다면 -1을 대신 출력한다.
                            console.log(answer[answer.length - 1]);
                            break;
                    }
                }  
            }
            else{
                switch(input[i]){
                case '5':               // 5: 덱에 들어있는 정수의 개수를 출력한다.
                    console.log(answer.length);
                    break;
                case '6':               // 6: 덱이 비어있으면 1, 아니면 0을 출력한다.
                    console.log(answer.length === 0 ? '1' : '0');
                    break;
                }
            }
        }
    }
}

solution(input);

​

세번째 시도

배열 내장 함수를 사용하는 것이 문제인가 싶어 Linked List​로 구현해보았다.

코드는 복잡해졌지만, array를 사용할 때 보다 채점 퍼센트가 더 올라갔다.

하지만 그럼에도 시간 초과로 실패하였다.

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

class Node {
    constructor(value) {
      this.value = value;
      this.next = null;
      this.prev = null;
    }
}
  
class Deque {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    isEmpty() {
        return this.size === 0;
    }

    addFront(value) {
        const newNode = new Node(value);

        if (this.isEmpty()) {
            this.head = newNode;
            this.tail = newNode;
        } 
        else {
            newNode.next = this.head;
            this.head.prev = newNode;
            this.head = newNode;
        }

        this.size++;
    }

    addRear(value) {
        const newNode = new Node(value);

        if (this.isEmpty()) {
            this.head = newNode;
            this.tail = newNode;
        } 
        else {
            newNode.prev = this.tail;
            this.tail.next = newNode;
            this.tail = newNode;
        }

        this.size++;
    }

    removeFront() {
        if (this.isEmpty()) {
            return '-1';
        }

        const removedValue = this.head.value;
        if (this.size === 1) {
            this.head = null;
            this.tail = null;
        } 
        else {
            this.head = this.head.next;
            this.head.prev = null;
        }

        this.size--;
        return removedValue;
    }

    removeRear() {
        if (this.isEmpty()) {
            return '-1';
        }

        const removedValue = this.tail.value;
        if (this.size === 1) {
            this.head = null;
            this.tail = null;
        } 
        else {
            this.tail = this.tail.prev;
            this.tail.next = null;
        }

        this.size--;
        return removedValue;
    }

    printFirst() {
        if (this.isEmpty()) {
            return '-1';
        }

        return this.head.value;
    }

    printLast() {
        if (this.isEmpty()) {
            return '-1';
        }

        return this.tail.value;
    }
}

function solution(input) {
    const deque = new Deque();
    
    for(let i = 1; i < +input[0] + 1; i++){
        if(input[i].trim().length > 1){
            let array = input[i].trim().split(' ');
            if(array[0] === '1'){        // 1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000)
                deque.addFront(+array[1])
            }
            else if(array[0] === '2'){   // 2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000)
                deque.addRear(+array[1])
            }
        }
        else if(input[i].trim().length === 1){
            switch(input[i].trim()){
                case '3':               // 3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
                    console.log(deque.removeFront());
                    break;
                case '4':               // 4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
                    console.log(deque.removeRear());
                    break;
                case '5':               // 5: 덱에 들어있는 정수의 개수를 출력한다.
                    console.log(deque.size);
                    break;
                case '6':               // 6: 덱이 비어있으면 1, 아니면 0을 출력한다.
                    console.log(deque.isEmpty() ? '1' : '0');
                    break;
                case '7':               // 7: 덱에 정수가 있다면 맨 앞의 정수를 출력한다. 없다면 -1을 대신 출력한다.
                    console.log(deque.printFirst());
                    break;
                case '8':               // 8: 덱에 정수가 있다면 맨 뒤의 정수를 출력한다. 없다면 -1을 대신 출력한다.
                    console.log(deque.printLast());
                    break;
            }
        }
    }
}

solution(input);

​

마지막 시도 - 성공 !

내 친구 지피티와 상의해본 결과 console.log가 자주 사용되어 시간 복잡도가 높아진다는 피드백을 받았다.

+ 문자열 함수 trim()은 반드시 필요할 때만 사용하라는 피드백도 받았다.

하지만 입력 값을 받을 때 인적 실수를 항상 고려하라는 교수님의 말씀이 떠올라서 ^__^ 제외는 안했다.

그래서 console.log 대신 출력 값을 저장하는 배열을 만들고 마지막에 배열을 출력해주었다.

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

class Node {
    constructor(value) {
      this.value = value;
      this.next = null;
      this.prev = null;
    }
}
  
class Deque {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    isEmpty() {
        return this.size === 0;
    }

    addFront(value) {
        const newNode = new Node(value);

        if (this.isEmpty()) {
            this.head = newNode;
            this.tail = newNode;
        } 
        else {
            newNode.next = this.head;
            this.head.prev = newNode;
            this.head = newNode;
        }

        this.size++;
    }

    addRear(value) {
        const newNode = new Node(value);

        if (this.isEmpty()) {
            this.head = newNode;
            this.tail = newNode;
        } 
        else {
            newNode.prev = this.tail;
            this.tail.next = newNode;
            this.tail = newNode;
        }

        this.size++;
    }

    removeFront() {
        if (this.isEmpty()) {
            return '-1';
        }

        const removedValue = this.head.value;
        if (this.size === 1) {
            this.head = null;
            this.tail = null;
        } 
        else {
            this.head = this.head.next;
            this.head.prev = null;
        }

        this.size--;
        return removedValue;
    }

    removeRear() {
        if (this.isEmpty()) {
            return '-1';
        }

        const removedValue = this.tail.value;
        if (this.size === 1) {
            this.head = null;
            this.tail = null;
        } 
        else {
            this.tail = this.tail.prev;
            this.tail.next = null;
        }

        this.size--;
        return removedValue;
    }

    printFirst() {
        if (this.isEmpty()) {
            return '-1';
        }

        return this.head.value;
    }

    printLast() {
        if (this.isEmpty()) {
            return '-1';
        }

        return this.tail.value;
    }
}

function solution(input) {
    const deque = new Deque();
    const answer = [];
    
    for(let i = 1; i < +input[0] + 1; i++){
        if(input[i].trim().length > 1){
            let array = input[i].trim().split(' ');
            if(array[0] === '1'){        // 1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000)
                deque.addFront(+array[1])
            }
            else if(array[0] === '2'){   // 2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000)
                deque.addRear(+array[1])
            }
        }
        else if(input[i].trim().length === 1){
            switch(input[i].trim()){
                case '3':               // 3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
                    answer.push(deque.removeFront());
                    break;
                case '4':               // 4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
                    answer.push(deque.removeRear());
                    break;
                case '5':               // 5: 덱에 들어있는 정수의 개수를 출력한다.
                    answer.push(deque.size);
                    break;
                case '6':               // 6: 덱이 비어있으면 1, 아니면 0을 출력한다.
                    answer.push(deque.isEmpty() ? '1' : '0');
                    break;
                case '7':               // 7: 덱에 정수가 있다면 맨 앞의 정수를 출력한다. 없다면 -1을 대신 출력한다.
                    answer.push(deque.printFirst());
                    break;
                case '8':               // 8: 덱에 정수가 있다면 맨 뒤의 정수를 출력한다. 없다면 -1을 대신 출력한다.
                    answer.push(deque.printLast());
                    break;
            }
        }
    }

    console.log(answer.join('\n'));
}

solution(input);

​

결과 값을 한번에 출력해도 되는거면

이런 요구사항은 왜 있는 건지..ㅎㅎ

알 수 없는 백준

​

++

혹시 console.log 때문에 계속 오류가 난건가 하여 두번째 시도 + 결과 값 배열 저장하여 출력해보았는데 역시나 시간 초과가 발생한다 ^^