MakerHyeon

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 아주 쉽지만 자료구조의 중요성을 느낄 수 있었던 문제이다. 해당문제는 리스트를 이용하면 시간초과가 나온다. 1. 맨앞값 삭제 O(N) 2. 맨앞의 값을 맨뒤로 보내기 (삽입,삭제) O(N) X 2 이짓을 1이 남을때까지,즉 N-1번반복하면 N-1 X O(N) 총 복잡도는 O(N^2)이 된다. 따라서 해당문제는 시간복잡도 O(1)인 queue를 이용한다. SOLUTION CODE # PYTHON f..

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 릿코드 문제와 똑같구만... SOLUTION CODE # PYTHON for _ in range(int(input())): stk = [] isVPS = True for ch in input(): if ch == '(': stk.append(ch) else: if stk: # 스택 비어있지않을때 stk.pop() else: # 스택 비어있으면 False isVps =..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 최대로 배정가능한 회의실 수를 구하는 문제이다. 간단히 생각해보자. 내가 회의를 하는 상황에서,회의를 가장 많이하려면 내회의가 빨리끝나야 뒤에 더 많은 회의를 할 수 있을것이다. 즉, 회의 종료시간이 빠르다면 많은 회의를 할 수 있다. 1. 따라서 회의 종료시간순으로 정렬을 한다. 2. 그 후 다음회의의 시작시간>=이전회의의 마감시간이면 해당 회의를 시작한다(회의수+1) 3. 이때, 회의 종료시간이 같다면 (9,10) (10,10) 빠른 시작시간을 가진회의를 선택해야 더 많은 회의를 선택할 수 있을 것이다. 따라..