[📣top interview question] Remove Duplicates from Sorted Array Solution 문제풀기!
👓 문제 요약
정렬된 배열을 하나 줄게!
중복된 숫자 없는 배열을 갖게 해줘!!
자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기
🔑 문제 풀이
문제를 잘 읽어보면, 다른 배열을 만들어서 사용하지 말고 추가 메모리는 하나만 사용하라고 명시되어있다!.
이 문제는 채점할 때 다음과 같이 하기 때문에 !! 다른 배열을 만들어서 사용하지 말라고 한다. 또한 단 하나의 추가 메모리를 사용하라고 합니다!
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}그래서 제가 어떻게 풀었냐면 !!
들어오는 인풋 배열에서 모든 것을 해결했습니다.!
c++ 의 vector 와 같이 특정 원소를 제거하는 연산은 O(n) 의 시간이 들게 됩니다. 배열 구조 특성상 메모리가 이어져야 하기 때문에 뒤에서 앞으로 이어준 후 새로운 배열을 반환하기 때문이라고 합니다. 만약 제거해야하는 원소가 매우 많아진다면 시간적 여유가 없어지겠죠??
다만 리스트 관련 자료구조로 특정 원소를 삭제한다면 연산은 O(1) 이 됩니다!
문제는 어렵지 않습니다. !! 손풀기로 갑시다!
🥽 소스코드 및 소스해석
var removeDuplicates = function (nums) {
let nowIndex = 0;
for (let compareIndex = 1; compareIndex <= nums.length; compareIndex++) {
if (nums[nowIndex] !== nums[compareIndex]) {
nowIndex++;
nums[nowIndex] = nums[compareIndex];
}
}
return nowIndex;
};🔨 문제 후기
취업관련 코딩테스트 준비를 하다가 찾은 문제집 !! 괜찮은 것 같다!!
하루에 3시간씩 알고리즘 관련 문제를 푸는데, 시간이 남으면 Hard 문제도 도전해야겠다!
Series
Algorithms
이 글은 "Algorithms" 시리즈의 18번째 기록입니다.
- 01#[프로그래머스][연습문제] 3 x N 타일링 풀이
- 02[프로그래머스][2019 kakao] 블록게임 해설
- 03[프로그래머스][2019 kakao] 길 찾기 게임 문제 해설
- 04[프로그래머스][2019 kakao] 무지의 먹방 라이브 문제 해설
- 05[프로그래머스][2019 kakao] 후보키 문제 해설
- 06[프로그래머스✈][2020 kakao] 자물쇠와 열쇠 문제 풀이
- 07[프로그래머스][2020 kakao] 기둥과 보 설치 문제 해설
- 08[프로그래머스✈][2020 kakao] 가사 검색 문제 풀이
- 09[백준🔉][16234] 인구이동 문제 해설
- 10[프로그래머스✈][2019 kakao 겨울 인턴십] 불량 사용자 문제 해설
- 11[프로그래머스✈][2020 kakao] 동굴 탐험
- 12[백준🔉][14501] 퇴사 문제 해설
- 13[프로그래머스✈][2017 카카오코드] 4단 고음 해설
- 14[프로그래머스✈][2019 kakao 겨울 인턴쉽] 징검다리 건너기 해설
- 15[프로그래머스✈][연습문제] 섬 연결하기 풀이
- 16[leetcode][15] 3sum 문제풀기!
- 17[leetcode][16] 3sum closet 문제풀기!
- 18[📣top interview question] Remove Duplicates from Sorted Array Solution 문제풀기!
- 19[📣top interview question] Best Time to Buy and Sell Stock II 문제풀기!
- 20[leetcode][30] Substring with Concatenation of All Words 문제풀기!
- 21[leetcode][31] Next Permutation 문제풀기!
- 22[leetcode][32] Longest Valid Parentheses 문제풀기
- 23[leetcode][40] Combination Sum II 문제풀기!
- 24[leetcode][42] Trapping Rain Water 문제풀기!
- 25[leetcode][43] Multiply Strings 문제풀기!
- 26[leetcode][44] Wildcard Matching 문제풀기!
- 27[leetcode][45] Jump Game II 문제풀기!