leetcode Remove Duplicates from Sorted Array Solution 문제풀기

18 Jan 2021

#[leetcode][📣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 문제도 도전해야겠다!

NestJS 시리즈 - 이거는 알고 시작하자.

15 Jan 2021

1. NestJS 블로그 만들기 -이거는 알고 시작하자.

NestJS를 시작하기전 이거만큼은 알고 시작하자!!

🚨🚨🚨 본 포스트와 이후 nestjs 시리즈에서는 Javascript, Typescript 를 배우기 위한 내용은 다루지 않습니다. 🚨🚨🚨

📣Prerequisites

1. Javascript & Typescript

Javascript 는 FrontEnd 를 공부중이시거나 NodeJS 를 다루어 보신분이라면 알고 계실거라고 생각합니다! 다만 Typescript 까지 해야하느냐?? 라고 물으신다면

NestJS 의 주요 핵심중 하나는 의존성주입(Defendency Injection) 입니다.

의존성주입이 무엇인지 먼저 알아보죠.

2. 의존성주입 (Dependency Injection)

의존성 주입은 제어의역전(Inversion of Control) 의 기술중 하나입니다.

🙄🙄🙄

의존성 주입이란 말을 처음 들은 여러분의 표정이 상상이 갑니다.

저도 그랬거든요 ^^..

간단하게 먼저 말하자면

제어의역전 : “내가 대신 제어해줄게”
의존성주입 : “니가 정의한 코드(클래스, 변수 등등)를”

예를 들어보겠습니다.

NestJS 에서는 생성자를 통해 의존성을 주입할 수 있습니다.

import { Controller, Get, Post, Body } from "@nestjs/common";
import { CreateCatDto } from "./dto/create-cat.dto";
import { CatsService } from "./cats.service";
import { Cat } from "./interfaces/cat.interface";

@Controller("cats")
export class CatsController {
  constructor(private catsService: CatsService) {}

  @Post()
  async create(@Body() createCatDto: CreateCatDto) {
    this.catsService.create(createCatDto);
  }

  @Get()
  async findAll(): Promise<Cat[]> {
    return this.catsService.findAll();
  }
}

위의 코드에서

  constructor(private catsService: CatsService) {}

