[JavaScript] 배열 정복하기
선형 자료구조
1) 배열
2) 연결 리스트
3) 스택
4) 큐
5) 해시테이블
6) 데시
비선형 자료구조
1) 그래프
2) 힙
3) 트리
4) 트라이
배열
여러 개체 값을 순차적으로 나열한 선형 자료 구조
배열 크기 및 배열 확인
Array.length : 배열 요소의 개수 확인
Array.isArray() : 배열 타입 확인
배열 추가 삭제
Array.push() : 배열 추가 - LIFO Back
Array.pop() : 배열 삭제 - LIFO Back
Array.shift() : 배열 추가 - LIDO Front
Array.unshift() : 배열 추가 - LIFO Front
Array.splice() : 배열 요소 삭제 및 변경
Array.slice()
배열 요소 삭제
delete array[index] : 문제점은 삭제해도 배열 사이즈가 그대
배열 탐색
Array.indexOf(item from) : 앞부터 index탐색
Array.lastindexOf(item, from) : 뒤부터 index 탐색
Array.includes(item, from) : 값포함 여부
배열의 변형
Array.sort() : 배열 정렬
Array.reverse() : 배열 반전
Array.join(sepaeator): 배열 값을 문자열로 변황
배열의 반복
Array.sort() : 함수의 매개변수로 함수를 넣어 고차 함수를 이용한 정렬 수행 가능
//before
let nums = [1, -1, 4, 0, 10, 20, 12];
console.log(nums.sort());
//after
let num = function(x, y){return x - y}
let nums = [1, -1, 4, 0, 10, 20, 12];
console.log(nums.sort(num));
Array.forEach() : 배열 요소 별 함수 각각에 실행
Array.map(): 배열 요소 별 함수 호출 및 결과를 배열로 반환
Array.find(): 콜백 함수의 조건을 만족하는 단 하나의 값만 반환
Array.filter(): 콜백 함수의 조건을 만족하는 값을 배열로 반환
Array.reduce(): 요소별로 함수 누적 결과값 반환
for ... length(index 접근)
for ... of(element 접근)
for ... in(ley 접근)
let number = [1,2,3]
for (let i = 0; i < number.length; i++){
console.log(number[i]);
}
for (let num of number){
console.log(num);
}
for (let key in number){
console.log(number[key]);
}
배열의 논리 연산
Array.some(): 배열 내 단 하나라도 콜백 함수의 조건을 만족하는 요소가 있으면 true 없으면 false (빈 배열일 때도 false)
Array.every(): 배열 내 모든 요소가 콜백 함수의 조건을 만족한다면 true, 아니면 false반환 (빈 배열일때는 true)
배열 선언
: new Array 또는 []를 통해 선언하며 사이즈 혹은 값을 입력하여 초기화 가능
접근 방법
Array[index] : index를 통하여 O[1] 접근
배열 문제를 풀어보자!
1) 수열 최소값 위치
수열이 주어질 때, 이 수열의 있는 수 중 최소값의 위치를 모두 출력하는 프로그램을 작성하시오. 입력은 자연수로 된 배열을 받고, 시작 위치는 0로 계산하여 취소값의 위치를 배열로 반환합니다.
먼저 최소값을 구한 다음에 최소값에 해당하는 index 위치를 구합니다.
function answer(nums) {
let result = [];
// 1. 최소값
let min = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < nums.length; i++) {
if (min > nums[i]) {
min = nums[i];
}
}
// 2. 최소값에 해당하는 위치 index
let count = 0;
for (let i = 0; i < nums.length; i++) {
if (min == nums[i]) {
result[count++] = i;
}
}
return result;
}
2) 체스 세트
오래된 창소에서 체스판과 체스 기물을 발견했습니다. 불행히도 기물 별 개수가 부족하거나 많아, 완전한 한 세트를 이루고 있지 못하고 있어 보입니다. 게임을 하기 위해 부족하거나 많은 기물의 개수를 계산하여 반환하는 프로그램을 제작해주세요
king(1), queen(1), rooks(1), bishops(2), knights(2), pawns(8)
배열로 만들어서 각각의 위치에서 빼면 됩니다.
function answer(chess) {
let result = [];
let onchess = [1, 1, 2, 2, 2, 8];
for (let i = 0; i < chess.length; i++) {
result.push(onchess[i] - chess[i]);
}
return result;
}
3) 두 수 최대 합
수열이 주어질 때, 이중 두 개의 수를 선택하여 최대 합이 나올 수 있도록 프로그램을 제작해주세요
내림차순으로 정렬한 후 배열의 첫번째와 두번째를 출력해줍니다.
function answer(nums) {
let sortedNums = [...nums].sort((a, b) => b - a);
let maxSum = [sortedNums[0], sortedNums[1]];
return maxSum;
}
function answer(nums) {
let result = [];
result = nums[0] > nums[1] ? [nums[0], nums[1]] : [nums[1], nums[0]];
for (let i = 2; i < nums.length; i++) {
if (nums[i] > result[0]) {
result[1] = result[0];
result[0] = nums[i];
} else if (nums[i] > result[1]) {
result[1] = nums[i];
}
}
return result;
}
4) 일곱 난장이
일터에 나갔던 난장이 9명이 와서는 모두 자기가 일곱 난장이 중 하나라고 우기고 있습니다.
모든 난장이의 가슴에는 숫자가 표시괸 배치가 있는데, 다행히도 일곱 난장이의 배지에 표시괸 숫자의 합이 100라는 단서로 일곱난장이를 분별할수 있습니다.
맨처음에 2명에 대한 합한 숫자를 구하기 위해 모든 값을 더하고 100를 빼줍니다.
두 요소의 합이 100을 뺀 값과 같은지 비교합니다.
그 두명의 값만 빼고 result 값에 넣어줍니다.
function answer(dwarf) {
let result = [];
let sum = 0;
for (let i = 0; i < dwarf.length; i++) {
sum += dwarf[i];
}
sum -= 100;
let faker = [];
for (let i = 0; i < dwarf.length; i++) {
for (let j = i + 1; j < dwarf.length; j++) {
if (sum == dwarf[i] + dwarf[j]) {
faker[0] = i;
faker[1] = j;
break;
}
}
if (faker.length != 0) break;
}
let count = 0;
for (let i = 0; i < dwarf.length; i++) {
if (faker[0] != i && faker[1] != i) {
result[count++] = dwarf[i];
}
}
return result;
}
function answer(dwarf) {
let sum = dwarf.reduce((a, b) => a + b, 0) - 100;
let faker = [];
dwarf.forEach((value, index) => {
let found = dwarf.find((v, i) => i !== index && v + value === sum);
if (found !== undefined) {
faker = [index, dwarf.indexOf(found)];
}
});
return dwarf.filter((_, index) => !faker.includes(index));
}
4) 나무 그리기
조카가 나무 그리기를 어려워하고 있습니다. 어른 조카를 위해 나무를 그려주는 프로그램을 만들어줍니다.
맨처음에 공백처리를 해줍니다.
피라미드 대칭을 유지하기 위해 i * 2 + 1 를 해줍니다.
마지막으로 개행을 해줍니다.
function answer(height) {
let str = "\n";
for (let i = 0; i < height; i++) {
for (let j = 0; j < height - i - 1; j++) {
str += " ";
}
for (let j = 0; j < i * 2 + 1; j++) {
str += "*";
}
str += "\n";
}
return str;
}
4) Two Sum
배열과 정수 값이 주어질 때, 배열 내 두 값을 합하여 정수 값을 만들 수 있도록 두개의 index반환하는 함수를 작성하시오
배열을 순회하면서 target에서 현재 요소를 뺀 값이 map에 있는지 확인 후 map에 있으면 그 인덱스와 현재 인덱스를 반환합니다.
function answer(nums, target) {
let map = {}; // key, value
// target - nums[i] = nums[j]
// for 2중 O(n^2) -> for 1중 O(n)
for (let i = 0; i < nums.length; i++) {
if (map[target - nums[i]] != undefined) {
return [map[target - nums[i]], i];
}
map[nums[i]] = i;
}
return [];
}
5) ox 퀴즈
정답을 맞춘 경우에 문제당 1점을 부여하고 연속적으로 맞출 경우에는 가산점을 부여합니다.
1일 경우에 score를 누적되도록 더합니다.
function answer(mark) {
let result = 0;
let score = 0;
for (let i = 0; i < mark.length; i++) {
if (mark[i] == 1) {
result += ++score;
} else {
score = 0;
}
}
return result;
}
6) 벽돌 옮기기
새로 온 알바생이 벽돌의 높이를 맞추지 않고 벽을 쌓아 놓았습니다.
관리자를 위해 몇 개의 벽돌을 옮겨야 벽돌의 높이가 갈아질 수 있는지 구해주는 프로그램을 제작해주세요.
처음에 벽돌 높이 평균을 구하고 현재 벽돌 높이 - 벽돌 높이 평균를 계산해서 옮겨야 할 벽돌 개수 구합니다.
function answer(blocks) {
let result = 0;
let avg = 0;
for (let i = 0; i < blocks.length; i++) {
avg += blocks[i];
}
avg /= blocks.length;
for (let i = 0; i < blocks.length; i++) {
if (blocks[i] > avg) {
result += blocks[i] - avg;
}
}
return result;
}
6) 숫자 빈도수 구하기
두 자연수 M, N을 입력받아, M부터 N까지 각 자리수의 빈도수를 합하는 프로그램을 제작해야 합니다.
주어진 범위 [s, e] 내의 모든 숫자에서 각 자릿수의 빈도수를 계산합니다. 각 숫자는 while 루프를 통해 자릿수별로 처리되며, 해당 자릿수의 빈도수를 증가시킵니다. 결과는 0부터 9까지의 자릿수 빈도수를 담은 배열로 반환됩니다.
function answer(s, e) {
let result = [];
for (let i = 0; i < 10; i++) {
result[i] = 0;
}
// 1. s <= n <= e
let num;
for (let i = s; i <= e; i++) {
num = i;
// 2. n => % /
while (num != 0) {
result[num % 10]++;
num /= 10;
num = parseInt(num);
}
}
return result;
}
7) 달팽이 만들기
조카를 잠 재우기 위해 달팽이 모양으로 숫자를 하나씩 적어주는 프로그램이 필요하게 되었습니다.
이를 위해 정사각형 모양의 달팽이 2차원 배열을 그려주는 함수를 작성해주세요
function answer(length) {
let result = [];
for (let i = 0; i < length; i++) {
result[i] = [];
}
let direction = 1;
let x, y, num;
x = y = num = 0;
x--;
while (1) {
for (let i = 0; i < length; i++) {
x += direction;
result[y][x] = ++num;
}
length--;
if (length <= 0) break;
for (let j = 0; j < length; j++) {
y += direction;
result[y][x] = ++num;
}
direction *= -1;
}
return result;
}