[JS - 알고리즘] 02. 1차원 배열

1차원 배열

01. 수열 축소

• slice : slice() 메서드는 어떤 배열의 begin부터 end까지(end 미포함)에 대한 얕은 복사본을 새로운 배열 객체로 반환합니다. 원본 배열은 바뀌지 않습니다.
  • begin음수 인덱스는 배열의 끝에서부터의 길이를 나타냅니다. slice(-2) 는 배열에서 마지막 두 개의 엘리먼트를 추출합니다.begin이 배열의 길이보다 큰 경우에는, 빈 배열을 반환합니다.
  • begin이 undefined인 경우에는, 0번 인덱스부터 slice 합니다.
  • 0을 시작으로 하는 추출 시작점에 대한 인덱스를 의미합니다.
  • end예를 들어, slice(1,4)는 두번째 요소부터 네번째 요소까지 (1, 2 및 3을 인덱스로 하는 요소) 추출합니다.end가 생략되면 slice()는 배열의 끝까지(arr.length) 추출합니다.
  • 만약 end 값이 배열의 길이보다 크다면, silce()는 배열의 끝까지(arr.length) 추출합니다.
  • 음수 인덱스는 배열의 끝에서부터의 길이를 나타냅니다. 예를들어 slice(2,-1) 는 세번째부터 끝에서 두번째 요소까지 추출합니다.
  • 추출을 종료 할 0 기준 인덱스입니다. slice 는 end 인덱스를 제외하고 추출합니다.
  • 반환 값
  • 추출한 요소를 포함한 새로운 배열.
• 내 풀이

function solution(s, m) {
    let answer;
    for (let i = m; i > 0; i--) {
        for (let j = 1; j < s.length; j++) {
            s[j - 1] = s[j] - s[j - 1];
        }
    }
    //0에서 m번만큼의 길이로 잘라준다.
    s = s.slice(0, s.length - m);
    console.log(s);

    return answer;
}

console.log(solution([5, 3, 7, 9, -2], 1));
console.log(solution([5, 3, 7, 9, -2], 2));

02. 제곱수 정렬

• 오름차순 정렬한 배열이기 때문에, left, right 투 포인터를 사용해 절대값이 더 큰 숫자를 제곱해준 다음에 새로운 배열에 넣어준다. 그러면 sort()를 할 필요가 없다. sort를 최대한 사용하지 않으려는 이유는 시간복잡도 때문이다.
• N의 제한 조건이 10만이 넘어간다면 최대한 O(n)으로 짜주자.
• 풀이

function solution(s) {
    let answer;
    let left = 0,
        right = s.length - 1;
    let arr = Array(s.length).fill(0);
    let pos = s.length - 1;

    //left보다 right가 클 경우에만 loop
    while (left <= right) {

        //절대값이 left가 더 큰 경우
        if (Math.abs(s[left]) > Math.abs(s[right])) {
            // 큰 값을 찾았을 때, pos idx에 값을 넣어주고
            //left idx는 증가시켜주고, pos idx는 감소시켜 준다.
            arr[pos] = s[left] * s[left];
            left++;
            pos--;

          // 절대값이 right가 더 큰 경우, 
        } else if (Math.abs(s[left]) < Math.abs(s[right])) {
            arr[pos] = s[right] * s[right];
            right--;
            pos--;
        } else {
            arr[pos] = s[right] * s[right];
            right--;
            pos--;
        }
    }
    console.log(arr);
    return answer;
}

console.log(solution([-4, -1, 0, 3, 10])); //[0, 1, 9, 16, 100]
console.log(solution([-7, -3, 2, 3, 11])); //[4, 9, 9, 49, 121]

03. 수열의 높이 조정

• 배열을 탐색하면서 최댓값과 최솟값을 찾는다. 연속된 수열이 아니기에 사용된 수열의 값을 arr에 저장해준다.
• 풀이

