https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net https://github.com/SeongeunJi/BOJ_Algo/tree/main/%EB%B0%B1%EC%A4%80/Gold/6198.%E2%80%85%EC%98%A5%EC%83%81%E2%80%85%EC%A0%95%EC%9B%90%E2%80%85%EA%BE%B8%EB%AF%B8%EA%B8%B0 GitHub - SeongeunJi/BOJ_Algo: This is a auto push ..
https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net https://github.com/SeongeunJi/BOJ_Algo/blob/main/%EB%B0%B1%EC%A4%80/Gold/2493.%E2%80%85%ED%83%91/%ED%83%91.java GitHub - SeongeunJi/BOJ_Algo: This is a auto push repository for Baekjoon Online Judge created with [BaekjoonH..
이번 문제는 이전에 풀었던 오큰수와 비슷한 방식으로 접근하여 풀 수 있다. 다만 다른 점은 배열 요소의 값으로 오큰수를 구하는 게 아닌, 등장횟수로 구한다는 것이다. 또한 문제를 풀기 전에, 내가 구현하려는 코드를 간략히 생각이나 글로 정리하고, 시간 복잡도를 계산해보는 습관을 들이기 시작했다. 이번 문제는 각 요소를 모두 탐색하여 빈도수를 구하는 것은 매우 비효율적이고 O(N^2)의 시간 복잡도를 가지게 되는데, 그렇게 되면 이 문제를 절대 해결할 수 없다. 그래서 나는 물론 여러가지 방법이 있겠지만, 나는 이를 구현하기 위해서 해쉬맵을 사용하여, 등장횟수를 구하는 방법을 사용했다. *시간 복잡도에서 상수는 생략할 수 있다. StringTokenizer st = new StringTokenizer(br..
바로 문제를 간략하게 해석해보겠다. 수열 각 요소들의 오큰수를 구하려 한다. 오큰수란 해당 요소보다 오른쪽에 위치하면서도 가장 가까운 큰 수이다. 단, 자신보다 큰 수가 없는 경우 오큰수는 -1이 된다. 시간 복잡도는 최대 수열의 길이가 100만이므로, O(N)의 코드로 구현 가능함을 알 수 있다. 이번 문제의 핵심 포인트는 스택을 이용하여 수를 비교하는 거라고 생각했다. 예를 들어 {2, 2, 2, 1, 1, ,1, 7}과 같은 수열이 존재할 때, 마지막 요소를 제외한 모든 요소들의 오큰수는 7이다. 따라서 어떻게 구현할 것이냐면 1. 이번엔 수의 값을 비교해야 하기 때문에 수들을 스택이 아닌 배열에 넣어야 한다. 왜냐하면 스택에 값을 넣어버리는 순간 top만 확인할 수 있기 때문이다. 2. 그럼 스택..
이번 문제는 쇠막대기이다. 나는 뭔가 스택보다 큐 자료구조가 훨씬 쉽게 느껴졌고, 스택은 약간 까다롭게 느껴졌는데 점점 풀다보니 실력이 붙는 것 같다. 아무튼 이번 문제는 괄호 검사와 비슷한 로직으로 구현해 낼 수 있다. 문제를 풀어보기 앞서, 항상 시간 복잡도를 계산하고 구현하는 것이 좋다. 따라서 일단 시간 복잡도를 간단하게 체크해보자면 문자열의 최대 길이는 10만개. 시간 제한은 1초이므로, O(N)의 시간복잡도를 가지는 코드로 충분히 구현 가능할 수 있다는 것을 알아낼 수 있다. 왜냐면 앞전에도 말했듯이, 대충 컴퓨터는 1초당 1억 정도의 연산을 수행할 수 있기 때문이다. *디테일한 상황에 따라 이 값도 당연히 달라진다. 그럼 문제를 파악해보자. 나는 이 문제를 해석할 때 다음과 같이 정리해보았다..
이번 문제는 간단하므로, 주석으로 설명을 대체하겠다. import java.io.*; import java.util.Stack; import java.util.function.BiPredicate; public class S17413 { static Stack stack = new Stack(); static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BiPredicate p = (ch1, ch2) -> ch1 == ch2; String i..
이번 문제는 스택에 대한 구조를 알고 있다면, 정말 쉽게 해결할 수 있었다. 이 문제를 구현하기 전, 우리가 고려해야 할 사항이 있다. 그것은 0.3초 내에 600,000개의 문자열을 처리해야 한다는 것이다. 만약 이를 구현할 때, 문자열을 하나 하나 다 뒤집어 가면서 구현하면 시간 복잡도는 O(M^2)라고 봐야한다. 정확히는 O(MN)이겠지만, 가장 앞에 있는 문자를 삭제하거나 추가할 땐, O(M^2)라고 봐도 상관이 없다. 그렇게 된다면 3600억이 되는데, 1억이 1초라고 그냥 가정하게 된다면 너무 많은 시간이 걸리기에 이렇게 구현하면 안된다. 이를 구현하기 위해선, 적어도 반드시 O(M)의 시간 복잡도를 가지는 코드여야 한다. 그럼 어떻게 구현할 수 있을까? 바로 커서 기준 왼쪽 문자열과 오른쪽 ..
이번 문제를 해결하기 위해선 규칙을 잘 파악해야 한다. 문제 자체는 간단하다고 생각하지만, 나는 이런 문제를 처음 봐서 약 20분동안 뭔 말인가 하고 문제를 들여다 보았다. 문제 해석과 풀이를 하자면 이와 같다. 1. 스택에 오름차순으로 수를 넣는다. 1,2,3,4,5,6,7 -> Possible | | 4,6,7,1 -> Impossible 2. 입력값이 주어질 때, 현재 스택의 top이 같거나 크면 수열을 만들 수 있다. 3. 현재 스택의 top보다 입력값이 작다면 pop을 여러번 해야만 만들 수 있다. 따라서 이 경우는 스택을 만들 수 없다. 이 세 개만 알아도 이 문제를 구현해내는데 아무런 어려움이 없을거라 생각한다. 조금 더 자세하게 설명하자면, 입력된 수열이 4이고, 현재 아무 수도 스택에 넣..
이번 문제도 어렵지 않았지만, 문자열을 다루는데 공부가 된거 같았다. import java.io.*; import java.util.Stack; public class S4949 { static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Stack stack = null; loop1: while(true) { String input = br.readLine(); if(input.equals(".")) break; // .만을 입력받으면 br..
스택은 아시다시피 괄호 검사를 할 때 많이 쓰이는 자료구조이다. 추가로 우리 웹사이트의 뒤로 가기와 앞으로 가기 또한 스택 구조를 이용하여 구현한 것이라고 한다. import java.io.*; import java.util.Stack; public class S9012 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); Stack stack = new Stack(); int T = Integer.parseInt(br.readLine()); lo..
