📌Introduction
1. Max Consecutive Ones
Given a binary array nums, return the maximum number of consecutive 1's in the array.
(주어진 이진수 배열 안에서 연속된 1의 갯수 구하기)
💡 1차 풀이
var findMaxConsecutiveOnes = function(nums) {
let cnt = 0;
let answer = 0;
for(let i = 0; i <= nums.length; i++) {
if(nums[i] === 1) {
cnt ++;
}
else {
if(cnt > 0) {
answer = Math.max(answer, cnt);
cnt = 0;
}
}
}
return answer;
};
속도나 메모리 사용량은 보통이다.
💡 2차 풀이
var findMaxConsecutiveOnes = function(nums) {
let cnt = 0;
let answer = 0;
nums.forEach(num => {
if(num === 0) {
cnt = 0;
}
else {
cnt ++;
answer = answer > cnt ? answer : cnt;
}
})
return answer;
};값이 0일 때가 아니라 1일 때마다 answer값을 갱신했다.
for과 forEach의 속도차이가 크지 않아 forEach를 사용했다.
결과적으로 속도는 개선되었으나 메모리 사용량이 늘어났다;
2. Find Numbers with Even Number of Digits
Given an array nums of integers, return how many of them contain an even number of digits.
(글자수가 짝수인 값의 갯수 반환)
💡 1차 풀이
var findNumbers = function(nums) {
let answer = 0;
nums.forEach(num => {
if((''+num).length % 2 === 0) answer ++;
})
return answer;
};
속도가 그리 빠른 편이 아니다. 조금 수정해봤다.
💡 2차 풀이
var findNumbers = function(nums) {
let answer = 0;
for(let i = 0; i < nums.length; i++) {
if(nums[i].toString().length % 2 === 0) answer += 1;
}
return answer;
};숫자를 문자열로 바꿀 때, +number 보다 number.toString() 이 더 빠르다.
그리고 연결리스트가 아닌 이상 배열에서는 forEach보다 for문이 더 빠르다.
3. Squares of a Sorted Array
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
(배열의 값을 제곱한 수를 내림차순으로 나열한 배열 반환)
💡 풀이
var sortedSquares = function(nums) {
let answer = [];
for(let i = 0; i < nums.length; i++) {
answer.push(nums[i] * nums[i]);
}
return answer.sort((a,b) => a - b);
};여기서 nums[i] * nums[i] 를 nums[i]**2 로 바꿔주면 조금 더 빨라진다.
📌Inserting Items Into an Array
1. Duplicate Zeros
Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.
Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything. (0을 발견하면 옆에 0을 추가하고, 원래 배열의 크기를 지키기)
💡 풀이
var duplicateZeros = function(arr) {
for(let i = 0; i < arr.length;) {
if(arr[i] === 0) {
arr.splice(i+1, 0, 0);
arr.pop();
i += 2;
}
else i ++;
}
};
2. Merge Sorted Array
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
(오름차순으로 정렬된 nums1, nums2 / m = nums1에서 병합되어야 하는 원소 갯수 / n = nums2의 원소 개수
nums1과 nums2를 nums 안에서 병합하시오 (병합 후 nums1의 길이 = m + n))
✔ non-decreasing order (비내림차순)
배열에 중복값이 있을 때, 오름차순을 비내림차순이라고 표현한다.
왜냐면 같은 값이 있어 무조건 오름차순이 아니므로, 다소 모호하지만 비내림차순이라는 말을 쓰는 것이다.
그냥 오름차순이라고 받아들이면 된다.
💡 풀이
var merge = function(nums1, m, nums2, n) {
while(nums1.length !== m) {
nums1.pop();
}
while(nums1.length !== m+n) {
nums1.push(nums2.pop());
}
nums1.sort((a,b) => a-b);
};문제 설명이 모호하고 (특히 m에 대한 설명) 영어다보니까 이해하는데 시간이 좀 걸렸다.
리트코드는 원래 이렇게 문제가 자세히 써있지 않고 예시 보고 알아서 파악해야 하나?ㅠㅠ
nums1 안에서 병합을 해야하니 병합에 필요없는 요소를 없애고,
nums2의 원소를 차례대로 데려온 후 오름차순으로 정렬했다.
속도는 빠른 편으로 측정됐다.
📌Deleting Items From an Array
1. Remove Element
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
(배열에서 주어진 val과 같은 값을 모두 삭제, 배열 그 자체에서 삭제하고 배열의 길이를 반환할 것)
💡 풀이
var removeElement = function(nums, val) {
for(let i = 0; i < nums.length; i++) {
if(nums[i] === val) {
nums.splice(i,1);
i --;
}
}
return nums.length;
};
💡 다른 풀이
var removeElement = function(nums, val) {
let idx = 0;
for(let i = 0; i < nums.length; i++) {
if(nums[i] !== val) {
nums[idx] = nums[i];
idx++;
}
}
return idx;
};빼는 것이 아니라 앞으로 값을 옮겨넣기
속도가 훨씬 빨라진다
2. Remove Duplicates from Sorted Array
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
(주어진 배열 안에서 중복값을 삭제하고, 크기는 그대로 유지할 것. 최종 배열의 길이 반환)
💡 풀이
var removeDuplicates = function(nums) {
for(let i = 0; i < nums.length; i++) {
if(nums[i] === nums[i-1]) {
nums.splice(i,1);
i--;
}
}
return nums.length;
};
💡 다른 풀이
var removeDuplicates = function(nums) {
for(let i=0; i < nums.length; i++){
if(nums[i] !== nums[i+1]){
nums[index++] = nums[i];
}
}
return index;
};두 값이 달라지는 부분에서 다음 값을 추출해, 배열 앞의 값을 바꿔나가는 풀이
기발하고 속도도 빠르다.
📌Searching For Items in an array
1. Check If N and Its Double Exist
Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M).
More formally check if there exists two indices i and j such that :
- i != j
- 0 <= i, j < arr.length
- arr[i] == 2 * arr[j]
💡 풀이
var checkIfExist = function(arr) {
for(let i = 0; i < arr.length; i++) {
let num = arr.shift();
if(arr.includes(num * 2)) return true;
arr.push(num);
}
return false;
};
2. Valid Mountain Array
Given an array of integers arr, return true if and only if it is a valid mountain array.
Recall that arr is a mountain array if and only if:
- arr.length >= 3
- There exists some i with 0 < i < arr.length - 1 such that:
- arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
- arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
💡 풀이
var validMountainArray = function(arr) {
let top = 0;
for(let i = 0; i < arr.length; i++) {
if(arr[i] === arr[i+1]) return false;
else if(arr[i] > arr[i+1]) {
top = i;
break;
}
}
if(top === 0 || top === arr.length) return false;
for(let j = top; j < arr.length; j++) {
if(arr[j] <= arr[j+1]) return false;
}
return true;
};
📌In Place Operations
새로운 배열을 생성하지 않고, 배열 내부에서 값 구하기
1. Replace Elements with Greatest Element on Right Side
Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.
After doing so, return the array.
💡 풀이
var replaceElements = function(arr) {
for(let i = 0; i < arr.length; i++) {
if(i === arr.length-1) arr[i] = -1;
else arr[i] = Math.max(...arr.slice(i+1))
}
return arr;
};
너~무 느리게 나와서 다른 풀이를 참고해서 전체적으로 고쳤다.
앞에서부터 다음의 모든 값의 최대값을 업데이트하지 않고, 뒤에서부터 최대값을 업데이트했다.
맨 뒤의 값을 -1로 하고, 원 값을 보관해서 하나씩 비교해서 더 큰 값을 넣어주면 된다.
💡 다른 풀이
var replaceElements = function(arr) {
let max = -1;
for(let i = arr.length-1; i >= 0; i--) {
let cur = arr[i];
arr[i] = max;
if(max < cur) max = cur;
}
return arr;
};
2. Move Zeroes
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
(0인 요소를 뒤로 옮기기)
💡 풀이
var moveZeroes = function(nums) {
let cnt = 0;
let index = 0;
while(cnt < nums.length) {
if(!nums[index]) nums.push(...nums.splice(index,1))
else index++;
cnt++;
}
return nums;
};
💡 다른 풀이
var moveZeroes = function(nums) {
let position = 0;
for(let i = 0; i < nums.length; i++) {
if(nums[i]) {
nums[position] = nums[i];
position++
}
}
for(let j = position; j < nums.length; j++) {
nums[j] = 0;
}
return nums;
};1차 풀이처럼 값을 빼서 옮기는 것이 아니라, 아예 0이 아닌 값을 position으로 세어가며 해당 인덱스에 값 넣기
3. Sort Array By Parity
Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.
Return any array that satisfies this condition.
(짝수값을 앞으로 옮기기)
💡 풀이
var sortArrayByParity = function(nums) {
let idx = 0;
for(let i = 0; i < nums.length; i++) {
if(!(nums[i]%2)) {
let temp = nums[i];
nums[i] = nums[idx];
nums[idx] = temp;
idx++;
}
}
return nums;
};짝수인 값을 맨 앞부터 트레이드하기
📌Conclusiog
1. Height Checker
A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in non-decreasing order by height. Let this ordering be represented by the integer array expected where expected[i] is the expected height of the ith student in line.
You are given an integer array heights representing the current order that the students are standing in. Each heights[i] is the height of the ith student in line (0-indexed).
Return the number of indices where heights[i] != expected[i].
💡 풀이
var heightChecker = function(heights) {
let changed = [...heights].sort((a,b) => a - b);
let answer = 0
let idx = 0;
for(let i = 0; i < heights.length; i++) {
if(heights[i] !== changed[i]) answer ++;
}
return answer;
};
2. Third Maximum Number
Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.
💡 풀이
var thirdMax = function(nums) {
nums.sort((a,b) => b - a);
let cnt = 1;
for(let i = 1; i < nums.length; i++) {
if(nums[i] !== nums[i-1]) cnt++;
if(cnt === 3) return nums[i]
}
return nums[0];
};
💡 다른 풀이
var thirdMax = function(nums) {
nums = [...new Set(nums)]
nums.sort((a,b) => b - a)
return nums[2] !== undefined ? nums[2] : nums[0];
};set으로 중복을 없애고 값 도출함. 속도 훨씬 빠르다.
3. Find All Numbers Disappeared in an Array
Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.
(배열의 크기만큼 (1~arr.length)의 범위 내에 숫자 중에 없는 숫자를 담은 배열 반환)
💡 풀이
var findDisappearedNumbers = function(nums) {
let answer = [];
let cnt = 1;
while(cnt <= nums.length) {
if(!(nums.includes(cnt))) answer.push(cnt);
cnt++;
}
return answer;
};따로 새로운 배열을 만들어서 풀었는데 속도가 엄청나게 느렸다.
제출할 때마다 속도가 다르게 나왔는데, 아예 그래프를 벗어나기까지 했음...
💡 다른 풀이
var findDisappearedNumbers = function(nums) {
let boolean = new Array(nums.length+1).fill(false);
let answer = [];
let cnt = 1;
for(let i = 0; i < nums.length; i++) {
boolean[nums[i]] = true;
}
for(let j = 1; j <= nums.length; j++ ) {
if(boolean[j] === false) answer.push(j);
}
return answer;
};js 전용 메서드를 사용하면 속도가 느려지는 것 같다.
간단하진 않지만 array.includes() 대신 for문으로 검색한 후, 존재 여부를 따로 배열로 표시해서 값을 도출했다.
역시 속도가 훨씬 빨랐다.
'Coding test' 카테고리의 다른 글
| [프로그래머스] 뉴스 클러스터링 (Lv 2) - javascript (0) | 2022.09.15 |
|---|---|
| [Leetcode] 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers - javascript (0) | 2022.07.06 |
| [프로그래머스] 행렬 테두리 회전하기 (Lv 2) - javascript (0) | 2022.06.29 |
| [프로그래머스] 거리두기 확인하기 (Lv 2) - javascript (0) | 2022.06.29 |
| [프로그래머스] 수식 최대화 (Lv 2) - javascript (0) | 2022.06.28 |