function solution(s, m) {
    let answer;
    let arr = Array(1000).fill(0);
    let max = -2147000000;
    let min = 2147000000;

    //최대값과 최소값을 찾아준다.
    for (let i = 0; i < s.length; i++) {
        if (max < s[i]) max = s[i];
        if (min > s[i]) min = s[i];
    }

    // 사용되는 값을 +1 해준다.
    for (let i = 0; i <= max; i++) {
        arr[s[i]] += 1;
    }

    // 입력 받은 m만큼 명령 수행
    for (let i = m; i > 0; i--) {
        // min === max일 경우 다 같은 경우이므로 return 0.
        if (min === max) return 0;

           // 가장 큰 값이 1일때, max-1의 값을 max 값으로 만들어줘야 한다.
        // max 값의 변화를 위해서 증감연산자를 사용
        if (arr[max] === 1) {
            arr[max]--;
            max--;
            arr[max]++;
        } else {
            // max 값의 idx가 1이 아니면 1보다 큰 경우밖에 없다.
            // 위와는 달리 max의 값이 변화하지 않았다.
            arr[max]--;
            arr[max - 1]++;
        }
        // 가장 작은 값이 1일때, min + 1의 값을 min 값으로 만들어줘야 한다.
        // min 값의 변화를 위해서 증감연산자를 사용
        if (arr[min] === 1) {
            arr[min]--;
            min++;
            arr[min]++;
        } else{ 
            // min 값의 idx가 1이 아니면 1보다 큰 경우밖에 없다.
            // 위와는 달리 min의 값이 변화하지 않았다.
            arr[min]--;
            arr[min + 1]++;
        }
    }
    // 높이값 return
    return max - min;
}

console.log(solution([2, 1, 3, 7, 5], 2));
console.log(solution([69, 42, 68, 76, 40, 87, 14, 65, 76, 81], 50));

04. 가장 높은 증가수열

• 가장 높은 차를 누적하는 문제.

function solution(arr) {
    let answer = 0;
    let height = 0;

    for (let i = 1; i < arr.length; i++) {
        // 증가하는 수열이라면 height에 저장한다.
        if (arr[i - 1] < arr[i]) {
            height += arr[i] - arr[i - 1];
        } else {
            //증가하는 수열이 아닐때, 최대값을 answer에 집어넣는다.
            answer = Math.max(answer, height);
            height = 0;
        }
    }
    //for문이 끝나고 나서도 최대값을 저장해줘야 한다.
    answer = Math.max(answer, height);
    return answer;
}

console.log(solution([5, 2, 4, 7, 7, 3, 9, 10, 11]));

 

5. 가장 긴 수열

function solution(nums) {
    let answer;
    let minus_cnt = 1;
    let plus_cnt = 1;
    let p_max = -2147000000;
    let m_max = -2147000000;


    for (let i = 1; i < nums.length; i++) {
        // 증가수열일때 증가cnt를 + 1
        if (nums[i - 1] < nums[i]) {
            plus_cnt++;
        } else { // 증가가 아닐 경우, 길이가 최대라면 p_max에 저장하고 cnt를 1로 초기화
            p_max = Math.max(p_max, plus_cnt);
            plus_cnt = 1;
        }
        // 감소수열일때 감소cnt를 +1
        if (nums[i - 1] > nums[i]) {
            minus_cnt++;
        } else { // 감소가 아닐 경우, 길이가 최대라면 m_max에 저장하고 cnt를 1로 초기화
            m_max = Math.max(m_max, minus_cnt);
            minus_cnt = 1;
        }
        // if문에서 plus_cnt가 증가하고 나온 경우일수도 있다.
        // 따라서 최대값을 또 한번 정해준다.
        p_max = Math.max(p_max, plus_cnt);
        m_max = Math.max(m_max, minus_cnt);
        answer = Math.max(p_max, m_max);
    }

    return answer;
}

console.log(solution([5, 3, 6, 7, 9, 8, 5, 3, 1, 2]));
console.log(
    solution([1, 2, 3, 3, 4, 5, 6, 7, 7, 8, 9, 10, 11, 12, 13, 14, 15])
);

