[Leetcode] 1. Two Sum, 13. Roman to Integer

1. Two Sum

링크

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

 

풀이

시간 - 5:05

var twoSum = function(nums, target) {
    for (let i=0; i<nums.length; i+=1) {
        let sum = nums[i]
        for (let j=i+1; j<nums.length; j+=1) {
            if (sum + nums[j] === target) {
                return [i,j]
            }
        }
    }
};

 

인사이트

없음

---

 

13. Roman to Integer

링크

https://leetcode.com/problems/roman-to-integer/description/

 

풀이

시간 - 52:03

const ROMAN_NUMBER = {
  I: 1,
  V: 5,
  X: 10,
  L: 50,
  C: 100,
  D: 500,
  M: 1000,
};

const SPECIAL_CASES = {
  'I': { 'V': true, 'X': true },
  'X': { 'L': true, 'C': true },
  'C': { 'D': true, 'M': true }
};

// 계수 결정 (V, L, D는 0.8, X, C, M은 0.9)
const getMultiplier = (char) => {
  return (char === 'V' || char === 'L' || char === 'D') ? 0.8 : 0.9;
};

var romanToInt = function(s) {
  let sum = 0;
  let temp = 0;
  let lastFlag = '';
  
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    const number = ROMAN_NUMBER[char];
    
    if (lastFlag !== char) {
      if (SPECIAL_CASES[lastFlag] && SPECIAL_CASES[lastFlag][char]) {
        temp = Math.floor(number * getMultiplier(char));
      } else {
        sum += temp;
        temp = number;
      }
    }else {
        temp += number;
    }

    lastFlag = char;
  }
  
  return sum + temp;
};

 

인사이트

1. 로직 분기를 잘 설계해야지 구현에서 삽질이 준다. 설계를 더 잘하자.

2. 경계 조건에서 실수가 많다. 조심하자

3. 위 문제는 규칙성이 있다. 규칙성을 파악하면 코드가 매우 간단해진다. 모르는 나는 매우 삽질을 했다.

 

 

---

14. Longest Common Prefix

링크

https://leetcode.com/problems/longest-common-prefix/description/

 

 

풀이

시간 - 27:30

var longestCommonPrefix = function(strs) {
    if (strs.length <=1) return strs[0]

    const mainWord = strs[0]
    let current = ''

    for (let i=0; i<mainWord.length; i+=1){
        current += mainWord[i]

        for (let j=1; j<strs.length; j+=1){
            if (strs[j].slice(0,i+1) !== current){
                return current.slice(0,current.length-1)
            }    
        }
    }

    return mainWord
};

 

인사이트

1. 문제 잘못 읽어서 실수했다. 근데, 테스트케이스를 다 맞은 거보니 히든 케이스에서 항상 점수를 잃어버렸나보다.

2. 예외처리에서 실수를 많이 했다. (strs 배열의 길이가 1이하일 때, 모든 원소의 문자열이 동일할 때)

3. 문자열 검색 시에 hashmap이나 trie 등을 사용하면 좋다. 이런 문제 유형을 LCP라 한다.