[알고리즘/그리디] 2812번 : 크게 만들기 - python

링크 : https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

 

---

• 문제
• 소요시간: 40분 실패

---

• 설계하기(접근방법) 

1. 입력받기

조건대로 입력받는다

 

2. 구현하기

처음에는 구현을 해버렸다

지금 숫자와 다음 숫자를 비교해서

다음 숫자가 크면 다음 숫자로 바꿔주고

 

지금 숫자가 크다면

앞에서 부터 1자리씩 줄여가면서 크기를 비교하고

다음 숫자가 큰 경우가 생기면

그 부분만 떼서 교체해준다

 

예를 들어

 

10 4

4177252841 일때

1 : 417725

2 : 417725 > 177252

3 : 417725 < 772528

4 : 772528  > 725284

72528 > 25284

2528 < 5284

->

77 + 5284 = 775284

..... 이러식으로 했으나 당연히 시간이 초과되었다

 

다른 사람의 풀이를 살펴보니

시간 내의 풀이는 stack으로 푸는 것이다

 

숫자를 앞에서부터 stack으로 밀어 넣는다

 

만약 스택 상단의 숫자 < 들어올 숫자

라면 stack을 pop하고 넣는다

 

이 과정은 스택이 비거나, 들어올 숫자보다 크거나 같은 숫자가 나타날때까지 반복한다

stack을 팝하는 행위는 지우는 행위와 동일하니, k 에서 1씩 빼준다

 

k가 0일 될때까지 반복한다

 

 

 

 

 

 

3. 출력하기

스택내의 숫자를 join 함수를 통해 출력한다

 

 

---

• 코드(출력)

n , erase = map(int, input().split())
number = input()

start = int(number[0 : n - erase])
print(start)
i = 1
while i < n - erase - 1:
    if start <= int(number[i: n - erase + i]):
        start = int(number[i: n - erase + i])
        i += 1
        continue
    else: 
        str_start = str(start)
        j = 0
        while  j  < n - erase:
            if  int(str_start[j: n - erase]) < int(number[i + j: n - erase + i]):
                start = int(str_start[0 : j] + number[i + j : n - erase + i])
                break
            else:
                j += 1
        i += 1
        
print(start)

- 시간초과 코드

---

• 얻어갈 부분
• 이해하기 어려운 문제였다. 왜 어려웠는지 다시 생각을 해보자