day 1_11.21

문제
양수 N을 이진법으로 바꿨을 때, 연속으로 이어지는 0의 갯수가 가장 큰 값을 return해 주세요.

• 이어지는 0은 1과 1사이에 있는 것을 의미합니다.
• 1과 1사이에 있는 0을 binary gap 이라고 하겠습니다.

input: 9
output: 2
설명: 9의 이진수는 1001 입니다. 
1과 1사이에 있는 0은 2 이므로, 2를 return

input: 529
output: 4
설명: 529의 이진수는 1000010001 입니다. 
binary gap은 4와 3 두개가 있습니다. 
이 중 큰 값은 4이므로 4를 return

input: 20
output: 1
설명: 20의 이진수는 10100 입니다. 
1과 1사이에 있는 연속된 0의 수는 1 뿐입니다. 
(뒤에 있는 0은 1사이에 있는 것이 아니므로)

input: 15
output: 0
설명: 15의 이진수는 1111 입니다. 
binary gap이 없으므로 0을 return

input: 32
output: 0
설명: 32의 이진수는 100000 입니다. 
binary gap이 없으므로 0을 return

const solution = N => {
 
}

test 5,6의 기대값이 각각 5, 2인데 둘다 0으로 나와서 통과하지 못했다.
test 5,6은 어떤 수였을까?

const solution = N => {
  // 십진수를 이진수로 변환
  let binary = N.toString(2); 
  // 0이 포함되어 있지 않으면 0 반환
  if(!binary.includes("0")){ 
    return 0;
  }
  // 배열로 만들어서 오른쪽 끝자리의 0을 모두 제거
  let binary1 = binary.split(""); 
  while(binary1[binary1.length-1] === '0'){
    binary1.pop()
  }
  // 문자열로 합치고 '1'을 기준으로 쪼개서 0들의 길이로 매핑 
  let length = binary1.join("").split("1").map((el)=>{
    return el = el.length;
  })
  // 내림차순으로 정렬하고 첫번째 값을 반환
  let binaryGap = length.sort(function(a,b){return b-a;})[0];
  
  return binaryGap;
}

day 2_11.22

문제
prices는 배열이며, 각 요소는 매일의 주식 가격입니다. 만약 한 번만 거래할 수 있다면 = 사고 팔 수 있다면, 제일 큰 이익은 얼마일까요?

Input: [7,1,5,3,6,4]
Output: 5
설명: 2일(가격=1)에 샀다가 5일(가격=6)에 사는 것이 6-1이라 
제일 큰 수익 7-1=6 은 안 되는거 아시죠? 먼저 사야 팔 수 있습니다.

Input: [7,6,4,3,1]
Output: 0
설명: 여기서는 매일 가격이 낮아지기 때문에 거래가 없습니다. 그래서 0

const maxProfit = prices => {
 
};

1. 배열에서 샀을 때의 index i, 팔았을 때의 index j 라고 할 때
   사는게 파는 것보다 먼저라는 조건을 만족하는 관계는 j = i + 1
2. 차액이 양수여야 수익이 나므로 diff > 0 일 때의 값들을 배열에 담고
   내림차순으로 정렬해서 첫번째 값을 반환한다
3. 단, 차액이 모두 음수면 0을 반환한다

const maxProfit = prices => {
  let array =[];
  for(let i = 0; i<prices.length-1; i++){
    for(let j= i+1; j<prices.length; j++){
      let diff = prices[j]-prices[i]
      if(diff >0){
        array.push(diff);
      }
    }
  }
  if(array.length===0){
    return 0;
  }
  return array.sort(function(a,b){return b-a})[0]  
};

day 3_11.23

문제
다음과 같이 input이 주어졌을 때,같은 알파벳으로 이루어진 단어끼리 묶어주세요.

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

output에서 순서는 상관없습니다.

const groupAnagrams = strs => {

};

0. 입력받은 인자 strs

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

1. 변수b는 입력받은 배열strs의 string요소들을 쪼개고 정렬하고 합쳐서 철자가 같은 요소는 같은 단어가 되도록 매핑한 배열이다

• strs와 순서가 동일한 점을 이용한다

b = ["aet", "aet", "ant", "aet", "ant", "abt"]

2. 변수c는 b에서 중복값을 제거한 배열이다

c = ["aet", "ant", "abt"]

3. c의 요소들을 키로 가지는 객체obj의 초기값을 빈배열[]로 설정하고

obj = {
  abt: [],
  aet: [],
  ant: []
}

