[LeetCode 코테 풀기] 1920. Build Array from Permutation

라피신을 끝내고 다시 코딩 독학을 하기 위해 돌아왔다.

본래 백준 코테를 조금씩 풀고 있었지만, LeetCode로 옮겨왔다.

 

해외 취업이나 그런 이유는 아니고, 그냥 Discuss의 위치가 눈에 딱 보이는 곳에 있는게 좋았다.

그리고 어차피 초보자인 나에게는 백준을 보든, LeetCode를 보든, 프로그래머스를 보든 다 의미없다.

 

알고리즘을 잘 모르니까 결국

문제에 대한 해설지(= 능력있는 개발자 분들이 잘 짠 코드)를 보며

어떤 코드가 더 효율적이고 좋은 코드인지 처음부터 맨땅에서 배워야 하기 때문에

단순히 전국 보다는 전세계적인 사람들이 모인 곳에 더 코드를 잘 짜는 능력자 분들이 많이 계실 것 같아서 선택했다.

 

 

공부하는 방법은 아래 선생님의 글을 참조하자.

https://www.fwantastic.com/2020/12/faang-1-leetcode.html

FAANG 취업 도전기 - 1. 코딩 테스트 준비 & leetcode를 효율적으로 사용하는 방법

 

프리미엄을 결제한게 아니라서 문제에 대해 제한이 있지만

무료 문제를 풀어도 배울 점이 많으니까 상관없다.

---

1920. Build Array from Permutation

문제 해석:

zero-based permutation인 nums가 주어졌을 때, ans[i] = nums[nums[i]]인 배열 ans 빌드하세요. (0<= i <= nums.length)

이때, 배열 ans의 길이 nums와 같습니다. 

* zero-based permutation인 nums는 0부터 nums.length -1 까지인 distinct integers 입니다.

 

참고. 알고리즘에 풀이로 채택한 언어는 JavaScript이다.

 

문제출처 : Build Array from Permutation - LeetCode

Build Array from Permutation - LeetCode

---

풀이:

일단 문제를 풀기에 앞서 영문 해석에서 막혔다. 번역기를 이용하자.

 

순열은 서로 다른 n에게 r개를 뽑아 순서에 따라 일렬로 배열하는 방법이다.

수학적인 순열은 이런 느낌이다.

숫자 [1, 2, 3, 4]가 있다고 가정하자.

서로 다른 숫자 4개(= n)에서 2개(=r개)를 뽑아 순서에 따라 일렬로 배열한다고 하면

[1, 2], [1, 3], [1, 4], [2, 1] 등등 여러 가지 순열이 나올 수 있고,

이때 순열의 수를 구하는 공식은 n(n-1)(n-2)...(n-r+1)이기 때문에 4x3 = 12개가 된다.

 

어쨌든 문제로 다시 돌아와서 최종적으로 구해야하는 배열 ans는 nums[nums[i]]라고 했으니

ans[0]은 nums[nums[0]]이 될 것이고 나머지도 아래와 비슷한 형태일 것 같다.

완전히는 아니더라도 대충 문제를 이해 했으니 풀어보자.

* 본 글은 언어를 전혀 모르는 채로 맨 땅에 헤딩하며 공부하는게 컨셉(?)이기 때문에, 문법부터 하나씩 차근차근 필기 했다.

 

1) JS 변수 선언

JS는 느슨한 타입(loosely typed)의 동적 언어라서 C언어처럼 변수 타입을 명시적으로 지정하지 않는다.

타입에 대한 자세한 설명은 아래 글을 참고해보자.

http://www.tcpschool.com/javascript/js_datatype_basic

코딩교육 티씨피스쿨

 

변수 선언은 아래와 같이 var 키워드로 선언을 하는데

var num = 123;

꼭 var 키워드만 사용하는건 아니다. ES6부터는 var 뿐만 아니라 let, const 키워드도 있다고 한다.

 

참고자료 : https://developer.mozilla.org/ko/docs/Web/JavaScript/Guide/Grammar_and_types

문법과 자료형 - JavaScript | MDN

 

참고자료 : https://curryyou.tistory.com/192

[자바스크립트] 변수 선언 방식 차이: var / let / const

 

2) 배열 생성

이제 문제에서 주어진 배열을 만들기 위해서 배열 생성을 알아보자.

배열은 아래와 같이 생성하고 대입하면 된다.

let ans = []; // 배열 선언

ans[0] = nums[nums[0]]; // 배열 요소에 값 대입
ans[1] = nums[nums[1]];
ans[2] = nums[nums[2]];

 

3) 함수

문제를 풀기 위해 코드를 보니 var buildArray = function(nums) { } 로 되어 있었다.

이게 뭔가 싶었는데, 아래 글을 읽고 보니 nums라는 인자를 가진 익명으로 선언된 함수였다.

https://developer.mozilla.org/ko/docs/Web/JavaScript/Guide/Functions

함수 - JavaScript | MDN

 

4) 반복문

nums.length가 얼마인지 모르는데 ans[0]부터 ans[1], ans[2], ... 하면서 계속 대입할수도 없고 그래서

반복문을 배우기로 했다.

https://developer.mozilla.org/ko/docs/Web/JavaScript/Guide/Loops_and_iteration

루프와 반복 - JavaScript | MDN

위의 내용에 의하면 아래와 같이 코드를 쓸 수 있지 않을까 싶다.

for(let i = 0; i < nums.length; i++) {
	ans[i] = nums[nums[i]];
}

 

이제 필요한 문법은 다 대충 훑어본 것 같다.

문제에 대한 해답을 쓸 수 있을 것 같다.

---

