코드카타 - week1_10.31~11.04

송철진·2022년 10월 31일
0

코드카타

목록 보기
1/11

코드카타는 2인1조를 이루어 알고리즘을 푸는 역량을 기르는 시간.

day 1 (10.31)

twoSum함수에 숫자배열과 '특정 수'를 인자로 넘기면, 더해서 '특정 수'가 나오는 index를 배열에 담아 return해 주세요.

nums: 숫자 배열
target: 두 수를 더해서 나올 수 있는 합계
return: 두 수의 index를 가진 숫자 배열

예) nums = [4, 9, 11, 14], target = 13 👉 return은 [0, 1]이 된다

가정
target으로 보내는 합계의 조합은 배열 전체 중에 2개 밖에 없다.

틀린 풀이:

const twoSum = (nums, target) => {
  // 아래 코드를 작성해주세요.
  for(let i in nums){
    for(let j in nums){
      if(nums[i] + nums[j] === target){
        return [Number(i),Number(j)];  
      }
    }
  }  
}
console.log(twoSum([4, 9, 11, 14], 15)); // [0,1]

정리
for...in 구문에서 i는 string타입이고
for문에서 i는 number타입이다

but, 중복이 허용되지 않으면 문제가 된다!
중복 없는 덧셈의 경우의 수는 다음과 같다

ij[i,j]
01,2,3[0,1], [0,2], [0,3]
12,3[1,2], [1,3]
23[2,3]

...에서 다음의 규칙을 찾을 수 있다

  • 3은 nums.length-1
  • j의 첫번째 숫자는 i+1
    따라서;
const twoSum = (nums, target) => {
  // 아래 코드를 작성해주세요.
  for(let i=0; i<nums.length; i++){
    for(let j=i+1; j<nums.length; j++){
      if(nums[i] + nums[j] === target){
        return [i,j];  
      }
    }
  }  
}

day 2 (11.01)

reverse 함수에 정수인 숫자를 인자로 받습니다. 그 숫자를 뒤집어서 return해주세요.
x: 숫자 return: 뒤집어진 숫자를 반환!
예들 들어, x: 1234 return: 4321
x: -1234 return: -4321
x: 1230 return: 321

const reverse = x => {
  // 여기에 코드를 작성해주세요.
  let result="";
  let array = x.toString().split("");
  if(array[0] === "-"){ // 음수일 때
    result = "-";
    for(let i=array.length-1; i>0; i--){
       result += array[i];
    }
    return Number(result);
  }else{                // 정수일 때
    for(let i=array.length-1; i>=0; i--){
       result += array[i];
    }
    return Number(result);
  }
}
console.log(reverse(1234));
console.log(reverse(-1234));

다른 풀이1

다른 풀이2

  • split("")함수 대신 ... 이라는 스프레드 연산자로 쪼갤 수 있다
  • join()함수를 쓰면 합칠 수 있다
  • reverse()함수를 쓰면 배열을 뒤집을 수 있다

day 3(11.02)

String 형인 str 인자에서 중복되지 않은 알파벳으로 이루어진 제일 긴 단어의 길이를 반환해주세요.
str: 텍스트 return: 중복되지 않은 알파벳 길이 (숫자 반환)

예를 들어,
str = "abcabcabc" return 은 3 => 'abc' 가 제일 길기 때문
str = "aaaaa" return 은 1 => 'a' 가 제일 길기 때문
str = "sttrg" return 은 3 => 'trg' 가 제일 길기 때문

방법1.
1. 입력받은 문자열str을 알파벳 단위로 쪼개서 배열v1으로 만든다
2. 배열v1을 중복 요소 없는 배열v2로 만든다
3. 배열v2의 요소로 만들 수 있는 모든 문자열의 경우의 수를 배열v3로 구한다
4. 배열v3를 뒤집은 배열v4를 구한다
👉 길이가 긴 요소부터 짧은 요소 순으로 반복문을 돌릴 것이므로
5. 배열v4의 요소가 str에 존재하는지 반복문을 돌린다
6. 있으면 그 요소의 길이를 반환한다(끝)

문제점: 중복 요소 없는 배열v2의 길이가 9이상이면 max 콜스택 초과 에러가 발생한다

// 배열에서 순서가 있는 num 개수만큼 경우의 수 뽑기 
const getPermutations = (arr, num) => {
    const results = [];
    if (num === 1) return arr.map(v => v);

    arr.forEach((fixed, index, origin) => {
        const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
      
        const permutations = getPermutations(rest, num - 1);
      
        const attached = permutations.map(v => [fixed, ...v]);
        results.push(...attached);
    });

    return results;
}
// 배열에서 순서가 있는 모든 경우의 수 뽑기
const getAllPermutations = (arr) => {
    let results = [];
    arr.forEach((value, index, origin) => {
        results.push(...getPermutations(origin, index + 1));
    });
    return results;
}

