큰 수 만들기

---

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

프로그래머스

 

---

재귀함수 어려워

통곡의 벽🥲

3시간.. 재귀함수 깨우쳐보겠다고 코드 두드리는데

아놔 모르겠다

재귀 함수를 마음껏 주무르는 날이 올까?

재귀 함수 잘 다루는 사람 보면 멋져죽겠음..

흑흑 문 좀 열어주세요..

---

문제 해석

배열에서 앞에서 하나씩 한글자 뽑고, 나머지에서 고르는 거네..

Combination인거 알겠는데..

구현 어떻게 했더라?

재귀 사용

 

다시 보니까..

Permutation이네.. 순서가 중요하니까

{1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}

 

Combination은 순서가 중요하지 않음

{1,2,3}

---

내가 시도한 코드: 재귀 사용

시벌탱

import java.util.ArrayList;
import java.util.Collections;

public class 큰수만들기 {

	//	https://school.programmers.co.kr/learn/courses/30/lessons/42883
	public static void main(String[] args) {
		큰수만들기.Solution solution = new 큰수만들기.Solution();
		String result = solution.solution("1231234", 3);
		System.out.println("result>>>" + result);

	}

	static class Solution {
		public String solution(String number, int k) {
			String[] splitedArr = number.split("");
			int arrLength = splitedArr.length;//2이상

			ArrayList<Integer> allNumberList = new ArrayList<Integer>();

			// 조사한 것 중에서 가장 큰 숫자를 리턴해라
			for (int i = 0; i < splitedArr.length - k; i++) {
				allNumberList.add(Integer.valueOf(DFS(i, k - 1, splitedArr)));
			}

			return String.valueOf(Collections.max(allNumberList));
		}

		private String DFS(int startIndex, int leftPickNum, String[] splitedArr) {

			if (startIndex >= splitedArr.length) {
				return "";
			}

			if (leftPickNum < 0) {
				return "";
			}

			ArrayList<Integer> allNumberList = new ArrayList<Integer>();

			for (int j = 1; j < splitedArr.length; j++) {
				String temp = splitedArr[startIndex] + DFS(startIndex + j, leftPickNum - 1, splitedArr);
				allNumberList.add(Integer.valueOf(temp));
				System.out.println("temp>> " + temp);
			}

			return String.valueOf(Collections.max(allNumberList));
		}// DFS end
	}//class end
}

 

 

---

재귀함수 사용, but 메모리 초과

import java.util.ArrayList;
import java.util.List;

public class 큰수만들기3 {

	//	https://school.programmers.co.kr/learn/courses/30/lessons/42883
	public static void main(String[] args) {
		큰수만들기3.Solution solution = new 큰수만들기3.Solution();
		String result = solution.solution("4177252841", 4);
		System.out.println("result>>>" + result);

	}

	static class Solution {
		public String solution(String number, int k) {
			int targetLength = number.length() - k;
			List<String> allCombinations = new ArrayList<>();// 값을 담을 List
			generateCombinations(number, "", targetLength, 0, allCombinations);//재귀함수

			// 만들어진 값 중에서 가장 큰 값 찾기
			String maxNumber = "";
			for (String combination : allCombinations) {
				if (combination.compareTo(maxNumber) > 0) {
					maxNumber = combination;
				}
			}

			return maxNumber;
		}

		private void generateCombinations(String number, String current, int targetLength, int index, List<String> combinations) {
			// If the current combination has reached the target length, add it to the list
			if (current.length() == targetLength) {//더이상 빼면 안됨
				combinations.add(current);// 값 추가
				return;
			}

			// If the index exceeds the length of the number, return
			if (index >= number.length()) {
				return;
			}


			//배열의 index 는 하나씩 증가시킨다
			// Include the current character in the combination
			generateCombinations(number, current + number.charAt(index), targetLength, index + 1, combinations);

			// Exclude the current character and move to the next one
			generateCombinations(number, current, targetLength, index + 1, combinations);
		}
	}
}//class end

 

 

---