여기에 해당하는 코드를 보시면 생성자에서 catService 의 타입만 지정했습니다. 그럼에도 불구하고

  @Post()
  async create(@Body() createCatDto: CreateCatDto) {
    this.catsService.create(createCatDto);

여기서 catService 의 create 메소드를 호출하고 있습니다.

이는 NestJS 가 “오 catsService 는 CatsService 타입이네? 내가 직접 찾아서 할당해줘야겠다!!” 라는 행동을 하게 됩니다. 이후 이 클래스의 생성, 소멸 주기를 몰라도 그냥 미친듯이 사용 가능합니다. NestJS 가 해당 객체를 관리해줄거거든요. 이미 내 손을 떠난 문제에요!!

“무슨 말인지 모르겠어.. 그냥 의존성주입이고 나발이고 내가 다 만들어서 개발할래!!” 라고 생각하신다면… 프레임워크를 사용 안하고 모든 것을 직접 개발하셔도 됩니다. 다만 프레임워크의 장점을 버리는 것이 더 큰 고통을 안겨줄지도 몰라요 😭😭😭

자 위에서 보신것과 같이 NestJS가 의존성주입을 사용하기 위해서 우리는 타입을 지정해주었습니다. Nodejs 환경에서 Javascript 는 타입을 명시할 수 없습니다. 따라서 Typescript 를 사용하게됩니다.

이제 Typescript 를 꼭 해야합니까?? 의 답변을 이해 하시겠죠??

3. HTTP

HTTP에 대해서 완전 자세하게 전문가까지의 지식이 필요한 것은 아닙니다. (저도 전문가는 아닙니다.) HTTP 메소드가 무엇인지. URL이 무엇인지. HTTP 포트가 무엇인지 !! 간략하게나마 아신다면 RESTful API 를 작성하시는데 큰 도움이 되겠습니다.

4. Database

데이터 제공을 할거잖아요?? 간단한 SQL 문법 정도는 집고 넘어갑시다. !! NoSQL 이 떠오른다고는 하지만 SQL 의 모든 것을 대체할거라고 생각하시면 안됩니다. !! MYSQL !! Postgresql !!!! 원하는 데이터베이스를 선택해서 해봅시다!!

위의 내용을 간략하게 라도 아신다면 이후 NestJS 를 배우시는데 큰 도움이 될 거에요!!

Javascript 를 모르신다면

노마드코더님, 드림코딩 엘리님, 또 영어를 잘하시면 Academind 님의 영상 등, 유튜브, Udemy 에 수많은 강의들이 있으니 꼭 들어보시길 바랍니다.

다음에는 CRUD 기능 실습을 통해 NestJS 가 이런거구나 라는 것을 알아보겠습니다.!!

leetcode 16 3sum closet 문제풀기

15 Jan 2021

#[leetcode][16] 3sum closet 문제풀기!

문제풀러가기✈

👓 문제 요약

이번에도 숫자를 엄청 줄게!! 숫자 3개를 뽑아서 그 숫자들의 합이 내가 원하는 숫자랑 가장 가까워지는 값을 찾아줘!!

자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기

🔑 문제 풀이v

이번에도 숫자 세개를 뽑아서… 더해서 … 원하는 숫자와 얼마나 가까운지 체크하면 된다! 다만 이번에도 3개 전부 완전탐색을 돌려버리게 된다면 타임아웃이 뜨지 않을까?

저번과 마찬가지로 투포인터 접근법으로 풀었다. 이전 문제를 풀었다면 별로 어렵지 않을 것이다!

그래서 제가 어떻게 풀었냐면 !!

저번과 마찬가지로 정렬 후 selected, left, right 숫자를 선정합니다.

select : 가장 작은 숫자
left : selected + 1
right : 가장 큰 숫자

이후 알고리즘은

합을 계산한 후 원하는 숫자와의 거리를 구한후,
이전에 구한 원하는 숫자와의 거리의 최솟값과 비교한후
더 작다면 이번에 계산한 값과, 거리를 저장!

가장 중요한 left 와 right 의 인덱스를 어떻게 변화시킬거냐.. 는 다음과 같습니다.

원하는 숫자가 방금 구한 합보다 작다면 right 인덱스를 1 줄여주고

왜냐면 방금 구한 합보다 작아져야 원하는 숫자에 더 가까워지기 때문 !!
반대의 경우 left 인덱스를 1 늘립니다.

계싼은 컴퓨터에게 맡겨욥!!

🥽 소스코드 및 소스해석

var threeSumClosest = function (nums, target) {
  let answer = 100000;
  let minDist = 1000000;
  nums.sort((a, b) => a - b);
  let selected = 0;
  while (selected < nums.length - 2) {
    let left = selected + 1;
    let right = nums.length - 1;
    while (left < right) {
      let sum = nums[selected] + nums[right] + nums[left];
      if (minDist >= Math.abs(sum - target)) {
        minDist = Math.abs(sum - target);
        answer = sum;
      }
      if (target - sum < 0) {
        right--;
      } else {
        left++;
      }
    }
    selected++;
  }
  return answer;
};

🔨 문제 후기

이전 문제를 풀었기 때문에 쉽게 풀 수 있었다. 이 알고리즘으로는 시간복잡도 O(n^2) 에 풀 수 있다. 혹시 O(nlgn) 방법으로도 가능할까 싶어서 생각하고 찾아봤는데.. 답은 나오지 않았다. 뭔가 있을거 같은데 …

Elasticsearch 폴더에는 뭐가 있을까??

14 Jan 2021

#[🌎elasticsearch] Elasticsearch 폴더에는 뭐가 있을까??

🧡 ElasitcSearch 폴더 구조

쉬어가는 느낌으로 ElasticSearch 의 directory 구조를 한번 살펴보도록 하겠습니다.

ElasticSearch의 폴더로 한번 가보죠!

folder구조

저는 elk라는 폴더에 elasticsearch 와 관련된 폴더들을 모아두었습니다.

📒Bin 폴더

bin 폴더 안에는 elasticsearch-cli, elasticsearch-sql-cli, elasicsearch-plugin 등등

elasticsearch 기능의 핵심적인 스크립트 들이 있습니다.

건들지마세용 …..

x-pack 부분은 elasticsearch 의 플러그인(보안, 알림, 모니터링, 보고, 그래프 등)들을 버전에 맞게 묶은 패키지라고 생각하시면 됩니다.!! elasticsearch를 알리게 만든 기능들의 집합체라고 생각합시다.!!

📒Config 폴더

elasticsearch.yml

이 파일에서 elasticsearch 의 전반적인 환경을 설정할 수 있습니다. 메모장이나 에디터로 켜시면

# ---------------------------------- Cluster -----------------------------------
#
# Use a descriptive name for your cluster:
#
#cluster.name: my-application
#

cluster.name 옆에 #을 지우시고 cluster.name : <원하는 이름=""> 을 쓰시면 클러스터 이름을 설정할 수 있습니다.

클러스터와 노드에 대한 내용은 이후 포스트에서 자세하게 다루겠습니다.

그 밑에 node, paths, memory, network, Discovery 가 있습니다.

paths 에서는 데이터, 로그가 저장되는 위치를 지정할 수 있습니다.
memory 에서는 다른 자바프로그램이 엘라스틱 서치의 힙 영역의 메모리를 사용하지 못하도록 lock 을 걸 수 있습니다.

memory 사용량 제한은 jvm.option 파일에서 힙사이즈를 조정함으로서 디테일하게 설정가능합니다.
network 에서는 어떤 ip의 어떤 port 번호로 elasticsearch에 접근 할 지 설정가능합니다.
discovery 에서는 elasticsearch 에 얼마나 많은 인스턴스들이 연결 되는지 설정가능합니다.

jvm.options

이 파일에서는 elasticsearch 에 허용해줄 메모리 크기를 설정해줄 수 있습니다. 기본은 1기가바이트 입니다. 메모리 외의 내용에 대해서는 전문가가 아니면 건들지 맙시다 …

log4j2.properties

여기는 elasticsearch 의 로그 관련 파일로, log4j2는 java 의 가장 강력한 logging 프레임워크중 하나입니다.

📒modules 폴더

여기는 완전히 elasticsearch 의 기능에 도움을 주는 built-in module 들이 모여있는 곳입니다. 많은 x-pack 폴더들이 보이시죠~ ?

📒plugins 폴더

이 폴더는 우리가 elasticsearch 에 custom 플러그인을 추가할 때 사용하는 폴더입니다.

leetcodd 15 3sum 문제풀기

14 Jan 2021

#[leetcode][15] 3sum 문제풀기!

문제풀러가기✈

👓 문제 요약

숫자를 엄청 줄게!! 숫자 3개를 뽑아서 그 숫자들의 합이 0 이 되는 부분집합좀 찾아줘!

자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기

🔑 문제 풀이

숫자 세개를 뽑아서… 0 을 만드는지 확인하면 된다!. 다만 3개 전부 완전탐색을 돌려버리게 된다면 타임아웃이 뜨지 않을까? 주어진 조건에서 숫자의 개수는 최대 3천개라 했으니 아마 타임아웃이 뜰거 같다.

그래서 제가 어떻게 풀었냐면 !!

일단 숫자 세개의 합이 0이 되어야하니, 숫자들을 정렬하고 최저의 수를 선택하고 이 숫자와 다른 숫자 2개를 선택했을 때 0이 되는 경우를 구했습니다. !!!!! 빠밤!!

저희는 최저의 수를 선택했기 때문에 해당 숫자보다 오른쪽에 있는 수는 무조건 선택된 숫자보다 크다는 겁니다.!!

그리고 숫자 두개를 정할껀데,

하나는 최저 숫자보다 한 단계 크거나 같은수
다른 하나는 가장 큰 수

를 선택해서 선택지의 폭을 줄여나가는 겁니다.

만약 세 개를 더했는데 0보다 크다? 그러면 가장 큰 수를 가르키는 포인트를 한 단계 낮은 숫자로 옮깁니다. 만약 세 개를 더했는데 0보다 작다? 그러면 선택된 최저의 수를 가지고는 0을 만들 수 없습니다.

선택된 숫자를 제외하고 가장 작은 수와 가장 큰 수를 더했기 때문

만약 세개를 더했는데 0이랑 같다? 정답에 추가합니다.

자자자자 요약해줄게요 !

최저의 수 선택 - selected 라 하겠습니다.
최저의 수와 같은 또는 한 단계 큰 수를 가르키는 포인트 - 그 숫자를 left라 하겠습니다.
최대의 수를 가르키는 포인트 - 그 숫자를 right라 하겠습니다.
selected + left + right === 0 -> 답에 추가!
selected + left + right < 0 -> selected 의 숫자로는 더이상 0을 만들 수가 없음!
selected + left + right > 0 -> right 의 숫자를 한 단계 낮춰줌 !!

이 것을 반복하시면 됩니다. 반복은 컴퓨터가 하기 때문에 마음껏 돌려주세요!

다만 중복을 피하기 위해 포인트를 옮길 때는 같은 수는 전부 지나쳐주세요!!

🥽 소스코드 및 소스해석

var threeSum = function (nums) {
  let answer = [];
  let selected = 0;
  let left = selected + 1;
  let right = nums.length - 1;
  if (nums.length < 3) return answer;
  nums.sort((a, b) => a - b);
  while (nums[selected] <= 0 && left !== right) {
    if (nums[selected] + nums[left] + nums[right] === 0) {
      answer.push([nums[selected], nums[left], nums[right]]);
      while (nums[right] === nums[right - 1]) right--;
      while (left + 1 < nums.length && nums[left] === nums[left + 1]) left++;
      right--;
      left++;
    } else if (nums[selected] + nums[left] + nums[right] < 0) {
      while (left + 1 < nums.length && nums[left] === nums[left + 1]) left++;
      left++;
    } else {
      while (nums[right] === nums[right - 1]) right--;
      right--;
    }
    if (right <= left) {
      [selected, left, right] = setValue(selected, left, right, nums);
    }
  }
  return answer;
};
const setValue = (selected, left, right, nums) => {
  if (nums[selected] === nums[selected + 1]) {
    while (nums[selected] === nums[selected + 1]) {
      selected++;
    }
  }
  selected++;
  left = selected + 1;
  right = nums.length - 1;
  return [selected, left, right];
};

🔨 문제 후기

자잘한 조건 때문에 오래걸린 문제!!

나는 정말 숫자에 약한 것 같다 ㅜㅜ 다들 화이팅!!

코드를 깔끔하게 정리하는 법좀 배워야할 듯 싶다.

릿코드 상당히 괜찮은 사이트 같습니다!

Older Newer

영원 웹 개발과 일상

leetcode Remove Duplicates from Sorted Array Solution 문제풀기

👓 문제 요약

🔑 문제 풀이

그래서 제가 어떻게 풀었냐면 !!

🥽 소스코드 및 소스해석

🔨 문제 후기

NestJS 시리즈 - 이거는 알고 시작하자.

1. NestJS 블로그 만들기 -이거는 알고 시작하자.

📣Prerequisites

1. Javascript & Typescript

2. 의존성주입 (Dependency Injection)

3. HTTP

4. Database

leetcode 16 3sum closet 문제풀기

👓 문제 요약

🔑 문제 풀이v

그래서 제가 어떻게 풀었냐면 !!

🥽 소스코드 및 소스해석

🔨 문제 후기

Elasticsearch 폴더에는 뭐가 있을까??

🧡 ElasitcSearch 폴더 구조

📒Bin 폴더

📒Config 폴더

elasticsearch.yml

jvm.options

log4j2.properties

📒modules 폴더

📒plugins 폴더

leetcodd 15 3sum 문제풀기

👓 문제 요약

🔑 문제 풀이

그래서 제가 어떻게 풀었냐면 !!

🥽 소스코드 및 소스해석

🔨 문제 후기