알고리즘 문제 풀어보기

가장 큰 수

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

풀이 코드

function solution(numbers) {
    const answer = numbers
      .map((number) => number.toString())
      .sort((a, b) => b + a - (a + b))
      .join("");
  
    return answer[0] === "0" ? "0" : answer;
  }

풀이 과정

• 모든 숫자를 스트링으로 변환 후 해당 수와 다음 수를 이어 붙였을 때 더 큰 순서대로 정렬 해주고 이어 붙여주면 된다. 혹시 0만 있는 케이스가 있을수도 있으므로 0에 대한 처리를 해줫다.

기술 면접 문제 풀어보기

13.BigO에 대해 설명해주세요.

BigO

• 대략적으로 숫자를 세는 공식적인 표현 => 입력된 내용이 늘어날수록 알고리즘에 실행 시간이 어떻게 변하는지 설명하는 공식적인 방식.

BigO의 시간 복잡도

• 입력이 커질수록 알고리즘의 실행 속도가 어떻게 바뀌는지 표현.

1-1) O(1) : 상수

/*
   n의 값이 늘어나도 실행 되는 시간에는 아무런 영향을 받지 않는다. 
   시간복잡도 O(1)
*/
function addSec(n) {
	return n * (n + 1 ) / 2;
}

• O(1) 상수 : n(입력값)이 커져도 실행 시간에 아무런 영향도 받지 않을 경우(항상 상수) 나타내는 표현

1-2) O(n) : 선형

/* 
  실행되는 시간이 n의 값이 늘어나는것과 비례하게 1:1비율로, 선형으로 늘어난다.
  시간복잡도 O(n) 
*/
function addFirst(n) {
	var total = 0;
	for (let i=0; i<=n; i++) { 
		total +=i;
	}
	return total
}

• O(n) 선형 : n(입력 값)이 커질수록 실행 시간도 같이 늘어난다.

1-3) O(n^2)

/*
  중첩 루프(for문)을 가진다. O(n) 연산 안에 O(n)을 가지고 있으면 O(n^2)이 된다.
  시간복잡도 O(n^2)
*/
function bigO(n) {
	for (let i=0; i < n; i++) {
		for (let j=0; j < n; j++) {
			console.log(i, j);
		}
	}
}

• O(n^2) : 실행 시간이 n의 제곱일 경우

1-4) O(log n)

/*
  입력의 크기에 따라 처리 시간이 증가하는 정렬 알고리즘에 사용 된다.
  시간 복잡도 O(log n)
*/
function bigO(n) {
    for (let i = 2; i <= n; i*2) {
        console.log(i);
    }
}

BigO의 공간 복잡도

• 입력이 커질수록 알고리즘이 얼마나 많은 공간을 차지하는지 표현. => 알고리즘 자체가 필요로 하는 공간을 의미.

기본 규칙

• Boolean, number, undefined, null은 불변 공간으로 O(1)를 갖는다.
• reference타입, 배열, 객체 문자열은 O(n) 공간이 필요하다.

2-1) O(1) : 상수

// 입려시 이미 배열의 길이가 정해져있어 변하는것이 아니기 때문에 공간 복잡도 O(1)를 갖는다.
function sum(arr) {
	let total = 0;
	for (let i=0; i < arr.length; i++) {
		total += arr[i];
	}
}

2-2) O(n) : 선형

// arr길이 만큼 newArr의 공간이 생기기 때문에 공간 복잡도 O(n)을 갖는다.
function double(arr) {
	let newArr = [];
	for (let i=0; i < arr.length; i++) {
		newArr.push([i]);
	}
}

최종 프로젝트

이전에 짯던 기본 구조에서 패킷 사이즈와 패킷 아이디를 받아 전체 패킷 크기를 구하는 부분에 문제가 있는 것 같아 구조를 뜯어고쳣다.
proto파일을 받아오는 loadProto와 비슷한 구조로 assets폴더 안에 있는 json파일을 읽을 수 있는 loadAssets.js를 만들었는데 loadAsset의 gameAssets를 받아서 사용하는 함수 getJobById가 제대로 작동하지 않는다.

• 문제점 : enterhandler에서 loadAssets를 이용해 jobid를 받아와 그 id에 해당하는 스텟을 createUser를 통해 user에 넣으려하는데 loadAssets에서 jobid를 받아오는 getJobById()가 작동을 안함.(실행 시 undefined가 뜸.)

어떤 부분이 잘못된것인지 잘 모르겠어서 내일 조금 더 건드려본 다음에 튜터님께 질문해봐야겠다.
아마 이부분만 잘 처리되면 게임 실행에서는 문제가 없을 것 같다.