해당 문제는 아래와 같은 알고리즘으로 풀이했다.입력받은 수식을 문자열로 저장하고, 문자 하나씩 탐색한다.피연산자의 경우 해당 피연산자에 해당하는 값으로 변환하여 리스트에 순서대로 저장한다. (값으로 변환하기 위해 values 리스트를 사용하고, 해당 값들은 stack에 담긴다.)만약 연산자를 만나는 경우, stack에서 두 값을 꺼내고 해당 연산자에 해당하는 연산을 수행한다.코드는 다음과 같다.import sysinput = sys.stdin.readlinen = int(input())formula = input().rstrip()values = list()stack = list()for i in range(n): values.append(int(input()))for i in formula: ..
Algorithm/Data Structure
해당 문제는 이전에 풀었던 오큰수(17298)과 비슷한 문제다. 단지 while문의 조건만 바꾸어주면 된다. 알고리즘은 다음과 같다.결과를 담을 리스트를 선언한다. 이때 원소들은 모두 -1을 가진다. (result list)각 원소가 몇 번 나왔는지 카운트한 숫자를 담은 dict를 선언한다. (count_dict) 단, 현재 코드에서는 defaultdict를 사용했지만, 그냥 (모든 원소가 0인) 100만까지의 숫자를 담을 수 있는 리스트를 선언해도 된다.stack은 아직 자기보다 많이 나온 수를 찾지 못한 원소들의 인덱스를 담는다. 0번째 인덱스부터 탐색해야하므로 0을 담고 시작한다.반복문을 통해 1번~n-1번 인덱스까지 탐색한다. (탐색 중인 원소를 current_value[=array[i]]라고 하..
해당 문제는 다음과 같은 알고리즘으로 풀이했다.결과를 담을 리스트를 선언한다. 이때 원소들은 모두 -1을 가진다. (result list)stack은 아직 자기보다 큰 수를 찾지 못한 원소들의 인덱스를 담는다. 0번째 인덱스부터 탐색해야하므로 0을 담고 시작한다.반복문을 통해 1번~n-1번 인덱스까지 탐색한다. (탐색 중인 원소를 current_value[=array[i]]라고 하자.)stack에 남아있는 원소가 있고(자기보다 큰 수를 찾지 못한 원소가 있고), 그 원소들 중 가장 오른쪽의 원소와 current_value를 비교했을 때 current_value가 더 크다면, stack에서 가장 오른쪽의 원소를 빼내고, 해당 원소의 NGE값은 current_value로 설정한다. 해당 코드는 다음과 같다...
해당 문제는 다음과 같은 알고리즘으로 풀이했다.레이저는 ()로 표시되어 있다. 따라서 ()부분을 모두 문자 L로 바꾼다. (.replace() 메서드 사용)주어진 문자열(formula)를 탐색한다. 이때 '('부분은 막대가 시작하는 부분으로 막대가 시작하는 부분이 나오면 num_stick에 1을 더해준다. (num_stick은 현재 구간에 있는 막대 개수다.)문자열 탐색 도중 ')'를 만난다면 가장 짧은 막대기 하나가 끝나는 부분이다. 따라서 num_stick에 -1을 해주고, 지금까지 세어준 막대기(result)에 +1을 한다.만약 'L'을 만나면 result에 num_stick을 더해주면 된다. (현재 구간에 쌓여있는 막대 개수만큼 레이저로 잘리기 때문이다.)코드는 다음과 같다.formula = in..
17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 처음에는 해당 문제를 collections 라이브러리의 deque 자료구조를 활용해서 풀었다. 알고리즘은 다음과 같다. 먼저 입력 받은 문자열을 리스트로 변환한다. (리스트로 변환하면 문자열의 각 문자가 원소로 리스트에 들어간다. 예를 들어, "abc" 문자열은 ['a', 'b', 'c']로 들어간다.) 만약 첫 번째 원소가 ''가 나올 때까지 문자를 합쳐준다. '>'가 나온 경우 탐색을 멈추고 태그 내용을 출력한다. 만약 첫 번째..
10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 파이썬 collections 라이브러리의 deque 자료구조를 활용하면 쉽게 구현할 수 있는 문제였다. 코드는 다음과 같다. import sys from collections import deque input = sys.stdin.readline n = int(input()) queue = deque() for _ in range(n): operation = input().rstrip() if operation == "size": print(len..
10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 단순히 문제의 요구대로 구현만 해주면 되는 문제였다. 단, 해당 문제는 First In First Out 구조인 큐를 구현하는 문제였기 때문에 collections 라이브러리의 deque를 활용했다. 코드는 다음과 같다. import sys from collections import deque input = sys.stdin.readline n = int(input()) queue = deque() for _ in range(n): operatio..
1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 처음에는 문제의 요구사항대로 그냥 구현만 해주면 된다고 생각했다. 즉, 커서라는 변수를 하나 선언하고 커서의 위치에 따라 L, D, B, P라는 명령어 각각을 올바르게 수행해주면 된다고 생각한 후 코드를 작성했다. import sys input = sys.stdin.readline ''' L: 커서를 왼쪽으로 한 칸 옮긴다 / 커서가 맨 앞이면 무시한다. D: 커서를 오른쪽으로 한 칸 옮긴다 / 커서가 문장의 맨 뒤면 무시한다. B: 커서 왼쪽에 있는 문자를 삭제..
