m1ndy5's coding blog

https://www.acmicpc.net/problem/2493 사실 아이디어는 바로 떠올랐지만 당연히 시간초과가 나는 코드란 걸 알았기에 무슨 방법이 있는지 고민을 해보았다. 키포인트는 중간에 우뚝 솟은 탑이 있다면 그 앞은 고려할 필요가 없다는 것이다. 하지만 그 뒤는 고려를 해줘야하는게 높이가 1 4 3 2 인 탑이 있다면 2은 4에 걸리는 것이 아니라 3에 걸리기 때문이다. 따라서 오른쪽부터 훑으면서 앞쪽의 탑들이 자신보다 낮으면 스택에서 빼고 높다면 그 탑이 자신이 발사하는 레이저에 걸리는 탑이 된다.(break) 그리고 자신도 그 뒤쪽 탑에겐 높을 수 있으므로 자신도 stack에 push 해야한다. 만약 앞쪽 탑들이 다 빠지고 자신밖에 스택에 없다면 자신보다 높은 탑이 없으므로 0을 appe..

https://www.acmicpc.net/problem/10799 import sys sticks = sys.stdin.readline().rstrip() op = 0 cnt = 0 for i in range(len(sticks)-1): if sticks[i] == '(' and sticks[i+1] == ')': cnt += op elif sticks[i] == sticks[i+1]: if sticks[i] == '(': op += 1 else: cnt += 1 op -= 1 print(cnt)생각한 방법은 () 레이저 발사할 때 기준으로 몇개의 괄호가 열려있는지(몇개의 막대가 있는지)를 고려했다. (((이렇게 3개가 열려있으면 일단 한번 자르면 3조각이 생..

https://www.acmicpc.net/problem/1874 사실 문제이해를 못해서 문제가 뭔말인지 다른 브로그 읽어본건 안비밀ㅎ 오름차순으로 들어간다는게 작은수 -> 큰수로 들어간다라고 이해를 해서 엥 뭐지?했는데 알고 보니 4를 pop하려면 1, 2, 3, 4 이렇게 push를 해야한다 라는 말이었다. 이렇게 스택에 push pop하면서 입력받은 수열을 만들면 성공, 만들지 못하면 NO를 출력하는 문제였다. import sys n = int(sys.stdin.readline().rstrip()) stack = [] last = 0 o = '' for _ in range(n): i = int(sys.stdin.readline().rstrip()) if i not in stack: f..

https://www.acmicpc.net/problem/1406 왜 이문제가 실버 2일까~~ 했더니만 역시나 시간초과!!ㅎㅎ import sys s = sys.stdin.readline().rstrip() c = len(s) n = int(sys.stdin.readline().rstrip()) for i in range(n): com = sys.stdin.readline().rstrip() if ' ' in com: com, letter = com.split() if com == 'L': if c != 0: c -= 1 elif com == 'D': if c != len(s): c += 1 elif com == 'B': if c != 0: c -..

https://www.acmicpc.net/problem/1935 이 문제는 먼저 코드를 보기전에 후위 표기식이란 무엇인지를 알아야한다. 예를 들어 (A+B) * 2 + B/C 라는 식을 트리 형식으로 나타내보자. 이런 형식이 될 것이고 후위 표기식은 left => right => center 순으로 읽으면 된다. 따라서 위 식을 후위 표기식으로 표현하면 A B + 2 * B C / + 가 된다. 반대로 후위 표기식으로 표현된 식을 계산하는 방법은 숫자일 때는 스택에 push하고 연산자가 나오면 숫자 두개를 pop해 연산을 진행한 후 다시 스택에 push하는 것이다. 이 때 중요한 것이 +나 * 는 상관없지만 -나 / 같은 경우 뒤의 숫자가 먼저 나오므로 순서에 유의하여 문제를 풀어야한다. import ..

https://www.acmicpc.net/problem/10773 import sys k = int(sys.stdin.readline().rstrip()) stack = [] s = 0 for i in range(k): n = int(sys.stdin.readline().rstrip()) if n == 0: p = stack.pop() s -= p else: stack.append(n) s += n print(s)0이 들어오면 pop하고 sum에서도 빼주는 것이 키포인트였다.

https://www.acmicpc.net/problem/9012 import sys stack = [] def push(num): stack.append(num) def pop(): if len(stack) == 0: return -1 n = stack.pop() return n n = int(sys.stdin.readline().rstrip()) for i in range(n): s = sys.stdin.readline().rstrip() stack = [] for ch in s: if ch == '(': push(1) if ch == ')': result = pop() if result == -1: stack.append(1) break if len(stack) == 0..

https://www.acmicpc.net/problem/10828 왜 이문제가 실버지..? 했는데 input()으로는 시간초과가 나는 문제였다. input() 대신 sys.stdin.readline().rstrip() 을 사용하면 시간초과가 해결되는 문제였다. 참고로 sys.stdin.readline()을 사용하려면 import sys를 해줘야한다는 점!! import sys stack = [] def push(num): stack.append(num) def top(): if len(stack) == 0: return -1 return stack[len(stack)-1] def size(): return len(stack) def empty(): if len(stack) == 0: return 1 r..