제출한 답안 :

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var buildArray = function(nums) {
    let ans = [];
    for(let i = 0; i < nums.length; i++)
        ans[i] = nums[nums[i]];
    return (ans);
};

런타임 106ms가 나왔고, 정답으로 처리됐지만,

세상에는 더 빠른 방법이 있을 것이다.

 

문제를 푸는 것보다 중요한건 그 능력자분들의 코드를 보며 배우는 것이다. 따라서 여러 코드를 보러가자.

 

* 생각보다 javascript로 푼 해답이 적어서 서운하다(?)

 

---

좋은 코드 학습:

lokitgom님 코드

https://leetcode.com/problems/build-array-from-permutation/discuss/1362485/Javascript-easy-solution

Javascript easy solution - LeetCode Discuss

 

pgmreddy님 코드

https://leetcode.com/problems/build-array-from-permutation/discuss/1314463/1920-Map-each-element-e-to-Ae-return-resulting-array

1920 - Map each element e to A[e], return resulting array - LeetCode Discuss

 

가장 투표가 많은 두 분 코드를 보기로 했다.

볼수록 정말 놀라운 코드이다. 코드가 뭐 이렇게 짧고 빠를 수 있나.

 

모르면 배우면 된다. 정답이라고 넘어가지 말고 능력자분들의 코드를 이해 하려고 노력해보자.

 

1) 화살표 함수

return nums.map(a=>nums[a]);

위의 코드는 lokitgom님의 코드이다.

이게 당최 무슨 코드인가 한참을 고민하며 구글을 여기저기 찾아보다가 화살표 함수라는 것을 알게 됐다.

ES6 문법이라고 한다.

 

참고자료 : 

https://velog.io/@ki_blank/JavaScript-%ED%99%94%EC%82%B4%ED%91%9C-%ED%95%A8%EC%88%98Arrow-function

JavaScript - 화살표 함수(Arrow function)

 

아래의 사이트를 통해 화살표 함수를 간략하게 공부하고,

이해했는지 확인하기 위해 가장 마지막에 있는 문제도 풀어보면 좋을 것 같다.

 

https://ko.javascript.info/arrow-functions-basics

화살표 함수 기본

 

함수를 만드는 방법 중 하나이며, 아래와 같이 사용할 수 있다고 한다.

// let num = function () { console.log("1") };
let num = () => console.log("1");

매개변수(param)가 하나일 땐 소괄호를 생략해도 되지만, 매개변수가 없을 땐 소괄호를 생략할 수 없다고 한다.

 

만약 함수 내부의 코드가 여러줄이라면 아래와 같이 중괄호를 사용할 수 있다고 한다.

다만, 보기에는 일반적인 함수와 큰 차이가 없는 듯 해서 그리 놀랍지는 않았다.

/* let add = function(a, b) {
	let result = a + b;
    return result;
} */

let add = (a, b) => {
	let result = a + b;
    return result;
}

중괄호를 사용했다면 반드시 return을 사용해서 값을 반환해야 한다고 한다.

 

2) map() 메서드

화살표 함수에서 1차 충격을 받고 화살표 함수에 대해서 짧게 공부했는데 map은 도대체 뭔지..

또 다시 구글을 하염없이 돌아다니다가 Array의 메서드인 것을 발견했다.

 

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/map

Array.prototype.map() - JavaScript | MDN

 

https://hianna.tistory.com/407

[Javascript] 배열 map() 함수로 변경된 새로운 배열 생성하기

map 메서드는 배열의 각각의 요소에 접근하면서 map 메서드의 소괄호 안의 함수에게 전달되고

그 함수가 리턴하는 값으로 새 배열을 만들어주는 메서드인 듯 하다.

반복문으로 값을 배열에 넣는대신 map 메서드를 사용한 것일까.

map 메소드는 forEach문 처럼 하나씩 배열의 요소에 접근하는 것이 아닐까 싶다.

 

https://velog.io/@dnjswn123/forEach%EB%A5%BC-%ED%86%B5%ED%95%B4-%EB%B0%B0%EC%97%B4%EC%9D%98-%EA%B0%81-%EC%9A%94%EC%86%8C%EC%97%90-%ED%95%A8%EC%88%98-%EC%A0%81%EC%9A%A9%ED%95%98%EA%B8%B0-%EA%B7%B8%EB%A6%AC%EA%B3%A0-%ED%99%94%EC%82%B4%ED%91%9C%ED%95%A8%EC%88%98%EB%A1%9C-%EA%B0%84%EB%8B%A8%ED%95%98%EA%B2%8C

forEach를 통해 배열의 각 요소에 함수 적용하기 그리고 화살표함수로 간단하게

 

위에서 공부 겸 찾아본 모든 내용을 바탕으로 lokitgom님의 코드를 해석해보자면

1) "a를 인자로 전달하는 화살표 함수를 호출하고, 그 리턴값은 nums[a]로 함" 

    * 여기에서 a는 nums의 각 요소로 추측됨 (nums[0]부터 nums[n]까지)

       map 메서드가 nums 배열에 대한 메서드이기 때문인 듯함

       (map 메서드가 nums 배열의 요소를 하나씩 가져오고 그 값을 인자로 전달하는 듯함)

2) "그렇게 각각의 배열 요소에 접근해서

     화살표 함수로 nums[nums[0]] 부터 nums[nums[n]]까지 리턴하는 결과를 받아

     새로운 배열을 생성함"

3) 마지막으로 새로 만들어진 배열을 return 하여 함수를 마침

위와 같은 상황으로 돌아가는 코드이지 않을까 조심스럽게 추측해보았다.

 

lokitgom님의 코드에 대한 로직을 정확히 이해하지는 못했지만, 화살표 함수와 map 메서드에 대해서 공부할 수 있어서 좋다.