[binarysearch] 93, 96, 97, 98, 100, 102, 107 (Easy)

93. A Strictly Increasing Linked List

연결리스트가 오름차순인지 검사하는 문제. 같은 수가 나와도 오름차순이 아니므로 false를 반환한다.

/**
 * class LLNode {
 *   constructor(val, next=null) {
 *     this.val = val
 *     this.next = next
 *   }
 * }
 */
class Solution {
    solve(head) {
        if (!head.next) return true;

        let beforeVal = head.val;
        let curNode = head.next;

        while(curNode) {
            if (beforeVal >= curNode.val) return false;
            beforeVal = curNode.val;
            curNode = curNode.next;
        }
        
        return true;
    }
}


96. Interleaved String

두 문자열이 주어질 때, 두 문자열에서 하나의 문자씩 붙여 하나의 문자열로 만드는 문제.

class Solution {
  solve(s0, s1) {
    if (s0.length === 0) {
      if (s1.length === 0) return '';
      return s1;
    }
    if (s1.length === 0) return s0;

    const result = [];

    for (let i = 0; i < s0.length || i < s1.length; i++) {
      if (i < s0.length) result.push(s0[i]);
      if (i < s1.length) result.push(s1[i]);
    } 

    return result.join('');
  }
}


97. Check Palindrome

문자열이 중앙을 기준으로 데칼코마니인지 확인하는 문제.
Two pointer를 이용하여 풀었다.

class Solution {
  solve(s) {
    if (!s) return true;
    
    let l = 0, r = s.length - 1;

    while (l <= r) 
      if (s[l++] !== s[r--]) return false;

    return true;
  }
}


98. Anagram Checks

두 문자열이 Anagram 인지 확인하는 문제.
두 문자가 서로 구성하는 문자들과 그 문자들의 개수가 같은지 확인하는 문제다.
Map 을 사용하였다.

s0 문자열의 문자를 하나씩 맵에 넣는다.
s1 문자열의 문자를 만들어둔 맵에서 제거해나간다.
Map의 크기가 없다면 같다는 뜻이므로 true를 반환한다.

class Solution {
  solve(s0, s1) {
    if (s0.length !== s1.length) return false;

    const map = new Map();

    for (let i = 0; i < s0.length; i++) {
      if (map.has(s0[i])) {
        let count = map.get(s0[i]);
        map.set(s0[i], count + 1);
      } else 
        map.set(s0[i], 1); 
    }

    for (let i = 0; i < s1.length; i++) {
      const count = map.get(s1[i]);
      if (count === 1) {
        map.delete(s1[i]);
        continue;
      }
      map.set(s1[i], count - 1);
    }

    return !map.size ? true : false;
  }
}


100. Max Product of Two Numbers

숫자 배열 중에서 두 수를 곱한 것 중 가장 큰 수를 반환하는 문제.
음수도 나올 수 있고, 두 음수를 곱하면 양수이므로 가장 클 수도 있다.
음수가 배열에 존재함을 가정하고, 배열을 정렬한 뒤 앞에서 2개, 뒤에서 2개를 곱한 것 중 가장 큰 것을 반환하도록 했다.

class Solution {
  solve(nums) {
    if (nums.length <= 1) return 0;
    if (nums.length === 2) return nums[0] * nums[1];

    nums.sort((a, b) => a - b);

    return Math.max(nums[0] * nums[1], nums[nums.length - 2] * nums[nums.length - 1]);
  }
}


102. Longest Consecutive Duplicate String

문자열에서 가장 많이 연속된 문자의 길이를 반환하는 문제.
Two pointer를 사용하였다.

class Solution {
  solve(s) {
    if (s.length <= 1) return s.length;

    let l = 0;
    let r = 0;
    let maxLength = 0;
    let curLength = 0;

    while (r < s.length) {
      if (l === r) {
        curLength = 1;
        r++;
        continue;
      }
      if (s[l] === s[r]) {
        curLength++;
        r++;
      } else l = r;
      maxLength = Math.max(maxLength, curLength);
    }
    return maxLength;
    }
}


107. Check Power of Two

주어진 수가 2의 제곱되었을 때의 수인지 확인하는 문제.

class Solution {
  solve(n) {
    if (n === 1) return true;
    if (n === 0 || n % 2 !== 0) return false;
    
    for (let i = 1; i < 31; i++) 
      if (n === Math.pow(2, i)) return true;
    
    return false;
  }
}

좋은 웹페이지 즐겨찾기