링크 : https://www.acmicpc.net/problem/2493 문제소요시간: 40분 10초(부분 실패)설계하기(접근방법) 1. 입력받기타워의 높이를 입력받는다 2. 구현하기처음에는 탑의 위치를 지정해가면서 순회했으나 시간초과가 났다.방법이 떠오르지 않아 카테고리를 확인했고, 스택을 쓰는 문제였다는 것을 확인할 수 있었다 따라서 스택으로 코드를 구현했다자기보다 작은 높이가 스택에 있는 경우, 자기보다 큰 높이가 나올때 까지 pop해준다즉 큰 높이를 마주했을 때가 레이저를 마주했을 때와 같다.그 후 자신의 높이를 stack에 append 해준다. stack이 비어있거나, 자신보다 큰 높이를 찾지 못한 경우, 0을 저장해주고자신을 스택으로 append한다 3. 출력하기저장한 laser의 위치를 ..
링크 : https://www.acmicpc.net/problem/5430 문제소요시간: 48분 52초설계하기(접근방법) 1. 입력받기리스트가 숫자로 주어지는 것이 아닌 문자열로 주어지기에 고민해야한다 먼저 split(,)으로 문자열을 나누어준 후,왼쪽 끝과 오른쪽 끝의 괄호를 제거해준다 또한 배열의 원소 수가 많기 때문에 앞쪽의 원소를 제거하다 시간초과가 날 수 있다.deque를 통해서 popleft를 사용할 수 있도록 해주자 2. 구현하기 입력받은 deque를 R일 때는 pop()을정방향일 때는 popleft()를 수행할 수 있도록 짝수 홀수 카운터를 선언한다 중간에 배열이 비어버린 경우에 D를 수행한다면 error을 출력하고 다음 케이스로 넘어갈 수 있도록 구성하자 3. 출력하기 결과로 나온 리..
링크 : https://www.acmicpc.net/problem/19638 문제소요시간: 17분 53초설계하기(접근방법) 1. 입력받기입력이 10만개이니 sys를 통해 입력받는다 2. 구현하기 가장 키가 큰 거인에게 망치를 쓴다는 조건이 주어졌다거인이 10만명이니 리스트에서 매번 큰 거인을 찾는다면 시간이 초과될 것이다 따라서 heapq를 사용하여 가장 키가 큰 거인을 빠르게 찾을 수 있도록 구성해야 한다 입력받은 거인의 키에 (-1)을 곱해 거인의 키를 heappush 해준다 거인의 키가 입력되었으면 시도만큼 망치를 때리면서 1/2 floor을 해준다 문제에서 키가 1인 경우에는 더 이상 줄어들징 않는다고 했으니,망치를 치기 전에 가장 키가 큰 거인의 크기가 1인지 아닌지 검사해야한다.while문을..
링크 : https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net 문제 소요시간: 22분, 실패 설계하기(접근방법) 1. 문자열을 입력받는다, 스택을 선언한다 2. 알고리즘 해석 1) 만약 괄호가 열리면, stack에 append하고 괄호 내의 숫자는 후에 2or 3만큼 곱해진다 따라서 tmp 를 선언하여 그 변수를 제어해준다. 2) 괄호가 닫히고, 그 직전 괄호가 그 괄호의 쌍'()' or '[]' 이였다면 지금까지 곱해진 tmp만큼 ans에 더..
링크 : https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 소요시간: 21분 12초 설계하기(접근방법) 1. n을 입력받는다, heapq를 두 개 선언한다 2. 알고리즘 해석 1) x = int(input()) 을 받는다 x > 0 이면 heap_plus에 (x)를 x < 0 이면 heap_minus에 (-x)를 heappush 한다 x = 0일 때는 i) heap_plus, heap_minus 둘 다 원소가 있을 때 ..
링크 : https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 문제 소요시간: 24분 12초 설계하기(접근방법) 1.더 이상 입력일 없을 때까지 입력을 받는다 tree =sys.stdin.readline()을 입력으로 받은 후, if not tree: 로 조건을 설정하여 비어있다면 break을 해준다 2. tree_list(딕셔너리) 에 입력값이 없다면 트리를 딕셔너리에 추가한 후 1 그루를 value 값으로 정해준다 tree_list 내..
링크 : https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 소요시간: 개념 배우기 설계하기(접근방법) 1. n을 입력받는다, heap을 초기화한다 2. 알고리즘 해석 x를 n번 입력받는다. 0이 아닌 경우 -> heap에 heappush()를 한다. 다만 우리가 필요한 것은 최대 값이니 인자를 -x로 push 해주어야 한다 0인 경우 -> heap에 원소가 없는 경우 0 출력 -> heap에 원소가 있는 경우 heap..
링크 : https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 문제 소요시간: 15분 실패 설계하기(접근방법) 1. n, m을 입력받는다 2. 집합 s를 입력받고, 단어를 입력받으며 s 내에 있는지 검사한다 있다면 cnt += 1을 해준다 3.print(cnt) (실패 이유) m과 n 을 곱하면 연산량이 1억번이 넘어가므로 일반적인 리스트로는 시간이 초과된다. 파이썬의 딕셔너리 기능을 이용하면 키값을 통해 연산을 O(..
