Stack

올바른 괄호 문제 바로가기 첫 번째 풀이 def solution(s): while '()' in s: s=s.replace('()','') if s == '': return True else: return False 두 번쨰 풀이 def solution(s): stack = [] for i in s: if i == "(": stack.append(i) else: if stack: stack.pop() else: return False if stack: return False else: return True 고수의 풀이 def is_pair(s): st = list() for c in s: if c == '(': st.append(c) if c == ')': try: st.pop() except IndexError: return False return len(st) == 0 출처 CODE REVIEW 첫 번째 풀이에서는 while문을 이용해서 ()가 있으면 계속 지워나가는 식으로 해결했다. 정답에는 이상이 없었지만, 효율성 측면에서는 떨어졌다. 효율성을 늘리기 위해서 다른 방법을 시도해보았다. 두 번째 풀이에서는 stack을 이용했는데, (을 stack에 쌓아가면서 조건에 따라 지워가면서 true/false을 결정했다. 고수의 풀이는 앞의 풀이와 거의 동일하지만 return len(st) == 0 부분이 마음에 들어서 가져왔다. 매우 비슷한 문제로 백준 9012번 - 괄호가 있다.

백준 1874번 바로가기 나의 풀이 n = int(input()) stack = [] arr = [] ans = [] i = 1 for _ in range(n): num = int(input()) arr = [num] + arr while i <= num: stack.append(i) ans.append('+') i += 1 if stack[-1] == num: stack.pop() arr.pop() ans.append('-') if stack[::-1] == arr: print(*ans, sep="\n") for _ in range(len(stack)): print('-') else: print("NO") CODE REVIEW 예제를 이해하는 것부터 쉽지 않은 문제였다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써,부분이 모호해서 헷갈렸는데 차라리 1부터 n까지의 수를 차례대로 넣고 빼는 과정을 반복하면서 표현이 실제 실행 방식에 가깝지 않나 싶긴 하다. 이것도 애매하긴 마찬가지지만… input을 받는 arr, 주어진 수열을 stack list에 저장해서 비교해가며 문제를 해결했다. n까지 넣은 뒤에는 남은 숫자들을 비교했을 때 stack[::-1] == arr만족하지 않으면 NO, 만족한다면 저장해둔+- 결과를 출력해주면 된다.

백준 10773번 바로가기 나의 풀이 arr = [] for _ in range(int(input())): if (n:=int(input())) == 0: arr.pop() else: arr.append(n) print(sum(arr)) CODE REVIEW 실버 VI가 맞나 싶을 정도로 쉬웠던 문제. list와 pop() append() 메소드에 대한 이해도만 있으면 쉽게 해결 가능하다.

백준 4949번 바로가기 생각보다 간단하게 풀린 문제였다. 다만, 문제조건을 잘못 봐서 초기에 조금 헤맸다. n 이상인지 이하인지에 주의하고 범위설정에 유의해야겠다. 이 문제의 경우 1,000,000이 input으로 주어질 경우 output이 없는 문제가 발생하는데 범위를 1,005,000까지 여유있게 잡아주면 문제 없이 실행된다. 그외에는 팰린드롬과 소수판별 알고리즘만 짤 수 있다면 쉽게 해결 가능한 문제였다. while True : a = input() temp = [] if a == "." : break for i in a : if i == '[' or i == '(' : temp.append(i) elif i == ']' : if len(temp) != 0 and temp[-1] == '[' : temp.pop() else : temp.append(']') break elif i == ')' : if len(temp) != 0 and temp[-1] == '(' : temp.pop() else : temp.append(')') break if len(temp) == 0 : print('yes') else : print('no') 고수의 풀이 while(l:=input())!='.': s='' for i in l: if i in'()[]':s=(s+i).replace('()','').replace('[]','') print('yneos'[s>''::2]) CODE REVIEW 백준 9012번문제와 유사하면서도 따로 신경써줘야 할 것이 많은 문제. 처음에는 re이용해서 특수문자만 추출했는데, 자꾸 이해할 수 없게 에러나길래 그냥 input()그대로 사용하였다. 고수의 풀이에서 if i in '()[]':이후에 .replace('()','').replace('[]','')이 신박했다. 이것저것 따질 필요 없이 한큐로 해결 가능하다니…?!

백준 9012번 바로가기 나의 풀이 for _ in range(int(input())): bracket = list(input()) score = 0 for i in bracket: if score < 0: print('NO') break else: if i == '(': score += 1 else: score -= 1 else: if score != 0: print('NO') else: print('YES') 고수의 풀이 for _ in range(int(input())): b=input() while '()' in b: b=b.replace('()','') print("YES" if b='' else "NO") 참고 출처 CODE REVIEW 예전에 창의력 수학 문제를 풀다가 비슷한 논리를 본 기억이 있다. 산 모양 그래프로 풀어내는 문제였다. 고도 0에서 시작해서 고도 0으로 끝나는 산을 생각해보자. 이 산은 중간에 땅을 뚫고 고도가 0 미만으로 떨어지면 안된다. 아래 그림에서 주황색처럼 중간에 중간에 땅을 뚫고 들어가거나 파란색이나 초록색처럼 마지막에 고도가 0이 아니면 안된다. 코드에서도 마찬가지 논리로 score이 중간에 음수로 가는지, 끝에서 0인지를 체크하며 NO, YES을 출력했다. (바람직한 산의 모양) ...