QQ의 다이어리

문제 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 풀이 백준 9012번 문제와 유사하지만 이 문제는 (), [] 2개의 괄호가 있고, 각 괄호가 감싸는 문자열 또한 짝이 맞아야 한다. ([abc)]와 같은 경우는 안 된다. 따라서 현재 스택의 맨 위에 있는 괄호가 ( 인지 [ 인지 확인하는 것이 필요하다. 1) 괄호를 입력받으면 스택에 추가한다. 2) 닫는 괄호이면서, 스택이 비어있지 않고, '입력받은 괄호 == 스택의..

문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 탐색하려는 배열에 중복이 있다면 target이 되는 수를 찾아내도, 이 수가 몇개 있는지는 알아낼 수 없다. 따라서 algorithm 헤더의 upper/lower_bound를 사용하면 target이 되는 수들의 마지막 주소와 시작 주소를 얻을 수 있다. 따라서 upper_bound - lower_bound를 계산하면 총 개수도 계산할 수 있다. 코드 #..

문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 이분탐색을 이용하여 수를 찾는 문제이다. 탐색하려는 배열을 정렬한 후, 찾으려는 수가 배열의 중간값보다 크면 중간값 이전 값들은 고려하지 않고, 배열의 중간값보다 작다면 중간값 이후의 값들은 고려하지 않는다. 계속 범위를 줄여가다가 1) 중간값과 찾으려는 수가 일치하거나, 2) 배열의 크기가 0이 되어 끝을 가리키는 인덱스가 처음을 가리키..

문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 풀이 입력받은 문자열을 돌다가 1) 여는 괄호를 만나면 stack에 push한다. 2) stack이 비어있지 않은 상태에서 닫는 괄호를 만나면 pop 한다. 3) stack이 비어있는 상태에서 닫는 괄호를 만나면 false 입력받은 문자열을 다 돈 후에도 false 가 되지 않고 stack이 비어있다면 true를 반환한다. 코드 #include #include ..