algorithm challenge__24.03.06

석원·2024년 3월 6일

algorithm_challenge

목록 보기

3/3

프로그래머스 2문제와 백준 1문제를 진행 했습니다.

가장 가까운 같은 글자

/**
 * 
 * @param {string} s 입력받은 문자열
 * @returns {number[]} 문자열에 단어가 처음 나온경우 -1 아닌경우는 차이값
 * 
 * 문자열을 반복문을 돌리면서 array에 존재하는지 확인하면서 넣어줍니다.
 * 존재 하지 않은 경우 answer array에 -1을 push
 * 존재하는 경우 lastIndexOf를 이용하여 마지막 같은 문자열의 index를 찾고 현재 문자 index 에서 찾은 index를 빼서 push
 */
const solution = (s) => {
  const answer = [];
  const arr = [];

  for (let i = 0 ; i < s.length; i++) {
    if(stack.indexOf(s[i]) === -1) {
      answer.push(-1);
    } else {
      answer.push(i - stack.lastIndexOf(s[i]));
    }
    arr.push(s[i]);
  }
  return answer;
}


solution();

lastIndexOf() 메서드를 활용해서 쉽게 해결할 수 있었다.

과일장수

// 첫번째 풀이 테스트케이스 11~15 시간초과
const incorrect_solution = (k, m, score) => {
  let answer = 0;

  score.sort((a, b) => b- a);
    
    
    while(score.length) {
        const temp = score.splice(0, m);
        if(temp.length === m) {
          answer += m * temp[temp.length-1]
        }
    }
 
  return answer;
}

function correct_solution(k, m, score) {
  let answer = 0;

  score.sort((a, b)=> b-a)

  for(var i=0; i<score.length; i+=m) {
      let temp = score.slice(i, i+m)

      if(temp.length == m) {
          answer += m * temp[temp.length-1];
      }
  }

  return answer;
}


solution();

과일 장수 문제는 incorrect_solution에서 처럼 splice로 m (상자에 들어갈 갯수 ) 씩 잘라주면서 새로운 배열을 만들고 filter(), map(), reduce()를 사용해서 결과를 구했었는데, 시간초과가 발생했다. 그래서 자름과 동시에 answer에 누적을 해주는 방식으로도 코드를 수정해봤는데 같은 테스트케이스에서 시간초과가 발생했다.
그래서 다른분의 답을 참고했는데, 정렬 후 반복문 도는 부분에서 차이가 발생했는데, 이부분은 내일 좀 더 자세히 보고 코멘트를 다시 달도록 하겠다.

24.03.07 추가 코멘트
splice 메서드가 배열을 자르고 남은 요소들을 이어붙이는 과정에서 시간복잡도가 증가하게 됨을 알게되었다.

10815

const fs = require('fs');
// const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const input = fs.readFileSync('./10815.txt').toString().split('\n');

const solution = () => {
  const result = []
  const numberMap = new Map();
  input[1].split(' ').forEach(strN => {
    numberMap.set(Number(strN), "");
  })

  input[3].split(' ').forEach(strN => {
    if(numberMap.has(Number(strN))) {
      result.push(1);
    }else {
      result.push(0)
    }
  })
  
  console.log(result.join(' '));
}


solution();

입력으로 주어지는 2번째 라인과 4번째 라인을 활용하여 문제를 해결할 수 있었다.
2번째 라인을 기준으로 4번째 라인에 주어진 숫자들이 존재한다면 1을 그렇지 않다면 0을 반환해서
1 0 1 0 0 1 과 같은 문자열을 출력하는 문제 였다.
Map을 활용하여 2번째 라인의 데이터를 저장해두고, 4번째 라인 값을 확인하면서 result 배열에 조건에 맞게 값을 추가 해준후 join(' ')을 사용하여 문자열로 출력 되도록 작성했다.

석원

이전 포스트

algorithm challenge__24.03.06