코테연습 2일차

그래도 괜찮은 회사 다닌 내가 3년동안 발전이 없었던 이유는 열심히 하지 않아서 일 것이다.

 

항상 나의 삶은 발등에 불이 떨어져야 시작하는 삶이였고

 

벤쿠버에서 먹고살일이 막막해지자 드디어 코딩테스트 공부를 하기 시작하는데...

 

1. 바이너리 서치 트리 bst == 이진트리 탐색문제

https://leetcode.com/problems/range-sum-of-bst/description/

Range Sum of BST - LeetCode

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} low
 * @param {number} high
 * @return {number}
 */
var rangeSumBST = function(root, low, high) {
    var result = 0
   if(!root) {
       return 0;
   }
   if(root.val >= low && root.val <= high){
       result = root.val;
   }
   return result + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
};

2. 이중 for문 써서 푸는거?

https://leetcode.com/problems/two-sum/description/

Two Sum - LeetCode

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var Output = []
    for(var f = 0; f<nums.length; f++){
        var sum = 0
       for(var s =f+1; s<nums.length; s++){
               sum = nums[f] + nums[s];
         if(sum == target){
             Output.push(f);
             Output.push(s);
             return Output;
         }  
       }
    }
    };

내가 쓴방법은 부르투 포스 라는 방법으로 모든 경우의 수를 확인하는것임 배열의 크기가 큰 경우 속도가 느려질수 있음 주의

 

갓 지피티의 조언

var twoSum = function(nums, target) {
    var map = {};  // 해시 테이블을 저장할 객체를 선언합니다.
    for (var i = 0; i < nums.length; i++) {  // 주어진 배열을 순회합니다.
        var complement = target - nums[i];  // 목표값에서 현재 요소의 값을 뺀 '보수'를 구합니다.
        if (map[complement] != undefined) {  // 만약 이 보수가 해시 테이블에 존재한다면, 이 보수의 인덱스와 현재 요소의 인덱스를 반환합니다.
            return [map[complement], i];
        }
        map[nums[i]] = i;  // 보수가 해시 테이블에 존재하지 않는다면, 현재 요소와 그 인덱스를 해시 테이블에 저장합니다.
    }
};

포문을 한번사용하는것도 그렇고 더하기말고 빼기를 이용해서 남은 값이 배열에 있는지만 확인하면 된다는게 똑똑한 방법인듯함

코드에서 map[complement]는 해시 테이블 map에서 '보수'에 해당하는 키의 값을 조회하는 것

또 배워야할것은 인덱스를 바로뽑아내는 방법 나처럼 배열에 인덱스 하나씩 푸시해서넣는게 아니라 이렇게 하면 바로 배열로 리턴 가능할듯

map[complement]의 결과 값은 '보수'에 해당하는 키가 해시 테이블에 처음 등장했을 때의 인덱스입니다. 즉, 배열을 순회하면서 현재 요소 값이 '보수'가 되는 경우가 있다면, 그 때의 인덱스가 map[complement]의 값이 됩니다. 예를 들어, nums = [2, 7, 11, 15]이고 target = 9인 경우를 생각해봅시다. 이 때, nums[1]의 값인 7은 target - nums[0] 즉, 9 - 2 = 7이므로, map[7]은 1이 됩니다. 따라서 map[complement]는 이 '보수' 값이 해시 테이블에 처음 등장했을 때의 인덱스를 반환하게 됩니다. 따라서, 만약 map[complement]가 undefined가 아니라면, 이는 '보수' 값이 이미 배열에서 나타났음을 의미하며, 그 때의 인덱스와 현재 인덱스가 두 수의 합이 목표값이 되는 두 인덱스가 됩니다.

 

설명을 잘읽어보고 다시 한번 머리속으로 풀어보자

 

3. if문 처리하는것 

https://leetcode.com/problems/roman-to-integer/solutions/4414081/best-javascript-solution-and-video-explantion-tco-n-sco-1/

Best javascript solution and video explantion TCO(n) SCO(1) - undefined - LeetCode

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    var result = 0
    for(var i = 0; i < s.length; i++){
        if(s[i] == "I"){
            result += 1
        } 
        if(s[i] == "V"){
            if(s[i-1]=="I"){
                result += 3
            }else{
                result += 5
            }
        }
        if(s[i] == "X"){
            if(s[i-1]=="I"){
                result += 8
            }else{
            result += 10
        }}
        if(s[i] == "L"){
            if(s[i-1]=="X"){
                result += 30
            }else{
            result += 50
        }}
        if(s[i] == "C"){
            if(s[i-1]=="X"){
                result += 80
            }else{
            result += 100
        }}
        if(s[i] == "D"){
            if(s[i-1]=="C"){
                result += 300
            }else{
            result += 500
        }}
        if(s[i] == "M"){
            if(s[i-1]=="C"){
                result += 800
            }else{
            result += 1000
        }}

    } 
    return result;
}

이런식으로 풀어도 될까 싶었다만.... 일단 내가 아는선에서 해결해보자 하여 일일히 다 처리하는 아주 초등학생 느낌으로다가 풀어보았음

오브젝트를 배열로 만들어서 하고 싶었지만 일단 구글링 없이 하는방법 아는걸로만 풀어보고자함

 

다른사람의 풀이도보고 갓지피티의 풀이도 봐보자

우선 로마 숫자를 숫자에 매핑하는 객체를 생성합니다.
문자열의 각 문자를 순회하면서 해당 문자가 다음 문자보다 값이 크거나 같은 경우에는 결과에 더하고, 그렇지 않은 경우에는 결과에서 뺍니다.
이 방법을 사용하면 코드는 다음과 같이 간결해집니다.
/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    var roman = {"I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000};
    var result = 0;

    for (var i = 0; i < s.length; i++) {
        var current = roman[s[i]], next = roman[s[i+1]];

        if (next > current) {
            result -= current;
        } else {
            result += current;
        }
    }

    return result;
};

다른 사람의 풀이와 같은 방식으로 갓지피티 님도 푼것같다

 

코드를 뜯어보면서 이런유형의 문제를 해결하는 방법을 익혀야할듯

 

챗지피티보다 못한 인간의 삶 ㅎ...

 

그래도 꾸준히 해보자 어제는 1문제 오늘은 2문제 내일은 4문제 let's gooooo~~~