Codility #1 정리
Iterations
✅ Iterations > BinaryGap
- https://app.codility.com/programmers/lessons/1-iterations/binary_gap/
- 문제 : 이진 수 변환 후 1로 둘러쌓인 0의 최대 카운트 값을 구하는 문제
- 해결 : 정수를 2진수 문자열로 변환 후, 배열 순회 1번
- 순회 : 1이 시작되는 경우 카운팅을 시작, 1이 종료되면 카운트 답 갱신
Arrays
✅ Arrays > CyclicRotation
- 문제 : 배열을 오른쪽을 k번 회전하는 문제
- 해결 : 나머지 연산자를 이용해서 중복된 반복을 제거
- ⚠️ 신텍스 오류
- push, pop 와 unshift, shift 을 이용하는데 unshift, shift을 헷갈렸다.
✅ Arrays > OddOccurrencesInArray
- 문제 : 배열에서 숫자 쌍이 아닌 숫자를 리턴하는 문제
- 해결 : XOR연산자를 이용한다.
- XOR 연산자는 비트 연산자 이다. 결합법칙과 교환법칙이 가능한 연산자이다.
- 결합 법칙 가능 : 연산을 뒤에서 부터 하나 앞에서 부터 하나 상관없다.
- 교환 법칙 가능 : 연산의 변수를 변경해도 상관없다.
- XOR 연산자의 특징은 같은 숫자는 상쇄되는 특성이 있다.
- 0 ^ 1 => 1만 살아남음
- 0 ^ 9 => 9만 살아남음
- 0 ^ 9 ^ 9 => 0 출력
- 0 ^ 9 ^ 9 ^ 8 => 8만 살아남음
- 0 ^ 9 ^ 8 => 1이 리턴되는데, 8, 9가 아직 쌍 기다리는 중.
- 0 ^ 9 ^ 8 ^ 9 => 쌍이 없는 8만 리턴된다.
- XOR 연산자는 비트 연산자 이다. 결합법칙과 교환법칙이 가능한 연산자이다.
참고 )
- 교환 법칙, 결합 법칙 적용 : 덧셈, 곱하기 ( 빼기, 나누기는 둘 다 안된다. )
- 교환 법칙만 성립하는 경우 : 산술평균 ( n개 전용 수식이 있음 )
- 결합 법칙만 성립하는 경우 : 행렬곱
Time Complexity
접근법 - 시간복잡도를 계산하고, O(N**2)에서 O(N)으로 줄이는 문제
- 1, 공식을 이용해서 순회를 줄이는 방법 : 배열의 합, 나눗셈 및 나머지 연산으로 정답 구하는 식
- 문제의 조건에 맞는 식을 도출하거나 수학적 지식의 수식을 사용하기
- 2, 중간 누계 데이터를 사용해서 순회를 줄이는 방법 : 메타성 정보르 순회를 줄이는 케이스, 아래 예제 확인
- ✨ '게으른 업데이트 (Lazy Update)'
- ✨ '접두사 합(Prefix Sums)'
- 3, 사전 정렬을 이용해서 순회를 줄이는 방법 : 정렬된 상태에서 시작하면 많은것을 해결 할 수 있다.
✅ Time Complexity > FrogJmp
- 문제 : 개구리가 최소한의 점프로 Y이상 거리를 넘는 점프수
- 해결 : 나이브하게 점프 횟수를 1부터 증가하면 순회를 계속 해야한다.
- 나눗셈 및 나머지 연산자를 이용하면 순회 제거 가능
✅ Time Complexity > PermMissingElem
- 문제 : 배열은 1부터 선형 증가하는데 빠진 숫자를 구하는 것
- 해결 : N*(N+1)/2는 수열의 합이다. 이 공식을 이용하면 순회 제거 후 답을 구할 수 있다.
✅ Time Complexity > TapeEquilibrium
- 문제 : 정수 배열을 2분할 후, 전후 배열의 합의 절대값 차이의 최솟값을 구하는 문제
- 해결 : 완전 탐색으로 접근하면 O(N**2) 복잡도가 나온다.
- 순회를 한번 제거할 수 있는데, 합을 구하기 위해 배열을 순회하는것이 O(N)이다.
- 위 과정은 배열의 합을 미리 구해놓으면 O(1)로 단축 가능.
- ⚠️ 로직 오류 : 초기 최대값은 배열의 합이 아니다, 마이너스 고려하면 MAX_SAFE_INTEGER 을 사용하자.
Counting Elements
✅ Counting Elements > FrogRiverOne
- 문제 : 나뭇잎은 K시간대 i위치에 하나씩 셋팅된다. 0~N까지의 모두 나뭇잎으로 커버되는 가장 빠른 시간은?
- 해결 : O(N**2)으로 (나뭇잎을 셋팅 순회) + (커버 여부 순회)로 완전탐색 접근
- 커버 여부 순회를 O(1)로 단축 할 수 있다. Set자료구조의 길이가 N이 되는지만 체크하면 순회 없이 O(1) 최적화
✅ Counting Elements > PermCheck
- 문제 : 배열이 순열이 되기 위해서 빠진 숫자를 구하는 문제
- ⚠️ 로직 오류 : 합공식 이용하면 바로 빠진값을 구할 수 있다.
- 반례 : 1,2,3의 합은 6 이다. 1, 1, 4로 합이 6인데도 순열이 아닐 수 있다.
- 로직 : 범위가 1~N 사이이고, 중복이 없다면 순열이다.
✅ Counting Elements > MaxCounters
- 문제 : N개의 카운터를 시뮬레이션 하는 문제, k번째 카운터 1증가 or 모두 카운터의 max값으로 동기화 연산 2가지 제공
- ✨ 특이점 : O(N**2)으로 (연산 N번 순회) + (max값 동기화)로 완전탐색 접근
- (max값 동기화) 과정을 O(1)로 줄일 수 있다.
- 게으른 업데이트 (Lazy Update) 개념 : max값으로 동기화를 즉시 할 필요는 없었다. 하지만 2개의 메타데이터가 필요.
- 항상 카운터의 최대값을 추적하는 변수, 카운터의 Lower Bound Max Value 변수
- 그리고 2가지 로직이 추가
- 1, k번째 카운터 1증가 할 때 카운터의 Lower Bound Max Value 변수를 체크해서 값을 올려준다.
- 2, 마지막 카운터 값 리턴할 때 카운터의 Lower Bound Max Value 변수보다는 크게 맞추어 준다.
✅ Counting Elements > MissingInteger
- 문제 : 주어진 수열에 나타나지 않은 가장 작은 양의 정수를 출력
- ⚠️ 로직 오류 : 배열 정렬 후 i, i+1의 값 사이에 1이상의 간격이 있는지 체크
- 위 로직이 잘 돌려면 예외처리가 몇가지 있다. 배열의 크기가 0, 1의 경우
- ⚠️ 로직 개선 : Set 자료구조로 i부터 탐색해도 충분히 시간내에 들어온다.
function solution(A) {
// 1. 중복 제거 -> 양수 필터링 -> 정렬
// (Set을 먼저 써서 정렬할 갯수를 줄이는 것이 성능상 조금 더 유리합니다)
const sortedA = [...new Set(A)].filter(x => x > 0).sort((a, b) => a - b);
// [체크 1] 양수가 아예 없는 경우 (예: [-1, -3])
if (sortedA.length === 0) return 1;
// [체크 2] 가장 작은 양수가 1이 아닌 경우 (예: [2], [2, 3]) -> 정답은 무조건 1
// 이 체크가 길이 체크보다 우선되어야 합니다.
if (sortedA[0] !== 1) return 1;
// [체크 3] 중간에 빈 숫자 찾기
for (let i = 0; i < sortedA.length - 1; i++) {
// 현재 숫자 + 1이 다음 숫자와 다르다면, 그 사이 값(현재+1)이 정답
if (sortedA[i] + 1 < sortedA[i+1]) {
return sortedA[i] + 1;
}
}
// [체크 4] 여기까지 왔다면 숫자가 연속된 것이므로 (예: [1, 2, 3]), 마지막 숫자 + 1 리턴
return sortedA[sortedA.length - 1] + 1;
}
Prefix Sums
✅ Prefix Sums > PassingCars
- 문제 : 1차선 양방향 도로에서 마주보고 오는 차량의 쌍을 계산하는 문제
- ✨ 로직 : 먼저 완전 탐색으로 생각. (왼쪽방향의 차량 순회)*(마주치는 차량 수 카운트)
- (마주치는 차량 수 카운트) 연산은 O(1)로 최적화 가능하다. 중간 누계 데이터를 추가하면된다.
- 배열의 오른쪽에서 부터 순회하여, 왼쪽 방향으로 오는 차량의 수를 누계한다. 오른쪽 방향의 차량이 있다면 ans에 중간 누계값을 더한다.
- 여기서의 중간 누계값 개념 = '접두사 합(Prefix Sums)'
⚠️ Prefix Sums > CountDiv
- 문제: A ~ B 사이 K로 나누어 떨어지는 숫자의 개수를 구해라.
- 처음 나의 로직 : A보다 같거나 큰 K로 나누어지는 숫자를 찾고, K씩 더해가면 나누어 떨어지는 숫자들의 수를 찾을 것 이다.
- 로직 (문제의 의도) :
function solution(A, B, K) {
// [틀린 부분 수정]
// 작성하신 코드: const start = A + (A % K);
// 문제점: A=10, K=3일 때, 10 + (10%3) = 11이 됩니다. 11은 3의 배수가 아닙니다.
// 10에서 다음 3의 배수(12)로 가려면 나머지가 1일 때 1을 더하는 게 아니라, (3-1)=2를 더해야 합니다.
// [고친 코드]
// A가 K로 나누어 떨어지면 A가 시작점이고, 그렇지 않으면 A에서 (K - 나머지)만큼 더해준 값이 첫 번째 배수입니다.
let start;
if (A % K === 0) {
start = A;
} else {
start = A + (K - (A % K));
}
// start 점이 B보다 크면 범위 내에 배수가 없다는 뜻입니다.
if (start > B) return 0;
return 1 + Math.floor( (B - start) / K );
}
/** Time Complexity: O(1), Space Complexity: O(1) */
function solution2(A, B, K) {
// (1) 0부터 B까지의 배수 개수
// (2) 0부터 A-1까지의 배수 개수
// 답 : (1) - (2)
// 설명:
// Math.floor(B / K)는 1부터 B까지의 K 배수 개수를 나타냅니다 0 포함 시 논리적 보정 필요).
// Math.floor((A - 1) / K)는 1부터 A-1까지의 K 배수 개수를 나타냅니다.
// A가 0인 경우 (A-1)은 -1이 되며, 자바스크립트에서 Math.floor(-1 / K)는 -1이 됩니다.
// 이는 0이 K로 나누어떨어진다는 사실(0 % K === 0)을 수식적으로 올바르게 보정해줍니다.
return Math.floor(B / K) - Math.floor((A - 1) / K);
}
// console.log(solution(6, 11, 2)); // 출력: 3 (6, 8, 10)
// 0,0,1 -> 1
// 0,1,1 -> 2
// 1,1,1 -> 1
// 0,0,2 -> 1
// 0,1,2 -> 1
// 1,1,2 -> 0
Sorting
✅ Sorting > MaxProductOfThree
- 문제 : 배열에서 숫자 3개를 골라 최대곱을 구하는 문제
- 로직 : 케이스를 분류해서 각 케이스 별 최대값을 결정적으로 구할 수 있음.
- 양수만 있는 경우, 음수만 있는 경우, 양과 음이 섞인 경우 max( top(양,양,양), top(양,음,음) )
- 로직 개선 : 위 케이스별로 모두 코드를 작성했는데, 아래 처럼 간소화 가능 ( 각 케이스가 커버된다. )
function solution(A) {
A.sort((a, b) => a - b);
const N = A.length;
// (1) top 3
// 1.1 양수만 있는 경우 커버, 음수만 있는 경우 커버
// 1.2 양,음수 같이 있는 경우 중 - 양양양 커버
const maxPossibility1 = A[N - 1] * A[N - 2] * A[N - 3];
// (2) bottom 2, top 1 => 양,음수 같이 있는 경우 중 - 음음양 커버
const maxPossibility2 = A[0] * A[1] * A[N - 1];
// 3. 두 값 중 더 큰 값을 반환합니다.
return Math.max(maxPossibility1, maxPossibility2);
}
✅ Sorting > Triangle
문제 : 삼각형 선분의 길이들이 배열로 주어진다. 이 중 삼격형을 만들 수 있는지 체크하는 문제
로직 : a,b,c 세변은 각각 나머지 변의 합보다 커야한다. 우선 정렬을 한다. 그리고 그리디 하게 a+b>c만 맞는지 순회 1번을 한다.
Stacks and Queues
✅ Stacks and Queues > Brackets
문제 : 올바른 괄호쌍인지 찾는 문제
로직 : 스택에서 괄호 쌍을 넣고 풀면된다. 전형적인 괄호쌍스택 문제. 괄호종류가 3가지
✅ Stacks and Queues > Fish
문제 : 물고기 크기, 물고기 위/아래 방향으로 n마리 물고기가 주어졌을때 살아남는 최종 물고기는?
⚠️ 로직 : 하류로 가는 물고기를 스택에 보관하고 있다가,
- 상류로 가는 물고기와 부딪칠때마다 스택을 비우거나(하류 가는 물고기가 먹힘)혹은 상류로 가는물고가기 잡아먹히면 된다.
- 답은 상류로 살아남은 물고기 수 + 하류 물고기 수
✅ Stacks and Queues > Nesting
- 문제 : 올바른 괄호쌍인지 찾는 문제
- 로직 : 스택에서 괄호 쌍을 넣고 풀면된다. 전형적인 괄호쌍스택 문제.
⚠️ Stacks and Queues > StoneWall
- 문제 : 직사각형의 돌을 최대한 적게 쌓는 문제이다.
- ⚠️ 로직 : 우선 발상이 어렵다. 스택 구조로 풀어가는게 최소임을 어떻게 아는가?