6. 바이토닉 수열

• 바이토닉 수열이란?
  • 연속적으로 증가하는 수열과 감소하는 수열이 함께 존재하는 것을 바이토닉 수열이라고 한다.

function solution(nums) {
    let answer = 'YES';
    let n = nums.length;
    let i = 0;
    // 증가하는 수열이면 i를 계속 증가
    while (i + 1 < n && nums[i] < nums[i + 1]) i++;
    // 증가하고 나서도 i가 0이거나 수열 끝에 다다르면 바이토닉 수열이 아니다.
    if (i === 0 || i === n - 1) answer = 'NO';

    // 감소하는 수열이면 i를 계속 증가
    while (i + 1 < n && nums[i] > nums[i + 1]) i++;
    // 만약 i가 nums의 끝에 다다르지 않는다면 바이토닉 수열이 아니다.
    if (i !== n - 1) answer = 'NO';

    return answer;
}

console.log(solution([1, 2, 3, 4, 5, 3, 1]));
console.log(solution([1, 3, 4, 5, 5, 6, 4, 3]));
console.log(solution([1, 2, 3, 4, 5]));

7. 거리두기

• 처음에 생각하는 것이 좀 어려웠다. ch라는 임시 배열을 활용해 O(n)의 시간복잡도로 풀어낸다.
• 사람이 있는 곳을 만나면 ch 배열에서 0으로 바꿔준다.

// - 앞에서부터 한번, 뒤에서부터 한번 쭉 2번 탐색을 해준다.
// - distance를 0으로 바꾼다. 0을 만나면 ++ -> 왼쪽 사람으로부터 떨어진 거리
// - 왜 distance를 1000으로 주는가? 1000 distance 설정을 해야 시작 부분에서 사람이 없을 경우에 1000으로 설정이 되서 나중에 거리 값을 측정할 때 min값으로 변경이 되게 된다.
function solution(nums) {
    let answer;

    // 임시 저장공간 ch배열 생성
    let ch = Array(nums.length).fill(0);

    // nums를 탐색하면서 사람이 있는 곳은 값을 0으로 설정해준다.
    // 처음 시작할 때 사람이 없는 경우가 있으므로, 초기 distance 1000이 입력된다.
    // 그래서 다시 되돌아올 때, min연산으로 거리 값을 제대로 입력해줄 수 있다.
       let distance = 1000;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 1) {
            ch[i] = 0;
            distance = 1;
        } else {
            ch[i] = distance;
            distance++;
        }
    }

    // 이번엔 배열의 끝에서부터 다시 처음으로 탐색한다.
    // 마찬가지로 distance를 1000으로 해준다.
    distance = 1000;
    for (let i = nums.length - 1; i >= 0; i--) {
        if (nums[i] === 1) {
            ch[i] = 0;
            distance = 1;
        } else {
            // 기존의 ch배열에 입력된 distance 값과 비교해서 최소값을 입력
            ch[i] = Math.min(distance, ch[i]);
            distance++;
        }
    }

    answer = -10;
    for (let x of ch) {
        // 요소들 중에서 가장 큰 값이 거리이다.
        answer = Math.max(x, answer);
    }
    return answer;
}

console.log(solution([1, 0, 0, 0, 1, 0, 0, 1, 0, 1]));

8. 빈도수 구하기

• 해시를 이용해서 간단하게 풀 수가 있다.

function solution(arr, k) {
    let hash = new Map();

    // x 요소가 해시에 존재한다면, 해시에 값 등록
    for (let x of arr) {
        // 만약 기존의 해시에 값이 존재한다면, value 값을 +1
        if (hash.has(x)) {
            hash.set(x, hash.get(x) + 1);
        } else { // 만약 기존의 해시에 값이 없다면, 해시에 등록
            hash.set(x, (hash.get(x) || 0) + 1);
        }
    }

    // sort의 compare 파라미터를 이용해 해시의 value 값을 기준으로 정렬시킨다.
    let temp = [...hash].sort((a, b) => b[1] - a[1]);

    // 정렬된 value 기준으로 k개만큼 answer 배열에 넣어준다.
    let answer = [];
    for (let i = 0; i < k; i++) {
        answer.push(temp[i][0]);
    }

    return answer;
}

