Algorithm(중하)

function solution(seoul) {
  var answer = '';
  for (let i=0; i<seoul.length; i++){
    if (seoul[i].includes('Kim')){
      return `김서방은 ${i}에 있다`;
    }
 
  }
}

// alternative
function solution(seoul){
  var idx = seoul.indexof('Kim');
  return "김서방은" + idx + "에 있다";
}

feedback: 문자열에서 특정 문자의 위치를 찾기 위해서 indexOf 사용 가능. string.indexof(searchvalue, position)이 method이며 1st parameter is the string I want to find, and the 2nd parameter(optional) is a position I want to start from. 찾는 문자열이 없을 경우 -1을 return하고 대소문자를 구분함. 위 함수로는 찾고자 하는 문자열이 나타난 '첫번째' 위치만 찾을 수 있으나 약간의 코드 변경을 하여 모든 index를 리턴하도록 할 수 있음.

// 1st try => fail the complexity test
function solution(participant, completion) {
  var sorted_index;
  
  for (let i=0; i<completion.length; i++){
    sorted_index = participant.indexOf(completion[i]);
    answer = participant.splice(sorted_index, 1);   
  }
  return participant.toString();
}
 
// 2nd try => fail the complexity test
function solution(participant, completion) {
  return participant.find((person) => {
      if (completion.includes(person)) {
          completion.splice(completion.indexOf(person), 1);
      } else return true;
  });
}
}

// 3rd try
function solution(participant, completion) {
  participant.sort(); completion.sort();
  for (let i=0; i<participant.length; i++){
    if (participant[i] != completion[i]){
      return participant[i];
    }
  }
}

feedback: time-complexity 때문에 몇 시간 골머리를 썩혔던 문제. 처음에는 For loop 두 개를 돌려서 문제를 해결했었는데 test cases는 다 통과했지만 효용성에서 시간 초과로 다 실패를 했다. for loop 자체가 시간이 오래 걸리는 코드라 for loop을 하나 써서 문제를 해결하려고 코드를 바꿨는데 저 코드도 마찬가지로 효용성 면에서 빵점이다. complexity를 더 배워야지 알겠지만 아마 splice자체도 배열 안을 차례대로 돌면서 element를 제거시켜주는 거라 그런지 시간이 오래 걸렸다. The time complexity of indexOf = O(n), for loop = O(n), splice = O(n). worst time complexity다. indexof와 splice를 쓰지 않기 위해서는 alphabetical order로 sort해서 비교하면 되기 때문에 이 방법을 이용해서 해결.

• for more about time-complexity
링크텍스트

function solution(participant, completion) {
  const map = new Map();

  for (let i=0; i<participant.length; i++){
    let a = participant[i], b=completion[i];
    
    map.set(a,(map.get(a) || 0) + 1);
    map.set(b,(map.get(b) || 0) - 1);
  }
  for (let [key,value] of map){
    if (value>0)  return key;
  }
  return 'nothing';
}

feedback: 이 문제에서는 hashing이라는 개념도 어떤 식으로 적용해야 하는지 배웠는데 Map()을 이용해 object를 만들고 고유 메서드(set, get)를 이용해 작성한 코드이다. 완주를 할 경우 map의 key에 대한 value를 0으로 만든 방법이다. 만약 동명이인이 존재한다면 value가 2가 되고 완주를 하면 -1을 뺀 1이 되므로 value>0이 된다. 완주를 못한다면 -1이 빼지지 않으므로 1로 남은 채 value 값은 >0 이다. hashing의 최대 장점은 time-complexity가 O(1)이라는 점. 물론 value가 포화상태라면 max O(n)까지 갈 수는 있다.

map methods
new Map() – 맵을 만듦.
map.set(key, value) – key를 이용해 value를 저장함.
map.get(key) – key에 해당하는 값을 반환. key가 존재하지 않으면 undefined를 반환.
map.has(key) – key가 존재하면 true, 존재하지 않으면 false를 반환.
map.delete(key) – key에 해당하는 값을 삭제.
map.clear() – 맵 안의 모든 요소를 제거.
map.size – 요소의 개수를 반환.

function solution(s){
  return s.split(' ').map(i => i.split('').map((j,key) => key%2 == 0 ? j.toUpperCase() : j).join('')).join(' ');
}

feedback: for loop을 2개 사용해서 풀었는데 훨씬 간결한 코드를 찾음

function solution(n) {
  var answer = 0;

  let temp = 0;
  let swapped;
  let k = (n+"").split('').map(i=> i = parseInt(i));
  do{
    swapped = false;
  for (let i=0; i<k.length-1; i++){
    if (k[i] < k[i+1]){
      temp = k[i];
      k[i] = k[i+1];
      k[i+1] = temp;
      swapped = true;
    }
  }
}while(swapped)

  return Number(k.join(''));
}

// alternative
return parseInt((n+"").split("").sort().reverse().join(""));

feedback: js의 method만 잘 알고 있다면 굳이 bubblesort를 사용할 필요가 없었던 문제.

// sol1:bubble sort -> 시간 초과
function solution(n) {
  var answer = 0;

  
  let swapped;
  do{
    swapped = false;
  for (let i=0; i<n.length-1; i++){
    if (n[i] < n[i+1]){
      temp = n[i];
      n[i] = n[i+1];
      n[i+1] = temp;
      swapped = true;
    }
  }
}while(swapped)

  n.length >1 ? n.pop() : n = [-1];
  return n;  
}

// sol2
function solution(n) {
   n.splice(arr.indexOf(Math.min(...n)),1);
   if(n.length<1)	return[-1];
   return n;
 }

feedback: bubble sort 사용했더니 시간 초과로 fail이 떴다. method가 있나 따로 검색해봤더니 min이라는 method가 있었다. JS, Python이 이런 method가 많다는 점에서 매우 편리한 것 같다. 참고로 ...arr는 ES6의 destructing 할당 구문으로 array에서 각각의 element를 추출하여 별도의 변수로 만들 수 있는 JS식이다. 즉, 만약 arr = [1,2,3]이라면 Math.min(1,2,3)이랑 같다.