[99club/TIL] 4주차 - 금요일 TIL(Today I Learned)

안녕하세요. delay100 입니다. 

---

미들러 문제. 큰수만들기 

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

 

1. 실패 코드 - 런타임 에러

맨 처음 문제를 보고, 백트래킹을 이용해 풀려고 했었습니다.

import java.io.*;
import java.util.*;

class Solution {
    static int[] num;
    static boolean[] isVisited;
    static int numberLength;
    static int max;
    static StringBuilder sb = new StringBuilder();
    public String solution(String number, int k) {
        numberLength = number.length();
        num = new int[numberLength];
        isVisited = new boolean[numberLength];
        max = 0;
        
        for(int i=0; i<numberLength; i++) {
            num[i] = number.charAt(i) - '0';
        }
        
        func(0, 0, numberLength-k);
        String answer = Integer.toString(max);
        return answer;
    }
    
    /**
    * 백트래킹
    * @param i 현재까지 순회한 num의 index
    * @param n 지금까지 담은 수의 길이
    * @param k 총 만들어야할 수의 길이
    */
    public static void func(int i, int n, int k) {
        if(k == n) {
            solve();
            return;
        }
        if(i >= numberLength) return;
        isVisited[i] = true;
        func(i+1, n+1, k);
        isVisited[i] = false;
        func(i+1, n, k);
    }
    
    /**
    * 백트래킹의 종료 시점에 실행되는 함수
    */
    public static void solve() {
        sb.setLength(0);
        for(int i=0; i<numberLength; i++) {
            if(isVisited[i]) {
                sb.append(num[i]);
            }
        }
        // System.out.println(sb.toString());
        int a = Integer.parseInt(sb.toString());
        if(max < a) {
            max = a;
        }
    }
}

테스트 2~10까지 런타임 에러 발생

그런데 테스트 2~10까지 런타임에러가 발생했습니다..

 

2. 성공 코드 

도저히 모르겠어서 검색해본 결과 그리디하게 푼 코드들이 많이 있었습니다.

** 그리디하게 푼다는 것은 현재 상태에서 가장 좋은 것을 택하며 진행하는 방법입니다.

문제를 해결한 방법은 스택을 이용해 현재 도달한 num값이 가장 크도록 만들어주었습니다.

즉, 앞 자리수가 가장 크도록 만들어주었습니다.

빼야하는 개수인 k값이 정해져있기 때문에 앞에있는 자리의 값이 크면 큰 값이 됩니다.

k가 0이 되는 경우에는 계속 push만 하게 됩니다.

import java.io.*;
import java.util.*;

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder();
        int numberLength = number.length();
        int size = numberLength-k;
        Stack<Integer> stk = new Stack<Integer>();
        
        // number을 순회하면서 각 값을 꺼냅니다.
        for(int i=0; i<numberLength; i++) {
            int num = number.charAt(i) - '0';
            // 아래의 3가지 경우를 만족하면 while문 실행
            // 1. 스택에 값이 존재
            // 2. 빼야하는 개수 값인 k가 존재
            // 3. 스택의 가장 위에있는 값이 현재 나온 값보다 작은 경우
            while(!stk.empty() && k > 0 && stk.peek() < num) {
                k--; 
                stk.pop();
            }

            stk.push(num); 
        }
        
        for(int i=0; i<size; i++) {
            sb.append(stk.get(i));
        }
        
        return sb.toString();
    }
}

[해결에 참고한 블로그]

 

https://kyeahen.github.io/algorithm/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-42883-%ED%81%B0-%EC%88%98-%EB%A7%8C%EB%93%A4%EA%B8%B0/

[프로그래머스] 42883 큰 수 만들기

 

---

+ 비기너 문제

나머지가 1이 되는 수 찾기 (https://school.programmers.co.kr/learn/courses/30/lessons/87389)

프로그래머스

+ 챌린저 문제

바이러스 (https://www.acmicpc.net/problem/2606)

2606번: 바이러스

---

감사합니다. 피드백 환영합니다.