스택으로 쌓아놓은 수열에서 조건을 만족하는 값들이 언제부터 다 나오는가?

17162번: 가희의 수열놀이 (Small) 여러개의 쿼리가 주어지는데,  1. 스택의 맨 뒤에 숫자를 추가 2. 스택이 비어있지 않으면 맨 뒤의 원소를 제거 3. 맨 뒤에서부터 최소 몇개의 수를 선택해야, 이들을 mod로 나누었을때 0,1,2,..,mod-1이 최소 1개 이상 나타나는가? 예를 들어 [2,3]인 경우 4로 나누면 나머지는 [2,3]인데, 여기서 0,1이 없으므로 -1 [2,3,1,4]인 경우 4로 나누면 나머지는 [2,3,1,0]인데 여기서 0,1,2,3이 모두 나왔으므로 4 -----------------------------------------------------------------------------------------------------------------------..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2025. 2. 27.
• textsms

O(N)으로 순서쌍 찾기1 - 기울기가 K인 직선의 개수

28137번: 뭐라고? 안들려 N개의 좌표가 주어질때, A,B를 두개의 좌표에 배치하여 이들을 이은 직선의 기울기가 K인 경우의 수를 찾는다 -------------------------------------------------------------------------------------------------------------------------------------------------------------- 2개의 점을 선택하는 순서쌍을 찾는거니까 단순하게 이중포문을 생각할 수 있지만 N  O(N)에는 찾아야한다는 소리인데... O(N)에 순서쌍을 찾는 문제들은 보통 해시맵(dict)을 쓰는 경우가 많다 두 점을 이은 직선의 기울기가 k라는 뜻은? 두 점의 좌표 (x1,y1), (x2,y2..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2025. 2. 19.
• textsms

가장 긴 연속하는 올바른 괄호 부분 문자열의 길이 구하는 알고리즘

15926번: 현욱은 괄호왕이야!! 괄호로만 이루어진 문자열이 주어질때 연속하는 부분 문자열 중 가장 긴 올바른 괄호 문자열의 길이를 구하는 문제 ------------------------------------------------------------------------------------------------------------------------------------------------------- 올바른 괄호 문자열을 구하는 알고리즘은 스택을 이용해서  스택이 비어있는데 (이 들어오면 넣고 스택이 비어있지 않을때, (이 들어오는 경우, 스택의 마지막 문자가 (인 경우에는 (이 들어올 수 있고 )이 들어오는 경우, 스택의 마지막 문자가 (인 경우에는 제거하고 마지막에 스택이 비면 올바른 ..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2025. 2. 17.
• textsms

코딩테스트 복기 - 배열에서 특정 수보다 작은 수 중 가장 가까운 수를 찾는 방법(find nearest element than smaller one on the left side)

1. 문제 배열이 주어질때, 특정한 수보다 작으면서 가장 가까운 수를 찾고자 한다. 예를 들어 [3,1,2,10,5,6,4]가 주어질때, 10보다 작으면서 가까운 수는 바로 옆에 2와 5가 있다 이 경우 인덱스가 더 작은 2를 출력하고 싶고 1의 경우는 만족하는 원소가 없으므로 -1을 출력한다. 2. 풀이 - 왼쪽에서 더 작은 원소의 위치를 찾기 생각보다 어렵던데..? 그냥 많이 어려운데 적어도 생각나는건 $O(N^{2})$ 브루트 포스뿐.. 하지만 n이 10만이 넘어가는데 브루트 포스가 통과할리는 없을 것 같고 스택을 이용해서 O(N)에 효율적으로 풀 수 있다고 한다 알고리즘을 보면 의외로 간단하네.. 생각하기가 어렵지 일단 A의 i번째 원소에 대해 왼쪽에서 작으면서 가장 가까운 원소를 찾는다 그래서 ..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2023. 5. 22.
• textsms

[Java]자바로 구현하는 절댓값 우선순위 큐

1. 문제 배열에 다음과 같은 연산을 할 수 있습니다. 배열에 정수 x (x ≠ 0) 를 넣습니다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거합니다. ( 절댓값이 가장 작은 값이 여러개일 때는, 그 중 가장 작은 수를 출력하고, 그 값을 배열에서 제거합니다. ) 비어있는 배열에서 시작하여 입력된 연산을 실행하는 프로그램을 작성해보세요. 2. 풀이 자바하면 클래스 어렵게 생각하지 말고 필요하다면 클래스를 구현해서 사용하라 절댓값을 만드는 클래스를 구현해야하는데, 문제는 절댓값을 기준으로 오름차순 정렬을 할 수 있어야하고 중요한건 절댓값만 저장하는게 아니라 원본도 저장해야한다. 그래야 우선순위 큐에서 출력할때 원본값을 출력할 수 있으니까 import java.util.Scanner;..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2023. 3. 22.
• textsms

[Java]우선순위 큐 응용 - MN개의 조합에서 조건을 만족하는 k번째 수를 찾는 빠르게 찾는 방법 1편

1. 문제 n개의 숫자로 이루어진 수열과 m개의 숫자로 이루어진 수열이 주어졌을 때, 각 수열에서 정확히 원소를 하나씩만 뽑아 나올 수 있는 모든 쌍들을 모두 구하고, 그 값들을 오름차순이 되도록 나열했을 때의 k번째 쌍의 두 수의 합을 구하는 프로그램을 작성해보세요. n,m은 1이상 10만 이하의 자연수 k는 1이상 min(nm, 10만)이하 2. 풀이 가장 쉽게 생각할 수 있는 방법은 mn개의 모든 조합을 만든 다음에 우선순위 큐에 모두 집어 넣고, k번째 빠지는 수를 출력하면 된다 근데 뭐 당연히 시간초과 + 메모리 초과임 m과 n이 10만인데 시간복잡도가 얼마냐 이거 O(M + N + MNlogMN + KlogMN)인가..? 아무튼 O(MN)으로 생각하는 순간 10만*10만 = 100억으로 오바다..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2023. 3. 21.
• textsms