[알고리즘]데일리 코딩 11-20문제

30분 동안 1문제씩 시간을 정해두고 푸는 코딩 학습 방법을 적용하고
풀이코드를 작성하였습니다.

11.문자열을 요소로 갖는 배열을 입력받아 가장 짧은 문자열과 가장 긴 문자열을 제거한 배열을 리턴해야 합니다.
가장 짧은 문자열의 길이와 가장 긴 문자열의 길이가 같은 경우는 없습니다.
가장 짧은 문자열 또는 가장 긴 문자열이 다수일 경우, 나중에 위치한 문자열을 제거합니다.

function removeExtremes(arr) {
  let short = arr.reduce((a,b) => a.length<b.length ? a:b);
  let long = arr.reduce((a,b) => a.length>b.length ? a:b);
  let newArr = arr.filter(v => v!==long);
  if (newArr.indexOf(short) !== newArr.lastIndexOf(short)) {
        newArr.splice(newArr.lastIndexOf(short),1);
        return newArr;
  }
    return newArr.filter(v => v!==short);
}
//문자열을 요소로 갖는 배열arr에서 가장 짧은 문자열과 긴 문자열을 제거한 배열 리턴
//똑같은 길이라면 나중에 위치한 문자열 제거
//중복되는 가장 짧은 문자열 제거 시,(긴 문자열 제거도 포함)
//arr.reduce((a,b) => a.length<b.length ? a:b); //뒤에 있는 요소 제거
//arr.reduce((a,b) => a.length<=b.length ? a:b); //앞에 있는 요소 제거
//빈문자열이 중복인 경우, 뒤의 문자열만 지워야 하는데 모든 빈 문자열이 제거되는 문제!!
//indexOf로 문자열에서 특정 문자가 처음 등장하는 index를 구하고, 
//lastIndexOf로 뒤에서 부터 등장하는 index를 구해 일치하지 않으면 중복된 문자가 존재함을 알 수 있다.

12.2차원 배열(배열을 요소로 갖는 배열)을 입력받아 'B'의 위치 정보를 요소로 갖는 배열을 리턴해야 합니다.
arr[i]는 'A' 또는 'B'만을 요소로 갖는 배열
'B'의 위치 정보(행, 열)를 요소로 갖는 배열을 리턴해야 합니다.
배열의 요소는 차례대로 행, 열입니다. ([행, 열])
행: 'B'를 요소로 갖는 배열 arr[i]의 인덱스 i
열: arr[i]에서 'B'(arr[i][j])의 인덱스 j
arr, arr[i]의 길이는 다양하게 주어집니다.
항상 한 개의 문자열 'B'가 존재합니다.

function findBugInApples(arr) {
  for(let i = 0; i<arr.length; i++){
    for(let j = 0; j<arr[i].length; j++){
      if(arr[i][j]==='B'){
        return [i,j];
      }
    }
  }
}
//B의 위치를 [행,열]로 리턴
//행의 위치 알기 for문 arr[i][j] === 'B' i는 몇번째줄배열인지, j는 그 배열의 몇번째인지
//i=행, j=열

13.문자열을 요소로 갖는 배열을 입력받아 문자열을 세로로 읽었을 때의 문자열을 리턴해야 합니다. 각 문자열의 길이는 다양합니다.
각 문자의 위치를 행, 열로 나타낼 경우, 비어있는 (행, 열)은 무시합니다.

function readVertically(arr) {
  let result = "";

  let wordLength = arr.map(x=>x.length);//[2,5]
  let maxLength = Math.max(...wordLength);//5
  let longestWord = wordLength.indexOf(maxLength);//[2,5].indexof(5) 값이 5인 인덱스 1
  let arrMax = arr[longestWord];//arr[1] = 가장 긴 문자열을 갖는 배열의 요소

  for(let i=0; i<arrMax.length; i++){
    for(let j=0; j<arr.length; j++)
      result+=arr[j][i];
    }
  result = result.split("undefined").join("");
  return result;
  }

