기록공간

문제 N개의 정수를 담는 배열 A가 주어진다. 0

문제 N개의 숫자를 원소로 가지고 배열 A가 주어진다. 여기서 (X, Y, Z) 인덱스 위치가 주어진다. (0 1일 경우 max(0, M[1 - 1]) + max(0, N[1 + 1]) Y -> 2일 경우 max(0, M[2 - 1]) + max(0, N[2 + 1]) ... Y -> 6일 경우 max(0, M[6 - 1]) + max(0, N[6 + 1]) 이 값들중 가장 큰 값이 정답이 된다. 코드는 다음과 같다. for문을 중첩하여 사용하지 않았기 때문에 시간 복잡도는 O(N)이 된다. class Info{ int sum_from_front = 0; int sum_from_back = 0; } class MaxDoubleSliceSum { public int solution(int[] A) { if..

문제 N개의 숫자가 들어있는 배열 A가 주어진다. 우선 여기서 Leader 숫자를 먼저 찾는다. Leader 숫자가 되기 위해서는 두 가지 조건 중 하나가 필요하다. 배열에서 가장 많이 중복되는 값 배열 길이의 절반 값보다 더 많이 나오는 값 이제 A를 둘로 쪼갠다. (0 = limitEquiLeft) && (RightCount >= limitEquiRight)) { ++result; } } return result; } }

문제 정수값을 담는 N개의 배열 A가 주어진다. A에 존재하는 정수값이 중복으로 배열 사이즈의 절반 이상 존재하는 경우 그 정수값은 Dominator가 된다. 이 Dominator를 찾고, 이 Dominator 값인 인덱스 위치 중 하나를 출력하는 문제이다. 해결 방법 중복되는 값으로 몇 개가 존재하는지 효과적으로 알 수 있도록 해시 테이블을 사용한다. 해시의 Key값에는 인덱스에 존재하는 값이 들어가고, Value값은 그 값이 존재하는 인덱스들을 담는 Vector 컨테이너가 들어간다. 배열 A를 순회돌며 해시 테이블에 Key값과 Value값을 넣어준다. 그 작업이 끝나면 해시 테이블에 들어간 값(Iterator)를 순회돌며 배열 A 사이즈의 절반이 넘어가는 Dominator가 존재하는지 찾는다. 만약 ..

문제 N개의 원소가 담긴 배열 H가 주어진다. H[0] ~ H[N-1] 까지의 원소에는 벽의 높이 값이 들어간다. 이때 H 높이들을 만족하는 벽을 쌓기 위해서 최소 몇 개의 블럭이 필요한지를 구하는 문제이다. 해결 방법 스택을 활용하여 풀 수 있는 문제였다. 스택을 사용하는 이유는 서로 같은 높이에 있는 있거나 가장 낮은 높이의 값들은 블럭을 하나로만 써야 최소한의 블럭을 만들 수 있기 때문이다. 이러한 값들을 스택에 기록해 블럭을 어떻게 만들지 결정한다. 다음과 같은 규칙으로 높이 값을 순회돌며 스택을 사용한다. (i번째 높이 값을 h라고 했을때) 1. 스택이 비어있다 => h를 push한다. 2. 스택 top의 값이 h보다 큰 경우 => pop 하고 배치 블럭 수를 1 증가시킨다. 3. 스택 top의..