console.log(solution([1, 1, 1, 2, 2, 3], 2));
console.log(solution([3, 3, 3, 5, 1, 1, 1, 7, 2, 2], 3));

9. 아나그램

• undefined와 null은 자동으로 Number로 형변환된다.
• 자세한 내용은 이곳을 참고

console.log(typeof null); //object
console.log(typeof undefined); //undefined
console.log(Number(null)); // 0
console.log(Number(undefined)); // NaN

console.log(undefined || 0); // 0
console.log(null || 0); // 0

console.log(undefined || 10); //10
console.log(null || 5); //5

console.log(null || true); // true
console.log(undefined || true); // true

console.log(null || false); // false
console.log(undefined || false); // false

• 내 풀이

function solution(str1, str2) {
    let answer = 'YES';
    let temp;
    let hash = new Map();
    let hash2 = new Map();

    // hash에 str1를 등록한다.
    for (let i = 0; i < str1.length; i++) {
        // hash.get(str1[i])d에 값이 없다면 undefined, undefined || 0 연산은 0이 나온다. 
        hash.set(str1[i], (hash.get(str1[i]) || 0) + 1);
    }

    // hash2에 str2를 등록한다.
    for (let i = 0; i < str2.length; i++) {
        hash2.set(str2[i], (hash2.get(str2[i]) || 0) + 1);
    }

    // hash2가 key 값을 가지고 있고, val 값이 똑같다면 continue,
    // 다르면 NO를 출력
    for (let [key, val] of hash) {
        if (hash2.has(key)) {
            if (val === hash2.get(key)) {
                continue;
            } else {
                answer = 'NO';
                break;
            }
        }
    }
    return answer;
}

10. 문자열 구분하기

• 첫번째 방법

// 1번째 방법
function solution(s) {
    let answer, i;

    // s[0]의 문자 길이만큼 for문 실행
    for (i = 0; i < s[0].length; i++) {
        let hash = new Map();
        let flag = true;

        // s가 가지고 있는 요소의 개수만큼 실행
        for (let j = 0; j < s.length; j++) {
            // 각각의 요소에서 s[0]의 길이인 i 만큼 substring을 실시한다.
            let x = s[j].substring(0, i + 1);
            // 만약 hash에 substring한 key가 있다면 false하고 탈출!
            if (hash.has(x)) {
                flag = false;
                break;
            }
            // key값이 없다면 hash에 key를 등록한다.
            hash.set(x, 1);
        }

        // 2번째 for문이 끝나고도 flag가 true라면 첫번째부터 일치하지 않으므로 break
        if (flag) break;
    }

    // se  se   se  까지 일치하는 것이므로 +1을 해준다.
    answer = i + 1;
    return answer;
}

console.log(solution(['seeasue', 'sesseysu', 'semeas']));
console.log(solution(['ackky', 'kabck', 'yokkcs']));
console.log(solution(['longlong', 'longtong', 'longbig']));

• 2번째 방법

// 2번째 방법
function solution2(s) {
    let answer, i;
    for (i = 0; i < s[0].length; i++) {
        // set 자료형을 이용한다.
        let set = new Set();
        for (let j = 0; j < s.length; j++) {
            // s의 요소들을 i번째까지 substring하고 set에 등록한다.
            let x = s[j].substring(0, i + 1);
            set.add(x);
            // 만약 set의 size가 1이 아니라면 일치하지 않는 경우이다.
            if (set.size !== 1) return i + 1;
        }
    }
    return 1;
}


console.log(solution(['seeasue', 'sesseysu', 'semeas']));
console.log(solution(['ackky', 'kabck', 'yokkcs']));
console.log(solution(['longlong', 'longtong', 'longbig']));