4. b의 요소들을 키로 객체obj에 접근하여 매칭되는 값에 strs의 요소들을 push()한다

obj = {
  abt: ["bat"],
  aet: ["eat", "tea", "ate"],
  ant: ["tan", "nat"]
}

5. 초기값은 빈배열[]인 변수d에 객체obj의 값을 차례로 push()하고 d를 리턴한다

d = [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

const groupAnagrams = strs => {
  let b = strs.map(el => el.split("").sort().join(""))
  let c = [...new Set(b)]

  let obj = {}
  for(let i=0; i<c.length; i++){
    obj[c[i]] =[]
  }
  for(let i=0; i<strs.length; i++){
    obj[b[i]].push(strs[i])
  }
  let d = []
  for(let i in obj){
    d.push(obj[i])
  }
  return d;
};

day 4_11.24

문제
숫자로 이루어진 리스트 nums를 인자로 주면, 그 안에서 어떤 연속적인 요소를 더했을 때 가장 큰 값이 나오나요? 가장 큰 값을 찾아 return해주세요.

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
설명: [4,-1,2,1] 를 더하면 6이 가장 크기 때문

const maxSubArray = nums => {

};

test5,2 통과 못함(다시 생각해볼 것!)

function x (arr) {
  let y = []
  let j = arr.length;
while(j > 1){
  for(let i=0; i<arr.length-1; i++){
    y.push(arr.slice(i,i+j))
    if(i+j === arr.length-1){
      break;
    }
  }
  j--;
}

const sumArr = (arr) => {
 return arr.reduce(
  function add(sum, currValue) { 
    return sum + currValue; 
  }, 0);
}

return y.map( el=>sumArr(el) ).sort(function(a,b){return b-a})[0]


}

let b = [-2,1,-3,4,-1,2,1,-5,4]
console.log( x(b) )

day 5_11.25

이진탐색법(Binary Search)

이진탐색을 배우기 전에 선형탐색(Linear Search)먼저 보겠습니다.

** 선형탐색이나, 이진탐색의 요소는 오름차순이나 내림차순으로 되어 있어야 적용할 수 있는 알고리즘입니다.

let arr = [2, 4, 6, 8, 11, 14];

위의 배열에서 요소가 8인것을 찾으려면 어떻게 해야할까요?
index 0에서부터 5까지 차례대로 요소를 확인하면서 8이 나올 때까지 for 문을 돌리면 됩니다.
이렇게 첫 index 부터 하나하나 찾아나서는 것을 선형탐색이라고 합니다.

그런데 배열의 길이가 1000이고, 1000이라는 요소를 찾아야 하는데 arr[999]에 1000이 있다고 가정한다면 몇 번의 for문이 돌아갈까요?
네, 1000번 입니다.

이렇게 선형탐색의 단점은 요소에 따라 탐색을 여러 번 해야할 수도 있다는 점입니다.
즉, 1을 찾으려면 for문을 한 번만 돌려도 되는데, 1000을 찾으려면 for문을 1000번 돌려야 한다는 말입니다.
만약 for문 내부에 복잡한 계산이 들어있다면 실행속도가 느려지고 효율적이지 않은 로직이 될 것입니다.

그럼 좀 더 효과적인 알고리즘이 있을까요?
네! 바로 이진 탐색입니다.

이진 탐색은 순서대로 찾는 것이 아니라, 중간부터 찾아 나서는 방법입니다.
만약 아래와 같은 배열에서 7을 찾아야 한다면,
첫 번째로 중간 위치의 요소를 비교하고(7<14)찾아야할 값보다 크면 왼쪽의 중간에서 다시 비교합니다.
다시 한 번 크기를 비교해서 오른쪽의 중간으로 갈지, 왼쪽의 중간으로 갈지 결정하여 다시 찾아나서는 것을 이진 탐색법이라고 합니다.

오늘의 코드 카타

오름차순인 숫자 nums 배열과 찾아야할 target을 인자로 주면,
target이 몇 번째 index인지 return 해주세요.

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1

설명: 찾지 못하면 -1로 return 해주세요.

• nums 배열에 있는 요소는 서로 중복된 값이 없습니다.

const search = (nums, target) => {

}

const search = (nums, target) => {
  let i = Math.floor(nums.length/2) // 소수점 내림
  while(nums[i] !== target){
    if( nums[i] > target ) i--;
    else i++;
  }
  return i;
}

let a = [-1,0,3,5,9,12]
let target = 9
console.log( search(a, target) ) // 4