TIL. 알고리즘 문제풀이

1. 격자판 최대합

문제 설명

5*5 격자판에 아래와 같이 숫자가 적혀있습니다. N*N의 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가 장 큰 합을 출력합니다.

▣ 입력설명
첫 줄에 자연수 N이 주어진다.(1<=N<=50) 두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는다.

▣ 출력설명
최대합을 출력합니다.

▣ 입출력 예

input	output
5 10 13 10 12 15 12 39 30 23 11 11 25 50 53 15 19 27 29 37 27 19 13 30 13 19	155

풀이

const solution = (arr) => {
  let answer = (sum1 = sum2 = 0);
  let n = arr.length;

  // 1)
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      sum1 += arr[i][j];
      sum2 += arr[j][i];
    }
    answer = Math.max(answer, sum1, sum2);
    sum1 = sum2 = 0;
  }

  // 2)
  for (let i = 0; i < n; i++) {
    sum1 += arr[i][i];
    sum2 += arr[i][n - 1 - i];
  }
  answer = Math.max(answer, sum1, sum2);
  return answer;
};

let arr = [
  [10, 13, 10, 12, 15],
  [12, 39, 30, 23, 11],
  [11, 25, 50, 53, 15],
  [19, 27, 29, 37, 27],
  [19, 13, 30, 13, 19],
];
console.log(solution(arr)); // 155

• 1) 이중 for 문을 통해서 각 행과 열의 최댓값을 구한다.
• 2) 대각선의 최댓값을 구해서 기존 answer과 비교 후 높은 값을 저장한다.

---

2. 회문 문자열

문제 설명

앞에서 읽을 때나 뒤에서 읽을 때나 같은 문자열을 회문 문자열이라고 합니다.
문자열이 입력되면 해당 문자열이 회문 문자열이면 "YES", 회문 문자열이 아니면 “NO"를 출력 하는 프로그램을 작성하세요. 단 회문을 검사할 때 대소문자를 구분하지 않습니다.

▣ 입력설명
첫 줄에 정수 길이 100을 넘지 않는 공백이 없는 문자열이 주어집니다.

▣ 출력설명
첫 번째 줄에 회문 문자열인지의 결과를 YES 또는 NO로 출력합니다.

▣ 입출력 예

input	output
goooG	YES
goooGg	NO

풀이

const palindrome = (str) => {
  let s = str.toLowerCase();
  let a = [];
  for (let i = 0; i < str.length; i++) {
    a.unshift(s[i]);
  }
  if (a.join('') === s) return 'YES';
  return 'NO';
};

let str = 'goooG';
console.log(palindrome(str)); // YES

• 받은 문자열을 toLowerCase() 를 사용하여 소문자 형태로 변환한다.
• 받아온 문자열을 for 으로 돌면서 새로운 배열 a 안에 반대로 입력시킨 후 비교했다.
• 배열을 새로 만들고, 다시 join() 으로 합치는 과정없이 손쉽게 비교할 방법을 찾아보자. 🤔

✍️ 다른풀이)

const palindrome = (str) => {
  let s = str.toLowerCase();
  let len = s.length;
  let a = '';
  for (let i = 0; i < len; i++) {
    if (s[i] === s[len - 1 - i]) { // 1)
      a += s[i];
    }
  }
  return s === a ? 'YES' : 'NO'; // 2)
};

let str = 'goooGg';
console.log(palindrome(str)); // NO

• 받은 문자열을 toLowerCase() 를 사용하여 소문자 형태로 변환한다.
• 1) 문자열을 돌면서 문자열의 반대와 일치하는지 확인한 후 맞다면 a 에 입력시킨다.
• 2) 모든 문자열이 맞다면 'YES' 를 출력하게 한다.

✍️ solution

function solution(s){
  let answer="YES";
  s=s.toLowerCase();
  let len=s.length;
  for(let i=0; i<Math.floor(len/2); i++){
    if(s[i]!=s[len-i-1]) return "NO";
  }
  return answer;
}

let str="goooG";
console.log(solution(str)); // YES

• 반복문을 돌면서 즉시 관찰한다. 같지 않으면 곧바로 'NO' 를 리턴시킨다. 😀

---

3. 유효한 팰린드롬

문제 설명

앞에서 읽을 때나 뒤에서 읽을 때나 같은 문자열을 팰린드롬이라고 합니다. 문자열이 입력되면 해당 문자열이 팰린드롬이면 "YES", 아니면 “NO"를 출력하는 프로그램을 작성하세요. 단 회문을 검사할 때 알파벳만 가지고 회문을 검사하며, 대소문자를 구분하지 않습니다. 알파벳 이외의 문자들은 무시합니다.

▣ 입력설명
첫 줄에 정수 길이 100을 넘지 않는 공백이 없는 문자열이 주어집니다.

▣ 출력설명
첫 번째 줄에 팰린드롬인지의 결과를 YES 또는 NO로 출력합니다.

▣ 입출력 예

input	output
found7, time: study; Yduts; emit, 7Dnuof	YES
found7, time: study; Yduts; emit, 7Dnuof999	NO

풀이

