투투

문제 여는 괄호 ‘(’와 닫는 괄호 ‘)’로 구성된 문자열에서 아래의 조건을 만족하는 문자열을 올바른 괄호 문자열이라고 부른다. () 는 올바른 괄호 문자열이다 어떤 문자열 x가 올바른 괄호 문자열이라면, (x)도 올바른 괄호 문자열이다. 어떤 문자열 x와 y가 올바른 괄호 문자열이라면, xy도 올바른 괄호 문자열이다. 현욱은 친구로부터 생일 선물로 굉장히 긴 괄호 문자열을 받았다(도대체 왜 이런 걸 선물하는걸까?). 하지만 현욱은 올바른 괄호 문자열이 아니면 굉장히 싫어하기 때문에, 받은 괄호 문자열에서 연속한 일부분을 잘라서 올바른 괄호 문자열을 만들려고 한다. 그리고 이왕이면 긴 문자열이 좋으니 현욱은 부분 구간을 최대한 길게 잘라내려고 한다. 현욱을 도와 주어진 괄호 문자열에서 위의 조건을 만족하..

문제 올바른 괄호열은 각각의 괄호의 짝이 맞는다. 이때 올바르지 않은 괄호열이 주어졌을 때 올바른 괄호열을 만들기위해 괄호를 추가하기 위해 최소 몇 개가 필요한지 구하라. 입력 첫 번째 줄에 올바르지 않은 괄호열 S가 주어집니다. S의 길이는 1 이상 50 이하입니다. 출력 첫 번째 줄에 S를 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 출력합니다. 불가능한 경우는 주어지지 않습니다. 접근 스택에 이전의 괄호에 대해 기록한다. 이를 활용해서 올바르게 짝지어진 괄호들은 스택에서 pop하면 마지막엔 올바르지 않은 괄호만 스택에 남게된다. 구현 - 입력받은 문자열을 탐색한다. - 여는 괄호가 나왔을 때는 스택에 push한다. - 닫는 괄호가 나왔을 때 스택의 top이 여는 괄호라면 ..

문제 시험기간에 간식을 번호 순서대로 나눠주려고한다. 간식을 받기위해 사람들이 번호에 상관없이 무작위인 일렬로 서있고 차례대로 간식을 받으려고 한다. 이때 자신의 차례가 아닐 때는 한 명이 들어갈 수 있는 공간으로 빠지게된다. 이렇게 마지막 번호까지 모두 간식을 순서대로 받을 수 있는지 구해보자. 입력 입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다. 다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다. 출력 간식을 받을 수 있으면 "Nice"(따옴표는 제외)를 출력하고 그렇지 않다면 "Sad"(따옴표는 제외)를 출력한다. 접근 스택과 큐를 활용하였다. 기존에 줄이 서있는 사람들을 큐에..

문제 사람들이 클럽에 입장하기 위해 일렬로 줄 서 있다. 클럽에 입장한 남녀의 차이를 최대 X만큼 둘 수 있다. 기본적으로 줄의 순서대로 사람들을 입장시키지만 남녀의 차이가 X를 넘어가려 한다면 첫 번째 사람대신 두 번째 사람을 먼저 들여보낼 수 있다. 이때 최대 몇 명이 클럽에 입장할 수 있을지 구하라. 입력 첫째 줄에 정인이가 기억할 수 있는 가장 큰 차이 X

문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다. Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다. 예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1..

문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,..

문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다. i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다. 그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다. 예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다. 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다. 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다. 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다. 5번 관리..

문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다. 출력 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다. 접근 순서대로 탐색을 진행하여 특정한 조건에 따라 선택한 숫자는 스택에 push한다. 이후 스택의 top과 현재 숫자를 비교하는데 앞으로 선택해야할 개수보다 남아있는 수가 작을 때까지 크기를 비교한다. 선택해야할 개수보다 남아있는 수가 크다면 계속해서 스택의 top과 비교하여 현재 값이 크다면 교체를 해준다. 구현 - 문자열의 형태로 숫자를 입력받아 num..

문제 N개의 막대기를 왼쪽부터 일렬로 세운 후에 오른쪽에서 바라보았을 때 몇 개의 막대기를 볼 수 있는지 구해보자. 일렬로 세워진 막대기를 오른쪽에서 보면 보이는 막대기가 있고 보이지 않는 막대기가 있다. 입력 첫 번째 줄에는 막대기의 개수를 나타내는 정수 N (2 ≤ N ≤ 100,000)이 주어지고 이어지는 N줄 각각에는 막대기의 높이를 나타내는 정수 h(1 ≤ h ≤ 100,000)가 주어진다. 출력 오른쪽에서 N개의 막대기를 보았을 때, 보이는 막대기의 개수를 출력한다. 접근 오른쪽에서 보기 때문에 가장 오른쪽에 있는 막대기는 무조건 볼 수 있다. 이후 가장 오른쪽에 있는 막대기의 높이를 기준으로 최댓값을 갱신하여 볼 수 있는 막대기를 구한다. 구현 - 입력받은 막대기의 높이를 뒤집어서 순차적으로..

문제 히스토그램이란 보통 분포의 정도를 알기 위해 사각형의 서열을 기준선에 맞춰 늘어놓은 다각형을 말한다. 만약 임의의 수열이 2, 1, 4, 5, 1, 3, 3일 경우 사각형의 너비를 1로 맞추어 히스토그램으로 만들면 다음과 같다. 우리가 하고자 하는 것은 임의의 히스토그램이 주어졌을 때 히스토그램 내에서 사각형으로 이루어진 가장 큰 면적의 크기를 알고자 한다. 왼쪽 의 히스토그램에서 가장 큰 사각형의 영역은 오른쪽에 밑줄이 쳐진 영역과 같다 입력 입력 첫 번째는 히스토그램을 이루는 사각형의 개수 n(n≤100,000)이 입력되고 그 뒤로 히스토그램을 이루는 사각형의 높이가 순서대로 n개 입력이 된다. 사각형의 높이 k는 0 ≤ k ≤ 1,000,000,000 이다. 사각형의 너비는 모두 1이다. 출력..