lv 2 ) 큰 수 만들기

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

프로그래머스

 

그리디 문제

 

 

#include <string>
#include <vector>
#include<iostream>
using namespace std;
/*
st = 0;
end = k;
rt 배열 = 리턴에 대한 배열 ( number 갯수 - k)
loop문
  if rt 배열 다 채워지면 break;
  if ori.len - st == rt.len - rt.newIdx     -> ori와 rt의 현재 자릿 수 동일 그대로 넣기
  ori 배열에서의 st, end 통해 각 자릿수의 최고 값 선정(comp [st idx ~ end idx])
    maxIdx(ori)
  rt 배열[curIdx] = ori배열[maxIdx]
  st = ori의 maxIdx + 1;
  end = ori의 나머지 인덱스 갯수(ori.len - st) - rt 나머지 인덱스 갯수(rt.len - rt. curIdx)
          + st
*/

typedef long long ll;
ll ori[1000001];
ll rt[1000001];
string solution(string number, int k) {
    string answer = "";
    int oriSize = number.size();
    int rtSize = number.size() - k;


    //init
    for (int idx = 0; idx < oriSize; ++idx) {
        ori[idx] = number[idx] -'0';  // -'0' 안할 시 아스키 값으로 넣음
    }
    for (int idx = 0; idx < rtSize; ++idx) {
        rt[idx] = 0;
    }
    int st = 0;
    int end = k;
    int rtCurIdx = 0;
    while (rt[rtSize - 1] == 0) // 값이 채워지면 break loop
    {
        // if ori.len - st == rt.len - rt.newIdx     -> ori와 rt의 현재 자릿 수 동일 그대로 넣기
        if ((oriSize - st) == (rtSize - rtCurIdx)) {
            for (rtCurIdx; rtCurIdx < rtSize; ++rtCurIdx) {
                rt[rtCurIdx] = ori[st++];
            }
            break;
        }
        //ori 배열에서의 st, end 통해 각 자릿수의 최고 값 선정(comp [st idx ~ end idx] 
        //->maxIdx(ori)
        int maxIdx = st;
        for (int idx = st; idx <= end; ++idx) {
            if (ori[idx] > ori[maxIdx]) {
                maxIdx = idx;
            }
        }
        // rt 배열[curIdx] = ori배열[maxIdx]
        rt[rtCurIdx++] = ori[maxIdx];

        //st = ori의 maxIdx + 1;
        //end = ori의 나머지 인덱스 갯수(ori.len - st) - rt 나머지 인덱스 갯수(rt.len - rt. curIdx)+ st
        st = maxIdx + 1;
        end = st + (oriSize - st) - (rtSize - rtCurIdx);
    }
    //ll배열 -> string
    for (int idx = 0; idx < rtSize; ++idx) {
        answer+=rt[idx]+'0';
    }
    return answer;
}

 

1시간 50분 소요(문제에 대한 패턴 찾기 + 구현 + 디버깅)

 

너무 오래걸렸다.  

 

 

 

타인 코드(stack 방식 사용)

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";

    for (char c : number) { 
        while (!answer.empty() && answer.back() < c && k > 0) {
            answer.pop_back();
            k--;
        }
        answer += c;
    }

    if (k > 0) {
        answer = answer.substr(0, answer.length() - k);
    }

    return answer;
}

string 타입 기능 중 back, pop_back 기능 있는 지 처음 알게 됐다...

---

 

내 풀이 (stack 이용)

#include <string>
#include <vector>
#include <iostream>
#include <stack>
using namespace std;

string solution(string number, int k) {
    string answer = "";
    stack<int>st;

    int idx = 0;
    while(idx!=number.size())
    {
        int t = number[idx++] - '0';
        while(!st.empty() && st.top() < t && k != 0)
        {
            st.pop();
            k--;
        }
        st.push(t);
    }
    while(!st.empty())
    {
        string t = to_string(st.top());
        answer = t + answer;
        st.pop();
    }
    // 수가 333222111처럼 작아지는 경우 위 while(!st.empty() && st.top() < t && k != 0)
    // 에서 필터링이 안되는 문제 해결
    if(answer.size() > number.size() - k) 
    {
        answer = answer.substr(0, number.size()-k);
    }
    return answer;
}

 

 

