Little cabin in the woods

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/2504📌 문제 탐색하기목표주어진 괄호열을 읽고 그 괄호 값을 규칙대로 계산하여 출력하기해야 할 것1. 계산 규칙 이해하고, 구현하기2. 입력이 올바르지 못한 괄호열이면 반드시 0 출력하기입력[첫줄] 괄호열 (1 ≤ 괄호열의 길이 ≤ 30)아이디어1. 계산 규칙 이해하고 구현하기- '()' 의 값 = 2- '[]' 의 값 = 3- '(x)'의 값 = 2*x의 값- '[x]'의 값 = 3*x의 값- xy = x의 값+y의 값 괄호 문제는 스택을 이용해서 풀 수 있다는 것을 알고 있으니, 이 문제도 스택을 활용해서 해결할 수 있는지 생각해보자. 스택에 쌓을 때,  고려해야 할 점은 크게 세 가지이다.1. 짝이 맞는 지 확..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/10799📌 문제 탐색하기목표잘려진 쇠막대기 조각의 총 개수 구하기해야 할 것1. 쇠막대기와 레이저 구분하기2. 각 쇠막대기가 몇 조각으로 잘리는 지 어떻게 구할까?입력[첫줄] 괄호 문자 ( 최대 길이 10^6 ) 아이디어1. 쇠막대기와 레이저 구분하기 '()'처럼 괄호가 인접하게 닫히면➡️ 레이저( 가 바로 인접하게 닫히지 않으면 ➡️ 쇠막대기, 만나는 첫번 째 ')'가 이 쇠막대기의 끝  2. 각 쇠막대기가 몇 조각으로 잘리는 지 어떻게 구할까? ➡️ 스택을 통해 괄호의 짝을 맞출 수 있다는 걸 이전 문제들을 풀며 알게 되었다. 이걸 응용할 수 없을까? 1) 일단, ( 과 ) 이 만났을 때 얘네가 레이저인지 쇠막대..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/9012📌 문제 탐색하기목표VPS인지 아닌지 판별하기해야 할 것1. VPS를 어떻게 판별할까?- VPS :  괄호가 순서에 맞게 잘 짝지어져 있는 조합입력[첫줄] 테스트 케이스의 수 T[둘째줄 ~ ] 괄호 문자열 ( 2 ≤ 괄호 문자열의 길이 ≤50)아이디어1. VPS를 어떻게 판별할까? 1단계. 괄호 문자열을 한 글자씩 탐색하며 스택의 가장 위에 있는 원소와 현재 문자를 비교한다.2단계. 만약 스택의 가장 위에 있는 원소와 현재 문자가 짝이 맞다면, 가장 위에 있는 원소를 스택에서 제거한다.3단계. 스택이 비어있거나, 스택의 가장 위에 있는 원소와 현재 문자가 짝이 맞지 않다면, 현재 문자를 스택에 삽입한다.4단계...

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/3986📌 문제 탐색하기목표입력된 단어 중 좋은 단어의 개수 세기해야 할 것1. 좋은 단어를 어떻게 판별할까?➡️선끼리 교차하지 않으면서 각 글자를 정확히 한개의 다른 위치에 있는 같은 글자와 짝 지을 수 있는 단어(예시 : ABAB는 좋은 단어x, AABB는 좋은단어, ABBA는 좋은 단어 )입력[첫줄] 단어의 수 N ( 1 ≤ N ≤ 100)[둘째줄 ~ ] 단어 ( 2 ≤ 단어의 길이 ≤10^5)아이디어1. 좋은 단어를 어떻게 판별할까? 이전에 푼 괄호 문제와 거의 유사한 유형의 문제이다.2024.12.15 - [STUDY/알고리즘&코딩테스트] - [백준] 4949. 균형잡힌 세상 (JAVA) 이 문제 역시 스택의..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/4949📌 문제 탐색하기목표문자열이 주어졌을 때, 균형잡힌 문자열인지 판단하기해야 할 것1. 균형잡힌 문자열인지 어떻게 판단할까?[규칙]- "("은 ")"을 만나야 한다. - "["은 "]"을 만나야 한다.-  괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.입력[첫줄~] 문자열. (100글자 이하)*종료조건 : "." 아이디어1. 균형잡힌 문자열인지 어떻게 판단할까? 문자열을 왼쪽부터 차례대로 탐색하다가 "(" 또는 "[" 가 나오면 스택에 쌓는다.")" 또는 "]"가 나오면 스택의 가장 윗 원소와 짝을 이룰 수 있는지 비교한다.짝을 이룰 수 있다면 스택에서 제거하고, 만약 ")"또는 "]"이 나왔는데 ..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/6549 📌 문제 탐색하기목표히스토그램에서 가장 넓이가 큰 직사각형 구하기해야 할 것1. 가장 넓이가 큰 직사각형을 어떻게 판단할까?2. n의 최대값이 10^5, 높이의 최대값이 10^9 인 것 고려하기입력[각 줄] 직사각형의 개수 n ( 1 ≤ n≤ 100,000 ) , 직사각형의 높이 ( 0 ≤ 높이 ≤ 1,000,000,000 )아이디어1. 가장 넓이가 큰 직사각형을 어떻게 판단할까?직사각형의 가로의 길이는 1로 고정되어 있고, 높이만 달라진다.가장 넓은 면적은 높이가 최대인 직사각형이 가장 멀리까지 확장될 때 발생한다.모든 직사각형을 하나씩 기준으로 삼고 최대 면적을 계산해볼 수 있겠지만, 그럴 경우 시간 복잡..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/3015📌 문제 탐색하기목표일렬로 서 있는 사람들 중 서로 볼 수 있는 쌍의 수 구하기해야 할 것1. 서로 볼 수 있는 쌍을 어떻게 셀까?입력[첫줄] 사람들의  N ( 1 ≤ N ≤ 5*10^5 )[둘째줄 ~ ] 각 사람들의 키 ( 1 ≤ 키  2^31 )아이디어1. 서로 볼 수 있는 쌍을 어떻게 셀까?(예시) 2 4 1 2 2 5 1➡️ 2와 서로 볼 수 있는 수 : 4➡️ 4와 서로 볼 수 있는 수 : 1,2,2,5➡️ 1과 서로 볼 수 있는 수 : 2➡️ 2와 서로 볼 수 있는 수 : 2, 5➡️ 2와 서로 볼 수 있는 수 : 5➡️ 5와 서로 볼 수 있는 수 : 1=> 총 10쌍 이므로 10 출력 위의 방식처럼..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/17298 📌 문제 탐색하기목표A의 오른쪽에 있는 수 중 가장 첫 번째로 등장하는(가장 왼쪽에 있는) A보다 큰 수 구하기해야 할 것1. 오큰수를 어떻게 판별할까?2. 수열의 크기 N의 최대값이 10^6 인 것 고려하기입력[첫줄] 수열의 크기 N ( 1 ≤ N ≤ 10^6 )[둘째줄 ~ ] 수열 ( 1 ≤ 수열의 각 원소  ≤ 10^6 )아이디어1. 오큰수를 어떻게 판별할까?➡️어떤 수의 왼쪽에 있는 수는 고려할 필요 없고, 오른쪽만 고려하면 된다는 점에서 스택 자료구조 떠올리기 2. 수열의 크기 N의 최대값이 10^6 인 것 고려하기 ➡️모든 수를 단순히 하나씩 탐색한다면 O(N^2)의 시간복잡도를 가지게 되므로 시..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/6198📌 문제 탐색하기목표각 관리인들이 볼 수 있는 옥상 수의 합 출력하기해야 할 것1. 관리인들이 볼 수 있는 옥상을 어떻게 판별할까?2. 빌딩의 개수 최대값이 80,000인 것 고려하기입력[첫줄] 빌딩의 개수 N ( 1 ≤ N ≤ 80,000 )[둘째줄 ~ ] 빌딩의 높이 h( 1 ≤ h ≤ 1,000,000,000 ) ⚠️int 형은 2*10^9까지 저장할 수 있다. 만약 다뤄야 할 자료형의 범위가 int를 넘어간다면 long 타입 사용을 고려해야 한다.아이디어1. 관리인들이 볼 수 있는 빌딩을 어떻게 판별할까?➡️ 모든 빌딩들에서 오른쪽으로만 볼 수 있기 때문에 현재 빌딩의 오른쪽에 있는 빌딩들만 고려하면 된..

이번에 풀어 볼 문제는 이다.https://www.acmicpc.net/problem/2493📌 문제 탐색하기목표각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지 출력하기해야 할 것1. 레이저 신호를 수신하는 탑을 어떻게 알아낼까?2. 탑의 수의 최대값이 5*(10^5) 인 것 고려하기입력[첫줄] 주어질 탑의 개수 N (1 ≤ N ≤ 500,000)[둘째줄 ~ ] 각 탑들의 높이 ( 1 ≤ 탑의 높이 ≤ 100,000,000 )아이디어1. 레이저 신호를 수신하는 탑을 어떻게 알아낼까?➡️ 현재 탑의 왼쪽에 위치한 탑 중 현재 탑과 높이가 같거나 큰 첫 번째 탑이 레이저를 맞는다. 2. 탑의 수의 최대값이 5*(10^5) 인 것 고려하기➡️이 문제를 단순히 왼쪽에서 오른쪽으로 모든 탑의 높이를 ..