1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 문제 히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다. 이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다. 주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이..
문제 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 풀이 [백준] 17298 오큰수 (Python) 문제 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 풀이 해당 문제의 입력이 백 developer-jason.tistory.com 위 문제와 사실상 동일한 문제, 하지만 이 문제에서는 수 자체를 비교하지 않고 수가 등장한 빈도와..
문제 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 풀이 해당 문제의 입력이 백만 개가 들어올 수 있으므로 O(N)만큼의 시간복잡도로 해결해야 하는 문제. 단순히 각 원소를 접근할 때 마다 오른쪽의 원소와 비교하며 오큰수를 발견 시 이를 출력하게 되면 O(N^2)로 문제 해결이 되지 않는다. 따라서 문제 해결을 위해 다른 방법을 찾아야 했다. 필자는 다음과 같이 생각했다. 1) 오른쪽에 작은 수가 들어오게 되면 해당 수는 쓸모가 없는 수가 되는 것일까 2) 오른쪽에 큰 수가 들어오게 되면 이전 수에도 영향을 미치지..
문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 풀이 첫 시도에서는 replace로 문제를 해결하려고 했다. 하지만 시간 초과가 발생하여 이를 해결하기 위해 stack으로 구현하였다. 코드 word = input() boom_word = input() stack = [] for i in word: stack.append(i) if len(stack) >= len(boom_word) and stack[-len(boom_word):] == list(boom_word): for _ in r..
