본문 바로가기

알고리즘/백준118

[백준/자바] 17298 오큰수 구하기 [백준/자바] 17298 오큰수 구하기 📌 문제 크기가 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, .. 2022. 11. 6.
[백준/자바] 1874 스택 수열 [백준/자바] 1874 스택 수열 📌 문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. ⚔ 입력 첫 줄에 .. 2022. 11. 5.
[백준/자바] 11003 최솟값 찾기 [백준/자바] 11003 최솟값 찾기 📌 문제 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. ⚔ 입력 첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000) 둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109) 📣 출력 첫째 줄에 Di 를 공백으로 구분하여 순서대로 출력한다. 💎 문제분석하기 먼저 문제에 주어진 범위에 대한 해석을 해보자면 L은 슬라이딩 윈도우의 크기임을 알 수 있다. 따라서 주어지는 크기 만큼의 슬라이딩을 움직이며 최소 값을 구하는 문제이다. i가 커지면서 순차대로 최소값을 .. 2022. 11. 5.
[백준/자바] 12891 DNA 비밀번호 [백준/자바] 12891 DNA 비밀번호 📌 문제 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다. 하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다. 그래서 민호는 부분문자열에서 등장하는 문자의 개수가 특정 개수.. 2022. 11. 5.
[백준/자바] 1253 좋은 수 구하기 [백준/자바] 1253 좋은 수 구하기 📌 문제 N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. ⚔ 입력 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) 📣 출력 좋은 수의 개수를 첫 번째 줄에 출력한다. 💎 문제분석하기 문제의 예시로 주어진10까지 연속된 자연수를 생각해보면 1,2를 제외한 나머지 수임을 알 수 있다. 이전의 포인터 문제 와 동일한 로직으로 접근할 수 있다. 따라서 먼저 받은 N을 배열에 .. 2022. 11. 4.

티스토리툴바