Greedy(16)_크게만들기(2812)

작성일 | In

BJO 2812 크게만들기

N자리의 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있 는 가장 큰 수를 구하는 프로그램을 작성하시오

첫째 줄에 N과 K가 주어진다. 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

정렬을 이용해서 풀 수 있지 않나 싶었는데, 숫자를 지웠을 때, 얻을 수 있는 가장 큰 수를 구해야 하므로. 안될 것 같다.

Stack을 이용해보자.

헤맸던 이유

논리연산자 사용시, 항상 첫번째 온 조건부터 먼저 검사한다. 따라서 어떤 논리연산자를 우선 검사할 건지 여부가 매우 중요하다. 이를 잊어버리고 있었다.

while문은 가독성이 떨어져서 선호하지 않는다. 하지만 횟수를 모르고, 조건에 맞게 반복해야 할 때는 while문이 필요하다. 집중하자

코드

import sys
stack = []


def push(data):
    stack.append(data)


def pop():
    if(len(stack) == 0):
        return -1

    else:
        return stack.pop(-1)


if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().split())
    text = sys.stdin.readline().rstrip()
    # i = 0
    # while(i != len(text)):
    for i in range(N):
        while(M != 0 and len(stack) != 0 and stack[-1] < text[i]):
            pop()
            M -= 1
        push(text[i])
        i += 1
    # while(M > 0):
    for i in range(M):
        # M -= 1
        pop()
    print("".join(stack))

주의해야할 것.

리스트에서 가장 큰 값 구한 뒤 N과 빼준 다음에, 그 값을 누적해주면 hamming Distance를 구할 수 있다.

참고자료

0%