꾸준하게 거북이처럼

1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 처음에 떠올린 문제풀이 방법은 list를 이용해서 insert 나 del 함수를 이용하는 것이었다. 하지만 이 문제는 시간제한이 0.3초로 짧았고, 시간 초과가 났다. 아무래도 최대 명령어 개수가 50만이고, insert만한다면? 파이썬 list 에서 insert의 시간 복잡도는 O(N)이므로, 또한 여기서 최대 문자열 길이는 60만이므로, 50만 * 60만 => 3천만 연산 + 다수의 if문 존재.. 시간 초과가 나기 쉽다. 이쯤되면 pop이나 append와 같..

1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 1 부터 n까지 오름차순으로 오직 stack의 push와 pop만으로 입력받은 수열을 만들 수 있는지 확인하는 문제이다. 예제를 보면서 직접 stack이 pop이 되고 push가 되는 과정을 그려보면 크게 두 가지로 나뉜다. 1. 입력받은 수열 arr1의 원소가 arr2(1~ n까지 수를 pop/push 하는데 사용될 stack)배열에 이미 존재한다면 pop 2. 존재하지 않는다면..

arr = input() stack = [] result = 0 for i in range(len(arr)): if arr[i] == '(': stack.append(arr[i]) else: stack.pop() if arr[i-1] == '(': result += len(stack) else: result += 1 print(result) # 레이저로 쇠막대기를 자르려고 한다. 총 쇠막대기 조각 수를 구하자. # 여는 괄호와 가장 인접한 닫는 괄호 () 이 부분이 레이저이고 나머지 부분 여는 괄호부터 닫는 괄호까지는 쇠막대기 이다. # 문제를 천천히 이해하면서 문제가 알려주는 그대로 손으로 쓰면서 또는 그림을 그려가면서 문제 풀이를 생각해보자. # 여는 괄호는 stack에 추가, 만일 닫는 괄호 바로 ..

알고리즘에서 중요한 자료구조 스택에 관련된 문제를 풀어보았다. 스택하면 LIFO 마지막에 참조한 원소를 먼저 pop한다는 것을 알고 있어야한다. number , m = map(int,input().split()) number = list(map(int,str(number))) stack = [] for value in number: while stack and m > 0 and stack[-1] < value: stack.pop() m -= 1 stack.append(value) if m != 0: stack = stack[:-m] for value in stack: print(value, end='') # 주어진 수 number에서 주어진 수 m개의 수를 제거할 때 가장 큰 수를 만들어야한다. # 여기..