본문 바로가기

코딩테스트22

[스택] 백준 17298 문제1. 크기가 N인 수열(A) 존재2. 각 원소 A[i]에 관련된 오큰수 NGE[i] 를 구한다3. 오큰수가 존재하지 않는 경우는 , "-1"로 저장( 1 (* 오큰수 : 오른쪽에 큰 수 중 가장 왼쪽에 있는 수 )ex) A [ 3,5,2,7 ] => NGE [ 5,7,7,-1 ]A [ 9,5,4,8 ] => NGE [ -1, 8,8,-1 ] 문제 분석N의 조건이 1,000,000까지 가능하므로 , 일반적인 반복문으로 풀이를 할 경우 시간초과가 난다스택을 이용하여, 풀이 진행스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수 는 오큰수가 된다오큰수 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력ex) A[top] ex) A [ 3,5,2 ,7] // result [ ] // s.. 2024. 10. 30.
[스택] 백준 1874번 문제1. 수열의 개수 N 제공 ( 1 2. n개의 줄에는, 1이상 n이하의 정수가 1개씩 제공 (같은 정수가 2번 나오지는 않음)3. 해당 제공된 n개의 줄의 수열을 오름차순으로 정리 (스택 이용)4. 오름차순 정렬이 불가능할경우, "No"반환입력출력8+4+3+6+8-7-5+2+1- + + - - - -  문제 분석1부터 자연수를 증가시키면서, 입력으로 주어진 숫자와 비교하며 자연수를 스택에 추가하거나 빼는 방식으로 풀이스택 연산 방법1. 현재 수열 값 >= 자연수- 현재 수열값이 큰 경우, 자연수를 증가시키며 스택에 삽입2. 현재 수열값 == 자연수- 스택에서 값을 빼오며, 입력버퍼에 쌓아두고, 삭제진행- 단, 같지 않을경우 스택을 이용해서 오름차순을 만들 수 없으므로 "No" 반환  수도코드probl.. 2024. 10. 29.
[슬라이딩 윈도우 + deque] 백준 11003번 문제1. 숫자 배열 크기 + 범위 크기가 주어짐2. 숫자 배열이 주어짐3. 숫자배열에서 범위만큼 움직이며, 그때마다 최소값을 저장문제 조건 : ( 1  문제분석범위 크기 이동만큼 최소값 탐색슬라이딩 윈도우 : 2개의 포인터를 잡고, 이동시키며 최소값 탐색범위크기 및 숫자개수 최대치가 5,000,000이므로 시간복잡도를 O(n) 초과하여 잡을 수가 없음 (시간 초과)기본 정렬 시간 복잡도 : O(nlogn)일반적인 정렬알고리즘으로 풀지 못하므로, 덱(deque)을 도입Deque (덱) - 앞쪽에서 추가/삭제 가능, 뒷쪽에서도 추가/삭제 가능[구조]    Add    ->                                               -> Remove                   Fr.. 2024. 10. 27.
[슬라이딩윈도우] 백준 12891번 문제문자열 {A, C, G ,T}인 문자열만 주어지는 상황1. 문자열 길이(S)를 입력 받고, 그 중에 부분 문자열(P)을 가지고 비밀번호를 만듬2. 부분 문자열중에서 비밀번호를 만들 때,A,C,G,T 각각의 만족하는 최소 조건이 존재3. 최소 조건을 만족하면 비밀번호를 만들 수 있음 (해당 개수 세기)4. 2초이내,  (1 ex) A C G T A C G G T A C C (주어진 문자열) (A (2개), C(0개), G(1개), T(1개) 이상 조건 충족)->해당 조건을 만족하는, 비밀번호 만들 수 있는 개수 구하기 문제분석1,000,000개 이므로, O(n)으로 시간복잡도를 가져야함슬라이딩 윈도우를 이용하여, 부분문자열을 표현조건에 맞는 비밀번호 생성 문자를 이용하여, 몇개를 만들 수 있는지 구현[.. 2024. 10. 24.

티스토리툴바