투투

문제 올바른 괄호열은 각각의 괄호의 짝이 맞는다. 이때 올바르지 않은 괄호열이 주어졌을 때 올바른 괄호열을 만들기위해 괄호를 추가하기 위해 최소 몇 개가 필요한지 구하라. 입력 첫 번째 줄에 올바르지 않은 괄호열 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개의 막대기를 보았을 때, 보이는 막대기의 개수를 출력한다. 접근 오른쪽에서 보기 때문에 가장 오른쪽에 있는 막대기는 무조건 볼 수 있다. 이후 가장 오른쪽에 있는 막대기의 높이를 기준으로 최댓값을 갱신하여 볼 수 있는 막대기를 구한다. 구현 - 입력받은 막대기의 높이를 뒤집어서 순차적으로..

문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다. 출력 각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다. 접근 나이트가 이동할 수..

문제 통로에 음식물들이 떨어져있고 근접한 음식물들이 모이면 큰 음식물 쓰레기가 된다. 음식물들이 떨어진 위치의 좌표가 주어질 때 가장 큰 음식물 쓰레기의 크기를 구하라. 어떤 음식물의 상하좌우에 음식물이 있을 때 근접한 음식물이라고 할 수 있다. 입력 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다. 좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 출력 첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라. 접근 뭉쳐있는 음식물끼리 같은 번호를 매기고 넘버링한 숫자의 개수를 카운트하여 가장 큰 수..