해결: 그리디 사용

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class 큰수만들기2 {

	//	https://school.programmers.co.kr/learn/courses/30/lessons/42883
	public static void main(String[] args) {
		큰수만들기2.Solution solution = new 큰수만들기2.Solution();
		String result = solution.solution("4177252841", 4);
		System.out.println("result>>>" + result);

	}// main end

	static class Solution {
		public String solution(String number, int k) {
			// 완전 탐색 X, 그리디 O
			//k는 제거해도 되는 수

			// 배열 중에서 가장 큰 값을 선택해서 넣을 Stack
			// LIFO : Last In First Out
			Stack<Character> stack = new Stack<>();
			int len = number.length();

			//각자리에서 시작
			for (int i = 0; i < len; i++) {

				char current = number.charAt(i);//값 꺼내기
				while (!stack.isEmpty()//비어있지 았곤
						&& stack.peek() < current
						&& k > 0) {//뽑을게 있어야함
					stack.pop();// 꺼낸다
					k--;//제거
				}
				stack.push(current);
				// 각 자리, 처음 시작할 때 push
				// 큰 값보다 현재 값이 클 때 push
			}

			// k가 0이 되지 않았다면, 스택에서 k개를 더 pop해줍니다.
			while (k > 0) {
				stack.pop();
				k--;
			}

			// 스택의 모든 요소를 합쳐서 결과 문자열을 만듭니다.
			StringBuilder result = new StringBuilder();
			for (char c : stack) {
				result.append(c);
			}

			return result.toString();
		}// solution func end

	}//class end
}

 

스택 사용 해설

숫자를 왼쪽에서 오른쪽으로 탐색하면서, 스택을 사용하여 가장 큰 숫자를 남기고 작은 숫자를 제거합니다.

요약:

• 스택을 사용하여 숫자를 왼쪽에서 오른쪽으로 순차적으로 처리하면서, 스택의 top보다 큰 숫자가 나오면 스택에서 제거하고 새로운 숫자를 넣습니다. 이 과정을 통해 가장 큰 숫자를 만들 수 있습니다.
• 이 과정에서 k개의 숫자가 제거된 후에 남는 숫자들을 최종적으로 이어 붙여 결과를 얻습니다.

"4177252841"에서 4개의 숫자를 제거하여 "775841"을 얻는 과정이 바로 이 스택을 사용한 그리디 접근 방법의 핵심입니다.

단계별로 스택에 숫자를 넣는 과정:

1. 숫자 4:
   • 스택이 비어 있으므로 스택에 넣습니다.
   • 스택: [4]
2. 숫자 1:
   • 스택의 top에 있는 숫자 4보다 작으므로, 그대로 스택에 넣습니다.
   • 스택: [4, 1]
3. 숫자 7:
   • 현재 스택의 top(1)보다 7이 크므로, 1을 제거하고 7을 넣습니다.
   • 스택: [4, 7]
   • k가 3이 됩니다 (제거한 숫자 1개 때문에)
   • 스택의 top(4)보다 7이 크므로, 4도 제거하고 7을 넣습니다.
   • 스택: [7]
   • k가 2가 됩니다 (제거한 숫자 1개 때문에)
4. 숫자 7:
   • 스택의 top에 있는 숫자 7보다 작지 않으므로, 그대로 스택에 넣습니다.
   • 스택: [7, 7]
5. 숫자 2:
   • 스택의 top에 있는 숫자 7보다 작으므로, 그대로 스택에 넣습니다.
   • 스택: [7, 7, 2]
6. 숫자 5:
   • 스택의 top(2)보다 5가 크므로, 2를 제거하고 5를 넣습니다.
   • 스택: [7, 7, 5]
   • k가 1이 됩니다 (제거한 숫자 1개 때문에)
7. 숫자 2:
   • 스택의 top에 있는 숫자 5보다 작으므로, 그대로 스택에 넣습니다.
   • 스택: [7, 7, 5, 2]
8. 숫자 8:
   • 스택의 top(2)보다 8이 크므로, 2를 제거하고 8을 넣습니다.
   • 스택: [7, 7, 5, 8]
   • k가 0이 됩니다 (제거한 숫자 1개 때문에)
   • k가 0이므로, 더 이상 숫자를 제거하지 않습니다.
9. 숫자 4:
   • k가 0이므로, 그냥 스택에 넣습니다.
   • 스택: [7, 7, 5, 8, 4]
10. 숫자 1:
    • k가 0이므로, 그냥 스택에 넣습니다.
    • 스택: [7, 7, 5, 8, 4, 1]

최종 결과:

이제 스택에 있는 숫자들을 이어 붙이면 "775841"이 됩니다. 이 숫자가 가장 큰 숫자입니다.