스택을 활용한 문제이다. 처음에는 그냥 조합을 이용해서 풀었는데 예상했지만 역시나 시간초과가 발생했다. 저번주에 필기시험이 있어서 잠시 코테를 쉬었더니 알손실이 왔다. 그래서 바로 풀지 못했다. (TMI..)
아무튼 내가 스택을 활용한 풀이에 약한 것 같다. 문제를 보고 스택을 활용한 풀이라는 것은 이해가 갔지만, 막상 적용이 안됐다.
맨 뒤의 원소를 비교하는 것은 for루프를 돌면서 while루프를 돌리면 되는데, 왜 생각이 안났을까...? 아무튼 문제 해설을 시작한다.
이 문제와 유사하게 스택을 활용하는 문제들을 뽑아놨다. 이번주 주말에 코테보기 전에 꼭 풀어봐야겠다.
큰 수 만들기, 괄호변환, 같은숫자는 싫어, 나누어 떨어지는 숫자, 짝지어 제거하기, 문자열 압축
1. 문제 설명
number로 숫자가 문자열 형태로 주어진다. 이때 k개의 숫자를 문자열에서 제거했을 때 나올 수 있는 가장 큰 수를 구하는 것이다.
2. 어려웠던 점
1) 조합
이런 문제를 보면 항상 생각나는 것이 조합이다. 물론 조합으로 풀 수 있지만 시간초과가 발생한다. 주어지는 조건을 보면
number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
이렇게 되어있어서 당연히 시간초과가 발생할 것이라고 생각했다.
def solution(number, k):
order_list = set()
for order in combinations(range(len(number)), k):
temp = tuple(sorted(order))
order_list.add(temp)
result = []
for pick_order in order_list:
temp = ""
for ord in range(len(number)):
if not ord in pick_order:
temp += number[ord]
result.append(int(temp))
return str(max(result))시간초과 발생했음
2) 스택을 활용한 풀이
스택을 활용한다는건 느낌이 왔으나, 뭔가 헷갈렸다. 항상 생각하는 것이지만.. 스택을 활용한 풀이는 맨날 헷길란다.
처음에는 스택을 선언하고, 와일 루프를 돌면서 스택의 맨 마지막 원소와 현재 p 번째에 있는 num의 수가 큰지 크지않은지의 여부를 확인해서 리턴하려고 했다.
이렇게 짜고 나서 보니, p값에 대한 처리가 매우 애매모호했다. 와일 루프를 돌때마다 p값은 갱신을 해줘야 하는데, 스택에 있는 맨 마지막 원소가 비교 대상보다 크다는 것을 확인하고 p값을 갱신해주면 그 다음 원소가 더 클 수도있었다.
항상 이 부분이 헷갈린다. 루프를 돌면서 비교를 하는데, 인덱스 처리는 어떻게 할 것인지? 그렇다고 삭제하면 인덱스에 혼동이 생기기 때문에 스택을 따로 선언하고 비교해줘야 하는게 맞다.
아무튼 결론은, 스택을 따로 선언하되 for루프를 돌면서 원소를 갱신해주고 루프 내에서 while루프를 돌면서 조건을 모두 처리해줘야 한다.
3. 풀이
def solution(number, k):
answer = []
for num in number:
if not answer:
answer.append(num)
continue
if k > 0:
while answer[-1] < num:
answer.pop()
k -= 1
if not answer or k <= 0:
break
answer.append(num)
answer = answer[:-k] if k > 0 else answer
return ''.join(answer)