[binarysearch] 58, 60, 61, 79, 85 (Easy)

황은하·2021년 11월 24일
0

알고리즘

목록 보기
99/100
post-thumbnail

58. High Frequency

가장 많이 나온 문자의 빈도를 반환하는 문제.
맵에 넣으면서 개수를 세는데, 개수가 증가할 때마다 최대값을 기억해 두었다가 최대값을 반환했다.

class Solution {
    solve(nums) {
        if (!nums.length) return 0;
        let maxCount = 0;
        const map = new Map();

        for (let i = 0; i < nums.length; i++) {
            let curCount = map.has(nums[i]) ? map.get(nums[i]) + 1 : 1;
            map.set(nums[i], curCount);
            maxCount = Math.max(maxCount, curCount);
        }
        return maxCount;
    }
}


60. Square of a List

오름차순으로 정렬된 배열에서 제곱하여 정렬된 배열을 반환하는 문제.
처음에는 현재 배열의 모든 값을 제곱한 뒤 정렬해주었다.

  • 내가 푼 방법
class Solution {
    solve(nums) {
        if (!nums.length) return nums;
        const newNums = nums.map((val) => val ** 2);
        newNums.sort((a, b) => a - b);
        return newNums;
    }
}

Two pointer로 풀었다.
어차피 오름차순으로 정렬되어 있기 때문에 인덱스를 right-left 로 구해도 맨 뒤부터 1씩 줄어들어서 문제가 발생하지 않는다.

  • 다른 사람이 푼 방법 -> 더 빠르다.
class Solution {
    solve(nums) {
        if (!nums.length) return nums;
        const result = Array(nums.length)
        let left = 0;
        let right = nums.length - 1;

        while (left <= right) {
            if (nums[left] ** 2 > nums[right] ** 2) {
                result[right - left] = nums[left] ** 2;
                left++;
            } else {
                result[right - left] = nums[right] ** 2;
                right--;
            }
        }
        return result;
    }
}


61. Recurring Character

최초로 중복되어 나온 문자의 인덱스를 반환하는 문제.
set에 최초로 나온 문자를 넣은 뒤, set에 이미 존재하는 문자가 나왔다면 현재 인덱스를 반환했다.

class Solution {
    solve(s) {
        if (!s.length || s.length == 1) return -1;
      
        const set = new Set();
        for (let i = 0; i < s.length; i++) {
            if (set.has(s[i])) return i;
            else set.add(s[i]);
        }
        return -1;
    }
}


79. Merging Two Sorted Lists

두 배열을 정렬된 순서로 합치는 문제.

  • 첫 번째 방법
    sort() 사용
class Solution {
    solve(a, b) {
        if (!a.length && !b.length) return a;
        if (!a.length) return b;
        if (!b.length) return a;
        
        const result = a.concat(b);
        result.sort((a, b) => a - b);
        return result;
    }
}
  • 두 번째 방법
    정렬시키지 않고 값을 하나씩 비교하면서 넣었다.
    더 빠르다.
class Solution {
    solve(a, b) {
        if (!a.length && !b.length) return a;
        if (!a.length) return b;
        if (!b.length) return a;

        let idxA = 0;
        let idxB = 0;
        const result = [];

        while (idxB < b.length) {
            if (idxA >= a.length) {
                result.push(b[idxB++]);
                continue;
            }
            if (a[idxA] <= b[idxB]) result.push(a[idxA++]);
            else result.push(b[idxB++]);
        }

        if (idxA < a.length) 
            for (; idxA < a.length; idxA++) 
                result.push(a[idxA]);
            
        return result;
    }
}


85. Sum of the Digits

현재 숫자를 각 자리수로 잘라서 각 한자리 숫자들을 더한 값을 반환하는 문제.

  • 내가 푼 방법
    현재 숫자를 10씩 나눠서 나머지를 최종값에 더하고, 몫을 현재 숫자로 저장하면서 최종값에 한 자리씩 더했다.
class Solution {
    solve(num) {
        if (num.length === 1) return num;
        let total = 0
        while (num > 0) {
            total += num % 10;
            num = Math.floor(num / 10);
        }
        return total;
    }
}
  • 다른 사람이 푼 방법
    문자로 바꾸어서 푼 방법. 한자리씩 받아와서 parseInt로 숫자로 형변환 시켜 더해주었다.
class Solution {
    solve(num) {
        if (num.length === 1) return num;
        num = num.toString();
        let count = 0;
        for (let n of num) {
            count += parseInt(n);
        }
        return count;
    }
}
profile
차근차근 하나씩

0개의 댓글