[Algorithm] array

3 분 소요

▶️ Arrar (1차원배열)

배열을 사용해서 문제를 구현한다

지정된 길이를 가지고 있는 배열 선언

const arr = new Array(배열길이).fill(초기화 값);

주의할 사항 → 정렬해서 배열이 제공되었다는 것은 O(n)의 시간복잡도를 가지도록 문제를 해결하라는 것!

1. 증가수열 찾기

단일 for문을 사용해서 문제를 해결한다

접근방법 : 배열의 인덱스를 이용해서 앞뒤 요소를 비교한다

const solve = (arr) => {
  for (let i = 0; i < arr.length; i++){
    if(arr[i] < arr[i+1]){
      // 문제에 따른 요구사항 구현
    }
  }
}

2. 바이토닉 수열 문제

[ 바이토닉인지를 확인하는 문제를 기준 ]

바이토닉 수열이란 증가하다가 감소하는 수열을 말한다

바이토닉 수열은 반복문 두개를 이용해서 해결한다 (중첩 x)

증가를 기준으로 진행하는 반복문
- 진행하는 반복문 이후 확인을 한번 해준다
- 포인트가 전혀 움직이지 않음(처음부터 증가하지 않음)
- 포인트가 제일 마지막에 위치(끝까지 증가)
감소를 기준으로 진행하는 반복문
- 왼쪽으로 진행하는 반복문 이후 확인 필요

// arr = [1, 2, 3, 4]라는 수열 입력됨

// 증가해야하므로 오른쪽 요소의 값이 더 크다면 i에 +1
while (arr[i] < arr[i+1]) i++;

// 전혀 증가하지 않거나 끝까지 증가만 한 경우를 확인
if (i === 0 || i === arr.length - 1) return false;

증가를 기준으로 진행하는 반복문의 예시이다

위 예시는 [1, 2, 3, 4]의 배열이 입력이므로 끝까지 증가만 해서 i === arr.length - 1의 조건에 걸린다

// 감소해야하므로 오른쪽 요소의 값이 더 작다면 i에 +1
while (arr[i] > arr[i+1]) i++;

// 끝까지 진행하지 않았으면 바이토닉 수열이 아니다
if (i !== n - 1 ) return false;

감소를 기준으로 진행하는 반복문의 예시이다

증가를 확인하는 반복문이 종료된 i의 시점에서 진행하고, 끝까지 진행했는가를 확인한다

3. 거리두기 문제

배열이 있을때 항목간 얼마나 멀리 떨어져있는지를 판별하는데 사용할 수 있다

배열을 기준으로 양방향으로 한번씩 계산해준다

왼쪽으로 진행
오른쪽으로 진행

- 문제

“X”와 가장 먼 “O”의 인덱스를 선정하는 문제
[ X O O X O O O X O ]

직관적으로 봤을때 6번째 O가 답이다

- 풀이

새로운 배열을 선언하고 임시변수를 선언한다

const tempArr = new Array(입력된 배열의 길이).fill(초기값);
let temp = 0;

이후 왼쪽과 오른쪽으로 진행하며 계산한다

// 왼쪽에서 오른쪽
for (let i = 0; i < n; i++){
  if(arr[i] === 1) {
    temp = 0;
  } else{
    temp++;
  }
  tempArr[i] = d;
}
// 오른쪽에서 왼쪽
for (let i = n-1; i >= 0; i--){
  if(arr[i] === 1){
    temp = 0
  } else{
    temp++;
  }
  tempArr[i] = Math.min(tempArr[i], temp)
}

// tempArr
[0, 1, 1, 0, 1, 2, 1, 0, 1]

tempArr에서 가장 큰수의 인덱스를 찾아주면 된다!

배열 관련 JS 메소드

1. join()

배열의 각 항목을 합쳐준다 이때 구분자를 입력할 수 있다

array.join("구분자")

아무것도 입력하지 않으면 ,를 구분자로 사용한다

2. split()

입력한 구분자를 대상으로 배열을 분리한다

string.split("구분자")

정규표현식도 사용이 가능하다
limit 옵션을 줄 수 있다 두번째 파라미터로 숫자를 입력하면 반환하는 배열의 크기를 정할 수 있다

3. reverse()

배열의 순서를 거꾸로 만들어준다

array.reverse()

원본을 변화시키기 때문에 주의해야한다

4. splice()

해당 부분을 삭제한다

array.splice(기준인덱스, 삭제개수)

원본을 변화시키므로 주의해야 한다
첫 번째 인자: 시작점
두번째 인자: 삭제할 개수

5. slice()

배열의 특정부분을 반환한다

array.slice(시작인덱스, 마지막인덱스)

시작지점과 어디까지인지(범위) 인덱스를 입력한다 (마지막 인덱스는 반환에서 제외된다)

6. find()

조건을 만족하는 첫 번째 요소의 값을 반환한다

array.find(item => 조건)

값을 찾으면 값 반환, 못찾으면 undefined를 반환

7. filter()

조건에 부합하는 값들을 새로운 배열로 만들어 반환

array.filter(item => 조건);

콜백함수를 파라미터로 받는다
콜백함수에서 true가 나온 값들을 새로운 배열에 저장

8. map()

배열의 요소 하나하나를 다른것으로 변환할 수 있다, 데이터를 맵핑한다

array.map(item => 변환값)

새로운 배열이 리턴된다
ex) array.map(item => +item) string 타입인 숫자를 number 타입으로 변환

9. some()

조건에 해당하는 것이 하나라도 있는지를 확인

array.some(item => 조건);

조건이 하나라도 맞으면 true를 반환
true를 반환하는 순간 some함수 종료

10. every()

모든 요소가 조건에 해당하는지 확인

array.every(obj => 조건)

모든 요소가 조건에 해당해야 true를 반환

10. reduce()

반복적으로 결과값을 다음 인자로 넘겨준다

array.reduce((prev, curr) => {
  return (다음 prev로 넣어줄 값)
}, 초기값)

콜백함수와 초기값을 전달한다 (초기값은 옵션)
콜백함수는 누적된 값을 반환한다
초기값을 넣은경우 초기값은 처음에 prev로 들어간다
reduceRight(): reduce와 동일하지만 순서가 반대로 진행된다

ex)

arr = [1, 2, 3, 4];
arr.reduce((prev, curr) => {
  console.log(prev);
  return prev + curr;
}, 0);

// 결과
0
1
3
6

Twitter Facebook LinkedIn

원종빈