//배열의 문자열 세로로 읽기
//1.문자열길이가 다 다르므로 제일 긴 문자열 찾기
//2.중복반복문, 바깥쪽은 가장 긴 문자열까지, 안쪽은 배열의 길이까지 result+= arr[arr.length까지][arr의 가장 긴 문자열의 길이까지]
//3.Max문자열길이보다 작은 길이인 문자열은 undefined가 중간에 섞여 나오므로, undefined없애주기
//4.특정 문자 없애는 방법 : replace("뺄문자", "") / split("뺄문자").join("") 뺄문자를 기준으로 문자를 떼주고 공백을 합치는 join

//reference 코드
function readVertically(arr) {
  let temp = [];
  for (let i = 0; i < arr.length; i++) {
    let str = arr[i];
    for (let j = 0; j < str.length; j++) {
      if (temp.length === j) {
        temp.push(str[j]);
      } else {
        temp[j] = temp[j] + str[j];
      }
    }
  }

  let result = '';
  for (let i = 0; i < temp.length; i++) {
    result = result + temp[i];
  }

  return result;
}

14.수를 요소로 갖는 배열을 입력받아 각 요소들이 그 이전의 요소들의 합보다 큰지 여부를 리턴해야 합니다.
boolean 타입을 리턴해야 합니다.
arr[i]는 arr[0]부터 arr[i-1]까지의 합보다 커야 합니다.

function superIncreasing(arr) {
  // TODO: 여기에 코드를 작성합니다.
  let result = 0;
  let boolean = [];
  for(let i=0; i<arr.length-1; i++){
    result+=arr[i];
    if(result<arr[i+1]) {boolean.push("true");}
    else {boolean.push("false");}
  }
  if(boolean.includes('false')) {return false;}
  else{return true;}
}
//배열의 각 요소들이 그 이전의 요소들의 합보단 크면 true, 같거나 적으면 false
//for 반복문 돌리고 result += arr[i] if(result<arr[i+1]) 새로운배열에 true/false를 담아주고
//새로운 배열에 false가 포함된다면 return false아니면 return true

//reference 코드
function superIncreasing(arr) {
  let sum = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] <= sum) {
      return false;
    }
    sum = sum + arr[i];
  }
  return true;
}
//배열의 합을 sum, 초기값arr[0]으로 값을 줌
//arr[1~arr.length까지]가 전 요소들의 총합보다 작거나 같다면 false,
//아니라면 sum+=arr[i] 계속 더해줌
//마지막 전 요소까지 다 더해줬는데도 return false에 안걸리면 return true;

15.두 수(num1, num2)를 입력받아, num1를 num2로 나눈 나머지를 리턴해야 합니다.
나눗셈(/), 나머지(%) 연산자 사용은 금지됩니다.
0은 어떤 수로 나누어도 나머지가 0입니다.
어떤 수도 0으로 나눌 수 없습니다. 이 경우 'Error: cannot divide by zero'를 리턴해야 합니다.

function modulo(num1, num2) {
  // TODO: 여기에 코드를 작성합니다.
  if(num1===0 || num1===num2) return 0;
  if(num2===0) return 'Error: cannot divide by zero';

  let i=1;
  while(i<num1){
    let pow = num2*i;
    if(pow>num1) return num1-(num2*(i-1));
    i++
  }
}
//num1%num2 나머지를 구해야 하는데, /랑 % 사용 금지
//num1과 num2가 같거나 num1이 0이면 0을 리턴
//num2가 0이면 에러 리턴
//while반복문으로 num2*i반복하고, num2*i가 num1보다 크면 num1 - num2*(i-1)

//reference 코드
function modulo(num1, num2) {
  if (num2 === 0) {
    return 'Error: cannot divide by zero';
  }
  while (num1 >= num2) {
    num1 = num1 - num2;
  }
  return num1;
} //

16.문자열을 입력받아 아이소그램인지 여부를 리턴해야 합니다. 아이소그램(isogram)은 각 알파벳을 한번씩만 이용해서 만든 단어나 문구를 말합니다.
빈 문자열을 입력받은 경우, true를 리턴해야 합니다.
대소문자는 구별하지 않습니다.

