Level 2
숫자 짝꿍
두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다.
(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다)
X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다.
X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.
- 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
- X, Y는 0으로 시작하지 않습니다.
- X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function solution(X, Y) {
let arrX = X.split("");
let arrY = Y.split("");
let answer = [];
arrX.forEach((x) => {
for (let i = 0; i < arrY.length; i++) {
if (x == arrY[i]) {
answer.push(x);
arrY.splice(i, 1);
break;
}
}
});
answer.sort((a, b) => b - a);
while (answer[0] == 0 && answer.length > 1) {
answer.shift();
}
return answer.length ? answer.join("") : "-1";
}
- 길이 제한이 300만까지여서 시간복잡도 O(n^2)는 시간 초과가 됩니다.
다른 풀이
- 0 ~ 9 까지의 정수를 반복으로 돌립니다. 시간복잡도가 O(n)로 바뀌어 시간 초과하지 않습니다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function solution(X, Y) {
let answer = "";
X = X.split("");
Y = Y.split("");
// 0 ~ 9를 기준으로 반복문을 돌립니다.
for (let i = 9; i >= 0; i++) {
const cntX = X.filter((x) => +x === i).length;
const cntY = Y.filter((x) => +x === i).length;
answer += `${i}`.repeat(Math.min(cntX, cntY));
}
if (answer == "") return "-1";
if (+answer == 0) return "0";
return answer;
}
구명보트
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function solution(people, limit) {
var cnt = 0;
// 무게 오름차순 정렬
people.sort((a, b) => a - b);
// i, j 같이 정의
for (let i = 0, j = people.length - 1; i <= j; j--) {
// 가장 적은 수 + 큰 수 가 limit보다 크면 큰 사람 혼자 탑니다. j--
// 적으면 둘이 타고 갑니다. i++, j--
if (people[i] + people[j] <= limit) {
i++;
}
// 보낸 수를 기록
cnt++;
}
return cnt;
}
Tip
- Array.shift() 는 시간복잡도 O(n)으로 효율성 실패!
인덱스 값을 변경하는 것으로 효율성을 올립니다.
멀리 뛰기
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다.
멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요.
예를 들어 4가 입력된다면, 5를 return하면 됩니다.
1
2
3
4
5
6
7
8
9
function solution(n) {
let arr = [1, 2];
for (let i = 2; i < n; i++) {
arr[i] = (arr[i - 1] + arr[i - 2]) % 1234567;
}
return arr[n - 1];
}
Tip
1234567로 나눌땐 피보나치 수를 생각해보자.
H-index
n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.
어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.
1
2
3
4
5
6
7
8
9
10
11
12
13
function solution(citations) {
var answer = 0;
citations = citations.sort((a, b) => b - a);
let i = 0;
while (i + 1 <= citations[i]) {
i++;
}
return i;
}
Tip
내림차순 정렬하면 현재 인덱스값은 해당 값보다 큰 수의 개수입니다.
연속 부분 수열 합의 개수
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function solution(elements) {
let set = new Set([...elements, elements.reduce((acc, x) => acc + x, 0)]);
let n = elements.length;
for (let i = 2; i < n; i++) {
let len = i;
let sum = 0;
for (let h = 0; h < len; h++) {
sum += elements[h];
set.add(sum);
}
let k = 0;
while (k < n) {
sum -= elements[k++];
if (len >= n) len = 0;
sum += elements[len++];
set.add(sum);
}
}
return set.size;
}
Tip
슬라이드 윈도우 (Sliding Window) 와 Set 객체 활용 => 일정 범위의 합에서 한칸 씩 앞 요소 빼고 뒷 요소 더하기로 이동
다른 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function solution(elements) {
let set = new Set();
let concat = elements.concat(elements);
let len = elements.length;
for (let i = 0; i < len; i++) {
let sum = 0;
for (let j = 0; j < len; j++) {
sum += concat[i + j];
set.add(sum);
}
}
return set.size;
}
- 입력 수열을 이어붙이기 => for문 중첩으로 모든 경우 해결 가능
n^2 배열 자르기
정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.
n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, …, n에 대해서, 다음 과정을 반복합니다.
1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
1행, 2행, …, n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], …, arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다.
주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function solution(n, left, right) {
var answer = [];
let cnt = 0;
for (i = 1; i <= n; i++) {
let row = 1;
while (row <= i) {
if (cnt++ >= left && cnt <= right + 1) answer.push(i);
row++;
}
for (j = i + 1; j <= n; j++) {
if (cnt++ >= left && cnt <= right + 1) answer.push(j);
}
if (cnt == right) break;
}
return answer;
}
- 시간 초과 발행
다른 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
function solution(n, left, right) {
var answer = [];
for (let i = left; i <= right; i++) {
// 2 3 4 5
let row = Math.floor(i / n) + 1;
let col = (i % n) + 1;
col < row ? answer.push(row) : answer.push(col);
}
return answer;
}
행렬의 곱셈
2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function solution(arr1, arr2) {
var answer = Array.from(new Array(arr1.length), () =>
new Array(arr2[0].length).fill(0)
);
for (let i = 0; i < arr1.length; i++) {
for (let j = 0; j < arr2[0].length; j++) {
let sum = 0;
for (let h = 0; h < arr2.length; h++) {
sum += arr1[i][h] * arr2[h][j];
}
answer[i][j] = sum;
}
}
return answer;
}
다른 풀이
1
2
3
4
5
function solution(arr1, arr2) {
return arr1.map((row) =>
arr2[0].map((x, y) => row.reduce((a, b, c) => a + b * arr2[c][y], 0))
);
}
[1차] 뉴스 클러스터링
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
function solution(str1, str2) {
var answer = 0;
let arr1 = [];
let arr2 = [];
// 대소문자 차이를 무시하므로 소문자로 통일
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();
// 입력 문자열을 두 글자씩 끊어서 다중집합 만들기
for (let i = 0; i < str1.length - 1; i++) {
// 두 글자씩 자르기
let word = str1.substring(i, i + 2);
// 영문자가 아닌 값이 있는 경우 제외
if (word.search(new RegExp("[^a-z]", "g")) < 0) arr1.push(word);
}
for (let i = 0; i < str2.length - 1; i++) {
let word = str2.substring(i, i + 2);
if (word.search(new RegExp("[^a-z]", "g")) < 0) arr2.push(word);
}
let union = [...arr1];
let inter = [];
// 합집합, 교집합 만들기
for (let i = 0; i < arr2.length; i++) {
// 양쪽 다 값이 존재할 경우 (비교 기준 arr1)
if (arr1.includes(arr2[i])) {
let index = arr1.indexOf(arr2[i]);
// 비교 기준인 앞 문자열 arr1에서 해당 값을 제거 (중요 !)
arr1.splice(index, 1);
// 교집합에 해당 요소를 삽입
inter.push(arr2[i]);
} else {
union.push(arr2[i]);
}
}
// 합집합이 0이면 answer 값이 infinity이므로 따로 처리
if (union.length == 0) return 65536;
answer = Math.floor((inter.length / union.length) * 65536);
return answer;
}