// 유닛테스트할 함수 본체
const getLengthOfStr = str => {
  // 입력된 str값이 빈문자열이 0을 반환
  if(str === ""){
    return 0;
  }else{
    const v1 = str.split("");  // 쪼갠다
    const v2 = [...new Set(v1)];  // 최소인자만 뽑는다
    let v3 = getAllPermutations(v2);  // 모든 경우의 수를 구한다(배열로)
    // 배열로 반환된 내부 요소를 string으로 만들기
    for(let i=v2.length; i<v3.length; i++){
      let result="";
      for(let j=0; j<v3[i].length; j++){
        result += v3[i][j];
      }
      v3[i] = result;  
    }
    // 그걸 거꾸로 뒤집기: 길이가 큰 문자열부터 비교할 것이다  
    const v4 = v3.reverse();

    // 입력받은 str에 v4의 요소가 있으면 v4의 길이를 반환한다  
    for(let i=0; i<v4.length; i++){
      if(str.indexOf(v4[i])!==-1){
        return v4[i].length;
      }
    }
  }
}
console.log(getLengthOfStr("abcdefghi"))
// 중복없는글자의 길이가 9이상일 때 콜스택초과 에러: 7~9번 테스트 불합격

방법2.
설명은.. 나중에 알아보자..

day 4(11.03)

숫자인 num을 인자로 넘겨주면, 뒤집은 모양이 num과 똑같은지 여부를 반환해주세요.
num: 숫자 return: true or false (뒤집은 모양이 num와 똑같은지 여부)

예를 들어, num = 123 return false => 뒤집은 모양이 321 이기 때문
num = 1221 return true => 뒤집은 모양이 1221 이기 때문
num = -121 return false => 뒤집은 모양이 121- 이기 때문
num = 10 return false => 뒤집은 모양이 01 이기 때문

const sameReverse = num => {
 
}
  1. 입력받은 숫자를 string으로 만들고 split("")해서 배열arr로 만든다
  2. arr의 맨앞i와 맨뒤length-1을 비교한다(반복 i++)
    i가 arr의 가운데 위치라면 더이상 비교할 필요가 없으므로 반복의 한계를 명시한다
  3. 예를 들면,
    arr = ["1", "2", "2", "1"] 이면 4/2=2 👉 i<2 까지
    arr = ["-", "1", "2", "2", "1"] 이면 5/2=2.5 👉 i<2.5까지
    👉 정중앙은 대칭의 기준이므로 비교할 필요가 없음!
const sameReverse = num => {
 let str = String(num); 
 let arr = str.split(""); 
 for (let i =0; i<str.length/2; i++){
  if(arr[i] !== arr[str.length-1-i]){ 
    return false; } 
 } 
 return true; 
} 
console.log(sameReverse(10801));

다른 풀이1 <오주형 님>
1. 쪼개서 배열로 만들고 = a
2. 역순으로 재배치하고 = b
3. for문으로 a와 b의 요소를 서로 비교해서
같으면 true, 다르면 false

const sameReverse = num => {
  let a = String(num).split("");
  let b = String(num).split("").reverse();
  
  for(let i = 0; i < a.length; i++) {
  if (a[i] == b[i]) {
    return true;
  } else {
    return false;
  }
 }
}

다른 풀이2 <박지영-김호준 님>
1. num을 문자형태로 변환(String())
2. 배열에 쪼개서 할당(스프레드 연산자)
3. 역순으로 변환
4. 합치기
5. 4.를 기존 num과 비교(숫자와 문자를 비교하는 것이므로 == 사용)
6. 삼항연산자로 같으면 true 다르면 false 반환

const sameReverse = num => { return ([...String(num)].reverse().join("")) == num ? true : false;}

day 5(11.04)

strs은 단어가 담긴 배열입니다. 공통된 시작 단어(prefix)를 반환해주세요.
예를 들어 strs = ['start', 'stair', 'step'] return은 'st'
strs = ['start', 'wework', 'today'] return은 ''

  1. 예를 들어
    strs = ['stccccccc', 'stb', 'staaaa'] 라는 배열이 입력된다면
    가장 짧은 문자열인 'stb'의 길이 만큼만 다른 요소와도 비교해주면 된다

  2. 각 요소를 slice(0,길이) 해서 새로운 배열arrNew을 만든다
    => arrNew = ['stc', 'stb', 'sta']

  3. 새 배열arrNew의 요소가 모두 동일한가?
    즉, 새 배열arrNew 중복값이 없는 배열result 로 만들었을 때
    => result = ['stc', 'stb', 'sta']
    result의 길이가 1인가? No

  4. 각 요소를 slice(0,길이-1)해서 배열arrNew을 다시 만든다
    => arrNew = ['st', 'st', 'st']

  5. 중복값 없는 배열 result = ['st']
    result의 길이가 1인가? YES

  6. result[0]의 값을 반환한다

  7. 마지막 1글자끼리 비교해도 result의 길이가 1이 아니면 반복문을 종료하고 빈문자열("")을 반환한다

const getPrefix = strs => {
  
  let array = [];
  for(let i=0; i<strs.length; i++){
    array.push(strs[i].length);
  }
  const minLen = array.sort()[0];
  
  for(let i = minLen; i>0; i--){
    let arrNew = strs.map(el => el.split("").slice(0, i).join(""));
    let result = [...new Set(arrNew)];
    
    if(result.length === 1){
      return result[0];
    }
  }
  return "";
}

Today I Learn
substring(기준, n)을 쓰면 문자열을 기준위치부터 n위치 전까지를 반환할 수 있다! slice(기준, n)만 알았던 나는 string을 배열로 만들어야 했기에 split("")와 join("") 메소드를 쓰는 번거로운 작업을 해야 했다.

profile
검색하고 기록하며 학습하는 백엔드 개발자

0개의 댓글