function isIsogram(str) {
  // TODO: 여기에 코드를 작성합니다.
  let newStr = "";
  if(str==="") return true;
  for(let i=2; i<str.length; i++){
    newStr = str.toLowerCase().replace(str[i], "");
    if(newStr.includes(str[i])) return false;
    return true;
  }
}
//소문자로 통일하고 중복되는 문자가 있으면 false, 없으면 true
//for반복문으로 str[i]를 str에서 뺀 새로운 문자열에 여전히 str[i]가 있으면 false, 없으면 true;

//reference 코드
function isIsogram(str) {
  if (str.length === 0) {
    return true;
  }
  let cache = {};
  let strLowered = str.toLowerCase();

  for (let i = 0; i < strLowered.length; i++) {
    if (cache[strLowered[i]]) {
      return false;
    }
    cache[strLowered[i]] = true;
  }
  return true;
}

17.수를 입력받아 제곱근 값을 소수점 두 자리까지 리턴해야 합니다.
최대 소수점 둘째 짜리까지 구합니다. (소수점 셋째 자리에서 반올림)
Math.sqrt 사용은 금지됩니다.

function computeSquareRoot(num) {
  let i = 1;
  while (true){
    if ( Number((i**2).toFixed(2)) === num) {
      break;
    }
    i = (i + (num / i)) / 2;
  } 
  return Number(i.toFixed(2));
}
//num의 제곱근값을 소수점2자리까지 리턴
//제곱근 구하는 방법 : 바빌로니아 법 검색
//x(제곱근근사값) = x+(num(제곱근 구할 숫자)/x)/2
//제곱근 근사값 구하는 방법 : 반복문으로 i=1부터 i**2로 거듭제곱한 값이 num이면 변수 a=i(제곱근값)
//i**2해서 나온 거듭제곱한 값이 num보다 크면 변수a=i-1(제곱근 근사값)
//소수점 2까지 구하는 방법 :  toFixed(2), number 타입 리턴
//근사값에서 정확한 제곱근을 구하려면, 근사값이 제곱근처럼 거든제곱하면 num과 같아질 때까지
//근사값을 계속 제곱근 구하는 공식에 집어넣어야 한다.
// i=(i+(num/i))/2

//reference 코드
function computeSquareRoot(num) {
  const diffs = [1, 0.1, 0.01, 0.001];
  let base = 1;
  for (let i = 0; i < diffs.length; i++) {
    while (base * base < num) {
      base = base + diffs[i];
    }

    if (base * base === num) {
      return base;
    } else {
      base = base - diffs[i];
    }
  }
  return Number(base.toFixed(2));
}

18.문자열을 입력받아 문자열에서 숫자를 모두 찾아 더한 뒤에 해당 값을 (숫자와 공백을 제외한 나머지) 문자열의 길이로 나눈 값을 정수로 반올림하여 리턴해야 합니다.
빈 문자열을 입력받은 경우, 0을 리턴해야 합니다.
숫자(digit)는 연속해서 등장하지 않습니다.

function numberSearch(str) {
  // TODO: 여기에 코드를 작성합니다.
  if(str==="") return 0;
  let arr = str.replace(/ /g,"").split("");
  let numberArr = [];
  let strArr = [];
  for(let i of arr){
   if(isNaN(Number(i))) {strArr.push(i);}
   else{numberArr.push(Number(i));}
  }
  return Math.round(numberArr.reduce((arr,cur) => arr+cur)/strArr.length);
}
//1.문자열 공백 제거 arr = str.replace(/ /g,"").split("")
//2.배열 요소 나열, number타입으로 바꾼 요소가 NaN이면 문자배열에 담기, 아니면 숫자배열에 담기
//3.숫자배열 요소 모두 합치기 reduce
//4.Math.round(숫자합친거/문자배열의 길이)

//reference 코드
function numberSearch(str) {
  const digits = '0123456789';

  if (str === '') {
    return 0;
  }
  let sum = 0;
  let pureStr = '';
  for (let i = 0; i < str.length; i += 1) {
    if (digits.includes(str[i])) {
      // 숫자인 경우
      sum = sum + Number(str[i]);
    } else if (str[i] !== ' ') {
      // 숫자도 공백도 아닌 경우
      pureStr = pureStr + str[i];
    }
  }
  // 결과를 반올림 한다.
  return Math.round(sum / pureStr.length);
}

