TIL. 알고리즘 문제풀이

1. 공통된 시작 단어

문제 설명

strs은 단어가 담긴 배열이다. 공통된 시작 단어(prefix)를 반환하기.
예를 들어 strs = ['start', 'stair', 'step'] return은 'st'

▣ 입출력 예

input	output
['start', 'stair', 'step']	'st'
['start', 'wework', 'today']	''

풀이

솔루션을 보고 이해하기

✍️ solution 1

let longestCommonPrefix = function (strs) {
  let pre = '';
  let firstString = strs[0];

  if (strs.length < 1) return pre;

  for (let i = 0; i < firstString.length; i++) {
    let save = firstString[i];
    for (let j = 0; j < strs.length; j++) {
      if (save !== strs[j][i]) return pre;
    }
    pre = pre + save;
  }
  return pre;
};

const strs = ['flower', 'flow', 'flight'];
const a = longestCommonPrefix(strs);

• pre 라는 빈 문자열을 선언하고 중복되는 시작 단어를 넣는 방식이다.
• 받아온 배열의 첫 번째 단어를 firstString 에 먼저 담아두고 이것을 기준으로 비교한다.
• for 문을 통해서 다른 요소들과 기준 단어의 시작글자들이 맞는지 판별해서 맞다면 pre 에 계속해서 추가하는 방법이다. 🤔

✍️ solution 2

const getPrefix = strs => {
  let prefix = strs[0];

  if(strs.length === 0) return '';

  for(let i=0; i<strs.length; i++){
    while(strs[i].indexOf(prefix) !== 0){
      prefix = prefix.slice(0, prefix.length-1)
    }
  }
  return(prefix)
}

const strs = ['start', 'stair', 'step'] 
console.log(getPrefix(strs))

• 1번 solution 보다 간편한 방법이다.
• 마찬가지로 기준 prefix 를 할당하고 for문을 통해서 다른 단어들과 비교해준다.
• 이때 while 문에서 IndexOf 를 통해 앞 문자열이 같은지 비교할 수 있다. 같다면 0, 다르다면 -1을 반환한다는 특징을 활용한다.
• slice 를 이용해서 기준 문자를 끝에서 부터 1자씩 잘라준다. 이렇게 하지 않으면 무한 루프에 빠지게 된다. 🧐

---

2. 가장 자주 등장한 숫자

문제 설명

nums는 숫자로 이루어진 배열이다. 가장 자주 등장한 숫자를 k 개수만큼 return하기.

▣ 입출력 예

input	output
nums = [1,1,1,2,2,3], k = 2	[1,2]
nums = [1], k = 1	[1]

풀이

function topK(nums, k) {
  let obj = {} // 1)
  for(let i=0; i<nums.length; i++){ // 2)
    let num = nums[i]
    if(obj[num]){
      obj[num] = obj[num]+1;
    } else{
      obj[num] = 1
    }
  }
  let sortedObj = Object.keys(obj).sort(function(a, b) { //3)
   return obj[b]-obj[a];
  })
  let result = sortedObj.slice(0,k) //4)
  console.log(result)
  return result.map(a => Number(a)) //5)
}

let nums = [1,1,2,3,3,3,4,4,4,4,5]
let k = 2
topK(nums,k)

✍️

• 1) 빈 객체를 선언한다.
• 2) for 문을 돌려서 객체 안에 nums로 받은 요소를 키로 넣고, 해당 키가 있다면 +1, 없다면 1을 할당한다.
• 3) 객체에 키와 값이 담겨있는데, 내가 필요한건 키의 순차가 아니라 키에 할당된 값의 순차이다. 또, 내림차순으로 정렬한다.
• 4) 위에서 내림차순으로 정렬한 이유는 slice 메서드를 사용하기 위해서이다. 배열을 0에서부터 k로 받은 넘버까지 잘라낸다.
• 5) 마지막으로 타입을 넘버로 변환해서 리턴한다.

✍️
처음 접근은 객체로 잘 접근했지만 3)부터가 어려웠던 것 같다. sort 함수에서 단순 정렬이 아니라 키에 담긴 값의 순차정렬을 통해서 키를 얻어낸다는 생각까지 떠올리기가 오래 걸렸던 것 같다. 차근 차근 익숙해지자 😀!!