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

항해99/99club1기TIL

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

delay100 2024. 4. 19. 22:41

728x90

SMALL

안녕하세요. delay100 입니다.

미들러 문제. 큰수만들기

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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

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. 성공 코드

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

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

문제를 해결한 방법은 스택을 이용해 현재 도달한 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();
    }
}