[๐Ÿ“ฃtop interview question] Remove Duplicates from Sorted Array Solution ๋ฌธ์ œํ’€๊ธฐ!

3554 ๋‹จ์–ด leetcodealgorithmalgorithm


๐Ÿ‘“ ๋ฌธ์ œ ์š”์•ฝ

์ •๋ ฌ๋œ ๋ฐฐ์—ด์„ ํ•˜๋‚˜ ์ค„๊ฒŒ!

์ค‘๋ณต๋œ ์ˆซ์ž ์—†๋Š” ๋ฐฐ์—ด์„ ๊ฐ–๊ฒŒ ํ•ด์ค˜!!

์ž์„ธํ•œ ๋ฌธ์ œ ์„ค๋ช…๊ณผ ๋ฆฟ์ฝ”๋“œ ํ™ˆํŽ˜์ด์ง€ ์ฐธ๊ณ . ๋ฌธ์ œํ’€๋Ÿฌ๊ฐ€๊ธฐ

๐Ÿ”‘ ๋ฌธ์ œ ํ’€์ด

๋ฌธ์ œ๋ฅผ ์ž˜ ์ฝ์–ด๋ณด๋ฉด, ๋‹ค๋ฅธ ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด์„œ ์‚ฌ์šฉํ•˜์ง€ ๋ง๊ณ  ์ถ”๊ฐ€ ๋ฉ”๋ชจ๋ฆฌ๋Š” ํ•˜๋‚˜๋งŒ ์‚ฌ์šฉํ•˜๋ผ๊ณ  ๋ช…์‹œ๋˜์–ด์žˆ๋‹ค!.

์ด ๋ฌธ์ œ๋Š” ์ฑ„์ ํ•  ๋•Œ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ํ•˜๊ธฐ ๋•Œ๋ฌธ์— !! ๋‹ค๋ฅธ ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด์„œ ์‚ฌ์šฉํ•˜์ง€ ๋ง๋ผ๊ณ  ํ•œ๋‹ค. ๋˜ํ•œ
๋‹จ ํ•˜๋‚˜์˜ ์ถ”๊ฐ€ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•˜๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค!

// 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 ๋ฌธ์ œ๋„ ๋„์ „ํ•ด์•ผ๊ฒ ๋‹ค!

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