19.암호화된 문자열과 암호화 키를 입력받아 복호화된 문자열을 리턴해야 합니다.
카이사르 암호(Caesar cipher)는 평문(plaintext)을 암호키 secret개만큼 (오른쪽으로) 평행이동시켜 암호화 합니다. 복호화는 암호화된 문자열을 원래의 평문으로 복원하는 것을 말합니다.
빈 문자열을 입력받은 경우, 빈 문자열을 리턴해야 합니다.
공백은 그대로 두어야 합니다.

//'hello'를 secret 3으로 암호화한 경우: 'khoor'
//'codestates'를 secret 11로 암호화한 경우: 'nzopdelepd'

//내코드
function decryptCaesarCipher(str, secret) {
  // 알파벳
  let alpha = 'abcdefghijklmnopqrstuvwxyz';

  let result = '';
  for (let i = 0; i < str.length; i++) {
    if (str[i] === ' ') {
      // 공백은 그대로 둔다.
      result = result + ' ';
    } else {
      // 현재 문자의 알파벳 순서를 구한다.
      let asis = alpha.indexOf(str[i]);
      // 복호화는 반대 방향으로 이루어기 때문에 seceret을 뺀다.
      //암호화된 문자인덱스 -> 복호화된 문자인덱스로 바꾸는 방법
      let tobe = (asis - secret + alpha.length) % alpha.length;
      result = result + alpha[tobe];
    }
  }
  return result;
}
//str은 암호화된 문자열, secret개만큼 오른쪽으로 평행이동시켜 암호화
//hello -> 알파벳 순서에 따라 h(i-j-k) => k로 바뀜
//return 할 것은 복호화된 문자열
//알파벳 문자열 구하기
//str[i]가 공백이라면 그대로 result에 공백을 붙여주고
//공백이 아니라면 알파벳 문자열에서 str[i]와 같은 알파벳의 인덱스 구하기
//복호화된 인덱스 구하기 : (새로운인덱스-secret+알파벳문자열 길이)%알파벳 문자열길이
//result에 알파벳배열[복호화된 인덱스] 붙여주기
//return result;

20.문자열을 입력받아 연속되는 문자가 있을 경우, 연속 구간을 반복되는 수와 문자로 조합한 형태로 압축한 문자열을 리턴해야 합니다.
빈 문자열을 입력받은 경우, 빈 문자열을 리턴해야 합니다.
3개 이상 연속되는 문자만 압축합니다.

function compressString(str) {
  // TODO: 여기에 코드를 작성합니다.
  for(let i=0; i<str.length-2; i++){
    let str33 = str[i]+str[i]+str[i];
    let str3 = str[i]+str[i+1]+str[i+2];

    let str55 = str[i]+str[i]+str[i]+str[i]+str[i];
    let str5 = str[i]+str[i+1]+str[i+2]+str[i+3]+str[i+4];

    if(str55===str5){
      str = str.replace(str5, 5+str[i]);
    }
    if(str33 === str3){
      str = str.replace(str3, 3+str[i]);
    }
  }
  return str;
}
//str에서 3번연속되는 문자(str[i])가 있다면 str[i] -> 3+str[i]로 바꿔주기
//for문으로 str[i]+str[i+1]+str[i+2]가 str[i]+str[i]+str[i]와 같다면,
//replace(연속되는 문자, 3+str[i])
//그 중복문자가 5이상이라면replace(연속되는 문자, 5+str[i])

//reference 코드
function compressString(str) {
  // 연속되는 문자를 기록하기 위한 변수
  // 첫 번째 문자로 초기화
  let before = str[0];

  // 동일한 문자의 반복 횟수
  let count = 1;

  // 정답으로 리턴할 문자열
  let result = '';

  // 마지막 부분이 연속된 문자일 경우를 위해 dummy 문자 추가
  str = str + ' ';
  for (let i = 1; i < str.length; i++) {
    // 동일한 문자가 반복될 경우
    if (before === str[i]) {
      count++;
    } else {
      // 이전과 다른 문자일 경우,
      // 반복된 횟수가 3 이상일 경우에만 압축을 한다.
      if (count >= 3) {
        result = result + `${count}${before}`;
      } else {
        result = result + before.repeat(count);
      }
      before = str[i];
      count = 1;
    }
  }

  return result;
}