(TIS) 20210511

들어가며

이 시리즈는 누군가가 읽을 것을 가정하는게 아닌, 단순 자기 기록용 글이라 정리가 하나도 되어있지 않다. 이제부터 꾸준히 문제를 풀어나가며 얻어가는걸 적어나갈 예정이다.

문제

programmers '124 나라의 숫자' : 진수관련문제

programmers '큰수만들기' :

되게 진을 뺐다. 자료구조에 대한 지식은 있지만 아직 이를 활용하기까지에는 연습이 좀 필요한 것 같다.
stack을 활용하는 좋은 문제였어 기록한다.
출처 : 프로그래머스

핵심은 'k'번 숫자를 제거할 수 있다와, 어떤 식으로 숫자를 기록해 나갈지이다.
처음에는 재귀를 통해 문제를 풀었다. 다만 풀고나니 무한루프를 돌기도하고 성능이 너무 좋지 않았다. 이후에 꾸역꾸역 풀어서 해결했지만 다른 분의 답안이 너무 좋아 가져와 보았다.

'stack'을 이용하셨다.

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack)>0 and stack[-1] < num and k > 0:
            stack.pop()
            k -= 1
        stack.append(num)
    
    if k != 0:
        stack = stack[:-k]
    
    return ''.join(stack)

숫자가 커지려면 우선 앞 자리가 가장 중요하다는 것 또한 포인트이다.
while문이 문제풀이의 핵심이었다. 만약 k가 0이상, 즉 뺄 수 있는 횟수가 남아있고, 이번 숫자가 stack의 마지막 숫자보다 크다면 바로 앞 숫자를 제거해 나가는 식이다.

또한 k != 0 구절을 이용해 아직 뺄 기회가 남았지만 이미 앞부분에 최고 큰 조합이 나온경우! 이 때는 마지막 k개를 빼는 형식으로 진행한다.

--> stack의 활용성에 대한 문제이다. 좀 더 자료구조적 지식을 활용하도록 노력해보자.

오늘의 배운점

  • 재귀함수를 아래 코드를 이용해 제한을 풀어주자
    import sys
    sys.setrecursionlimit(10**10)
  • 수학적으로 풀려고는 왠만하면 하지 말자
    -> 이러면 자료구조적으로 사고하는 능력이 늘지를 않는다.

좋은 웹페이지 즐겨찾기