const palindrome = (str) => {
  const s = str.toLowerCase().replace(/[^a-z]/g, ''); // 1)
  const reversedStr = s.split('').reverse().join(''); // 2)
  console.log(s); // foundtimestudyydutsemitdnuof
  console.log(reversedStr); // foundtimestudyydutsemitdnuof
  if (reversedStr === s) {
    return 'YES';
  } else {
    return 'NO';
  }
};
let str = 'found7, time: study; Yduts; emit, 7Dnuof';
console.log(palindrome(str)); // YES

• 1) 받아온 문자를 소문자로 변환하고 정규식 표현과 replace 메서드를 활용해서 영문자를 제외한 문자는 '' 로 처리한다.
• 2) 문자를 뒤집자 !
• 소문자로 변환, 영문자가 아닌 문자는 비교대상에서 제외, 이렇게 해서 받아온 문자가 유효한 팰린드롬인지 확인할 수 있다. 😀

• 📌 replace()
  
  - 첫번째 매개변수로는 문자열 또는 일반적으로 정규 표현식을 받는다.
  - 두번째 매개변수로는 문자열 또는 함수일 수 있다.
  - 메서드는 호출된 String 객체를 바꾸지 않는다. 단순히 새로운 문자열을 리턴한다.

  const re = /a/             // --a 가 있는 문자열
  const re = /a/i             //  --a 가 있는 문자열, 대소문자 구분 안함
  const re = /apple/          //  -- apple가 있는 문자열
  const re = /[a-z]/          //  -- a~z 사이의 모든 문자
  const re = /[a-zA-Z0-9]/    //  -- a~z, A~Z 0~9 사이의 모든 문자
  const re = /[a-z]|[0-9]/    //  -- a~z 혹은 0~9사이의 문자
  const re = /a|b|c/          //  --  a 혹은 b 혹은 c인 문자
  const re = /[^a-z]/         //  -- a~z까지의 문자가 아닌 문자("^" 부정)
  const re = /^[a-z]/         //  -- 문자의 처음이 a~z로 시작되는 문장
  const re = /[a-z]$/         //  -- 문자가 a~z로 끝남

• const s = str.toLowerCase().replace(/[^a-z]/g, '');
  → a~z 사이의 모든 문자가 아닌 문자를 전역으로 찾아서 ''로 대체한다. 🧐
  만약 g 를 생략하면 가장 처음 발견된 문자만을 '' 로 대체할 것이다.
  

found, time: study; yduts; emit, 7dnuof // 가장 처음으로 찾아진 문자 '7'만 대체
found7, time: study; Yduts; emit, 7Dnuof // 기존 문자열

• 📌 내장 함수들을 사용해 문자열 반전하기

1. split() 메서드로 문자열을 부분 문자열(substring)로 구분해 문자열 객체를 여러 개의 문자열로 이루어진 배열로 분할한다.
2. reverse() 메서드는 배열을 반전한다.
3. join() 메서드로 배열의 모든 요소를 문자열로 결합한다.

✍️ solution

solution
function solution(s) {
  let answer = 'YES';
  s = s.toLowerCase().replace(/[^a-z]/g, '');
  if (s.split('').reverse().join('') !== s) return 'NO';
  return answer;
}

let str = 'found7, time: study; Yduts; emit, 7Dnuof';
console.log(solution(str));

---

4. 숫자만 추출

문제 설명

문자와 숫자가 섞여있는 문자열이 주어지면 그 중 숫자만 추출하여 그 순서대로 자연수를 만듭니다.
만약“tge0a1h205er”에서 숫자만 추출하면 0, 1, 2, 0, 5이고 이것을 자연수를 만들면 1205 이 됩니다. 추출하여 만들어지는 자연수는 100,000,000을 넘지 않습니다.

▣ 입력설명
첫 줄에 숫자가 썩인 문자열이 주어집니다. 문자열의 길이는 50을 넘지 않습니다.

▣ 출력설명
첫 줄에 자연수를 출력합니다.

▣ 입출력 예

input	output
g0en2T0s8eSoft	208
goooGg	NO

풀이

const onlyNum = (str) => {
  const answer = parseInt(str.replace(/[a-zA-Z]/g, '')); // 1)
  return answer;
};
let str = 'g0en2T0s8eSoft';
console.log(onlyNum(str)); // 208

• 1) replace() 메서드를 통해서 문자열을 배제한 숫자만 추출해낸다.
• parseInt() 메서드를 사용해서 자연수를 얻어낸다.
  +) 만약 문자숫자 외에 특수기호 등이 오더라도 정규 표현식을 통해 숫자만 추출한 뒤 자연수를 얻어낼 수 있을 것이라고 생각했다. 🧐

✍️ solution

function solution(str) {
  let answer = '';
  for (let x of str) { // 1)
    if (!isNaN(x)) answer += x; // 2)
  }
  return parseInt(answer); // 3)
}

let str = 'g0en2T0s8eSoft';
console.log(solution(str));

• 1) for of 문을 돌려서 받아온 문자역 str의 키 값을 얻어낸다.
• 2) if 문을 통해 !isNaN(x) 에서 숫자일 경우 변수 answer 에 추가한다.
• 3) 최종 answer 문에서 자연수만 추출한다.

---