[Coding Test]/[백준]

[백준] 5397 파이썬(python) : 키로거 - 이중stack

https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 커서를 이동하는 부분에서 이전에 풀었던 1406번(에디터) 문제가 생각났다. 왼쪽으로 커서를 움직일때 다른 스택에 가장 위 값을 넣고 커서를 오른쪽으로 옮기면 다른 스택에서 원래 스택으로 다시 옮겨오는 방식이다. 이렇게 하면 append와 pop만 사용하기 때문에 O(1)로 문제를 해결할 수 있다. import sys t = int(sys.stdin.readline()) for _ in r..

[백준] 3986 파이썬(python) : 좋은 단어

https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 처음에 문제를 볼때 이걸 어떻게 스택으로 풀 수 있지 생각했는데 이전에 풀었던 괄호 짝 맞추기 문제들 처럼 같은 알파벳끼리 짝을 맞춰주면 풀 수 있다. 문제에서는 아치형 곡선이라고 말했는데 여는 괄호를 닫는 괄호와 짝이 맞는지로 바꿀 수 있다. ABAB는 3번째 위치의 A가 들어올 때 stack[-1]이 A가 아니므로 좋은 단어가 아니다. AABB는 2번째 위치의 A가 들어올 때 stack[-1]가 A이므로..

[백준] 1918 파이썬(python) : 후위 표기식

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net import sys string = list(sys.stdin.readline().rstrip()) res = '' #1 stack = [] #2 for char in string: if char.isalpha(): #3 res += char else: if char == '(': #4 stack.append(char) elif char == '*' or char == '/': #5 while..

[백준] 1935 파이썬(python) : 후위 표기식2

https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net import sys n = int(sys.stdin.readline()) string = sys.stdin.readline().rstrip() number = [] for _ in range(n): number.append(int(sys.stdin.readline())) stack = [] for char in string: if char.isalpha(): #1 stack.append..

[백준] 2504 파이썬(python) : 괄호의 값 - (★)

https://www.acmicpc.net/problem/2504 2504번: 괄호의 값4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.  만일www.acmicpc.net   여는 괄호는 받을 때는 스택에 삽입과 함께 그 값을 저장, 첫번째 닫는 괄호가 나오면 이제까지의 값 모두 res에 옮김 그리고 괄호값만큼 나눠준다.  ( ( ) [ [ ] ] ) 일때 값의 변화괄호(()[[]])tmp242618621res00444222222  닫는 괄호 ) 가 나왔을 때  if len(stack) == 0 or stack[-1] != '(' 여기서 안걸린다면 여는 괄호 (과 ..

[백준] 1406 파이썬(python) : 에디터 - 이중stack

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 시간이 오래걸리는 insert대신 append를 del 대신 pop을 사용하면 O(1)로 문제를 해결할 수 있다. 왼쪽으로 커서 이동은 top에 있는 원소를 다른 스택에 옮기고, 오른쪽으로 커서 이동은 다른 스택의 top에서 원래 스택으로 옮기는 방식이다. import sys string = list(sys.stdin.readline().rstrip()) #1 string2 = [] #2 n = i..