본문 바로가기

Baekjoon/[1] 자료구조22

[백준] 17299번 오등큰수 JAVA (자바) 풀이 문제 17299번 : 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구해라 : Ai가 수열 A에서 등장한 횟수를 F : Ai의 오등큰수는 오른쪽에 있으면서 F가 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다 : 그러한 수가 없는 경우에 오등큰수는 -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, ...,.. 2023. 7. 1.
[백준] 17298번 오큰수 JAVA (자바) 풀이 문제 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 : 둘째 줄에 수열 A의 원소 A1, A2, ..., AN [출력] : 총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공.. 2023. 6. 30.
[백준] 10799번 쇠막대기 JAVA (자바) 풀이 문제 10799번 : 여러 개의 쇠막대기를 레이저로 절단한다 : 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다 ( 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓기 ) : 각 쇠막대기를 자르는 레이저는 적어도 하나 존재 : 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다 : 굵은 실선 = 쇠막대기 점 = 레이저의 위치 점선 화살표 = 레이저의 발사 레이저 = ‘( ) ’ 쇠막대기의 왼쪽 끝 = ‘ ( ’ 쇠막대기의 오른쪽 끝 = ‘) ’ [입력] : 한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다 [출력] : 잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력 [문제 이해] : 막대기 총 개수를 size 라고 하자 : 막대기면 +1.. 2023. 6. 28.
[백준] 17413번 단어 뒤집기2 JAVA (자바) 풀이 문제 17413번 : 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. : 문자열 S 규칙 1) 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로 이루어짐 2) 문자열의 시작과 끝은 공백이 아니다. 3) ''가 문자열에 있는 경우 번갈아가면서 등장하며, '' 사이의 문자열은 길이가 3 이상 5) '' 사이에는 알파벳 소문자와 공백만 있다 6) 태그는 단어가 아니라 뒤집지 않고 태그와 다른 단어 사이에는 공백이 없다. [입력] : 첫째 줄에 주어지는 문자열 S [출력] : 첫째 줄에 문자열 S의 단어를 뒤집어서 출력 [스택 연산] init() 스택을 초기화 create() 스택을 생성 is_empty(s) 스택이 비어있는지 검사 is_full(s) .. 2023. 6. 28.
[백준] 10866번 덱 JAVA (자바) 풀이 문제 10866번 : 아래와 같은 [명령] 덱으로 구현해보기 [명령] push_front X 정수 X를 덱 앞에 넣는 연산 push_back X 정수 X를 덱 뒤에 넣는 연산 pop_front 덱에서 가장 앞에 있는 정수를 빼고 그 수를 출력, 큐에 정수가 없는 경우에 -1을 출력 pop_back 덱에서 가장 뒤에 있는 정수를 빼고 그 수를 출력, 큐에 정수가 없는 경우에 -1을 출력 size 덱에 들어있는 정수의 개수 출력 empty 덱이 비어있으면 1, 아니면 0 출력 front 덱의 가장 앞에 있는 정수를 출력. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력 back 덱의 가장 뒤에 있는 정수를 출력. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력 [입력] : 첫째 줄에 주어지는 명령.. 2023. 6. 27.
[백준] 1158번 요세푸스 문제 JAVA (자바) 풀이 문제 1158번 : 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고 이제 순서대로 K번째 사람을 제거한다. : 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. : 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. : 예를 들어 (7, 3)-요세푸스 순열은 이다. [입력] : 첫째 줄에 N K 입력 [출력] : 예제와 같이 요세푸스 순열을 출력한다. [큐 연산] init() 큐 초기화 create() 큐 생성 isEmpty() 큐 비어있는지 검사 isFull() 큐 가득 찼는지 검사 enqueue(e) 큐 맨 뒤에 e 추가 dequeue() 큐 맨 앞의 값 삭제 peek() 큐 맨 앞의 값 출력 (큐가 비어있는 경우 null 반환) element() 큐 맨 앞의 값 출력.. 2023. 6. 27.
[백준] 10845번 큐 JAVA (자바) 풀이 문제 10828번 : 아래와 같은 [명령] 큐로 구현해보기 [명령] push X 정수 X를 큐 넣는 연산 pop 큐에서 가장 앞에 있는 정수를 빼고 그 수를 출력, 큐에 정수가 없는 경우에 -1을 출력 size 큐에 들어있는 정수의 개수 출력 empty 큐가 비어있으면 1, 아니면 0 출력 front 큐의 가장 에 있는 정수를 출력. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력 back 큐의 가장 뒤에 있는 정수를 출력. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력 [입력] : 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000) : 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다 [출력] : 명령 출력할 때마다 한 줄에 하나씩 출력 [큐] : 큐는 들어가는 문 하나 나가는.. 2023. 6. 22.
[백준] 1406번 에디터 JAVA (자바) 풀이 문제 1406번 명령어 L 커서를 왼쪽으로 한 칸 옮김 (커서가 문장 맨 앞이면 무시) D 커서를 오른쪽으로 한 칸 옮김 (커서가 문장 맨 뒤이면 무시) B 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장 맨 앞이면 무시) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만 실제로 커서의 오른쪽에 있던 문자는 그대로 P$ $라는 문자를 커서 왼쪽에 추가함 : 위와 같은 명령어를 사용하여 문자열 수정하기 (처음에는 커서가 맨 뒤에 있다) [입력] : 첫째 줄에는 문자열이 주어진다 : 두번째 줄에는 명령어 개수 M이다 : 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다 [출력] : 첫째 줄에 모든 명령어를 수행하고 문자열 출력하기 [문제이해] : 커서는 좌우로 자유롭게 이동할 수 있다.. 2023. 6. 20.
[백준] 1874번 스택 수열 JAVA (자바) 풀이 문제 1874번 : 1부터 n까지의 수를 스택에 넣고 뽑아 하나의 수열을 만들 수 있다. (스택에 push 순서는 반드시 오름차순) 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지 보고 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지 작성하라 [입력] : 첫 줄에 n : 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다 : 물론 같은 정수가 두 번 나오는 일은 없다 [출력] : 한 줄에 한 개씩 출력 : push연산은 +로, pop 연산은 -로 표현 : 불가능한 경우 NO를 출력 [문제 이해] 입력받은 숫자까지 순서대로 수열을 만들어 push (이때 +출력) 그리고 해당 수 pop (이때 - 출력) 다음입력이 수열 안에 있으면.. 2023. 6. 20.
[백준] 9012번 괄호 JAVA (자바) 풀이 문제 9012번 : 괄호 문자열은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열 : 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열 = VPS [한 쌍의 괄호로 된 “( )” 문자열 = VPS] “(())()” = VPS “(()(” ≠ VPS : VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내기 [입력] : 첫 번째 줄에는 입력 데이터의 수 T 그 다음 줄은 괄호 문자열이 한 줄 (괄호 문자열의 길이는 2 이상 50 이하) [출력] : VPS이면 YES, 아니면 NO (한 줄에 하나씩 차례대로 출력) [스택 연산] init() 스택을 초기화 create() 스택을 생성 is_empty(s) 스택이 비어있는지 검사 is_full(s) 스택이 가득 찼는지 .. 2023. 6. 20.

티스토리툴바