타인코드의 경우 굳이 stack 을 생성하지 않고 주어진 변수 그대로 아름답게 활용하였다. 

 

 

"1231234", k=3 예제

---

풀이 흐름

 

스택: []  k=3

1 push            → [1]        k=3
2 > 1 → pop(1)    → []         k=2
2 push            → [2]        k=2
3 > 2 → pop(2)    → []         k=1
3 push            → [3]        k=1
1 < 3 → push      → [3,1]      k=1
2 > 1 → pop(1)    → [3]        k=0
2 push            → [3,2]      k=0
3 push            → [3,2,3]    k=0  ← k=0이라 이제 그냥 다 push
4 push            → [3,2,3,4]  k=0

결과: "3234" 

---

 

그리디 vs DP(With LLM 설명)

그리디(Greedy) 알고리즘

---

한 줄 정의

"지금 당장 가장 좋은 선택" 을 반복해서 전체 최적을 구하는 방법

---

일상 예시

편의점에서 거스름돈 주기

900원 거슬러줘야 할 때:

 

 

500원 1개  → 남은 400원
100원 4개  → 남은 0원

총 5개

매 순간 "가장 큰 동전부터" 쓰는 게 그리디예요.

왜 이게 최적이냐?

 

 

500원 안쓰고 100원만 쓰면 → 9개 필요
→ 항상 큰 동전이 이득

---

그리디가 성립하는 조건

"지금 최선 = 나중에도 최선" 이 보장될 때만 써요.

 

 

✅ 동전 거스름돈  → 큰 동전이 항상 이득
✅ 큰 수 만들기   → 앞자리 크면 항상 이득
❌ 배낭 문제      → 지금 최선이 나중에 독이 될 수 있음

---

큰 수 만들기에서 그리디가 성립하는 이유

 

 

1924에서 1 vs 9 중 앞자리 선택

9XX > 1XX  ← 뒤에 뭐가 오든 무조건

뒤를 볼 필요 없이 앞자리가 크면 무조건 이득 → 그리디 성립

---

DP(동적프로그래밍)와 차이

	그리디	DP
방식	지금 최선만 선택	모든 경우 저장 후 최적 선택
속도	빠름	느림
적용 조건	제한적	넓음
예시	거스름돈, 큰 수 만들기	배낭문제, 최단경로

---

한 줄 요약: 매 순간 최선을 선택했을 때 전체도 최선이 되는 문제에서 쓰는 알고리즘이에요.

 

 

 

 

 

배낭 문제 (Knapsack Problem)

---

문제 정의

 

 

배낭 무게 한도: 10kg

물건 목록:
A: 무게 6kg, 가치 9만원
B: 무게 5kg, 가치 7만원
C: 무게 5kg, 가치 7만원

최대 가치를 담아라

---

그리디로 풀면?

"가치 높은 것부터 담자" 전략:

 

 

A(9만원) 먼저 담기  → 6kg 사용, 남은 4kg
B(7만원) 담으려면  → 5kg 필요, 못 담음
C(7만원) 담으려면  → 5kg 필요, 못 담음

결과: 9만원

---

실제 최적은?

 

 

A 빼고 B+C 담으면
→ 5kg + 5kg = 10kg
→ 7 + 7 = 14만원

그리디: 9만원 < 최적: 14만원

---

왜 그리디가 실패하냐?

 

 

지금 최선 (A=9만원) 을 선택했더니
→ 나중에 더 좋은 조합 (B+C=14만원) 을 못 씀

즉 "지금 최선이 나중에 독" 이 되는 구조

---

그래서 배낭문제는 DP로 풀어요

 

 

무게 0~10kg 까지
모든 경우를 저장해가면서
최적 조합을 찾음

무게	0	1	2	3	4	5	6	7	8	9	10
A만	0	0	0	0	0	0	9	9	9	9	9
A,B	0	0	0	0	0	7	9	9	9	9	14
A,B,C	0	0	0	0	0	7	9	9	9	9	14

---

한 줄 요약: 배낭문제는 지금 가치 높은 것을 담으면 나중에 더 좋은 조합을 못 쓰게 되기 때문에, 모든 경우를 따져보는 DP가 필요해요.