스터디 기록 20

문제 목록

❤️‍🔥 짝지어 제거하기

function solution(s) {
  let word = [];

  // 스택으로 넣어서 마지막과 마지막+1가 같으면 빼주기
  // 결과적으로 담아뒀던 word에 아무것도 없으면, 짝지어 제거하기가 성공된 것이므로 1리턴
  for (let i = 0; i < s.length; i++) {
    word.push(s[i]);

    if (word.length >= 2 && word.at(-1) === word.at(-2)) {
      word.pop();
      word.pop();
    }
  }
  return !word.length ? 1 : 0;
}

solution('baabaa');

스택을 이용해서 풀었다! 스택하면 예전에 했었던 햄버거 만들기밖에 생각이 안나..

function solution(s){
    var stack = [];

    for(let i = 0; i<s.length; i++){
        if(stack[stack.length-1] != s[i]){
            stack.push(s[i]);
        }
        else{
            stack.pop();
        }       
    }
    if(stack.length>0) return 0;
    else return 1;
}

동원님 코드! 다른 부분들은 거의 유사하지만 나는 애초에 넣어주고 했었는데 동원님은 지금 넣을 값하고 마지막 같이 같은지 확인해 주었다 이렇게 해 준게 훨씬 간결하고 좋아 보여서 가져왔다!

❤️‍🔥 영어 끝말잇기

❌ 실패 코드

function solution(n, words) {
  //? 앞에 말한 단어의 마지막 문자로 시작하는 단어 말하기
  //! 가장 먼저 탈락하는 사람 번호, 몇 번째 차례인지
  // 지금까지 말한 단어는 connectGame push 시켜 줘서 현재 단어가 connectGame에 있다면 탈락
  //
  let connectGame = [words[0]];
  let turn = 0;
  for (let i = 0; i < words.length; i++) {
    //? 첫번째는 바로 통과
    if (i === 0) continue;

    const before = words[i - 1];
    const now = words[i];

    //? 전에 말한 단어 사용하면 탈락
    if (connectGame.includes(now)) {
      break;
    }

    //! 현재 단어의 첫글자가 전 글자의 마지막 글자와 같은지 비교
    if (now.at(0) === before.at(-1)) {
      turn++;
      connectGame.push(words[i - 1]);
      connectGame.push(words[i]);
    }
  }

  //? [탈락 번호, 몇 번째 차례]
  //? 게임 turn이 words의 길이만큼 돌아갔다면 탈락자가 없는 것이므로 [0, 0]
  if (turn + 1 === words.length) return [0, 0];
  return (turn + 2) % n === 0
    ? [n, Math.ceil(turn / n)]
    : [(turn + 2) % n, Math.ceil(turn / n)];
}

실패했던 코드 시간초과도 아니고 그냥 실패이다... 사유는 모르겠다 일단 성공코드 먼저 보자!

⭕ 성공 코드

function solution(n, words) {
  //? 앞에 말한 단어의 마지막 문자로 시작하는 단어 말하기
  //! 가장 먼저 탈락하는 사람 번호, 몇 번째 차례인지
  // 지금까지 말한 단어는 connectGame push 시켜 줘서 현재 단어가 connectGame에 있다면 탈락
  //
  let connectGame = [words[0]];
  console.log(connectGame);
  //? 첫번째는 바로 통과
  for (let i = 1; i < words.length; i++) {
    const before = words[i - 1];
    const current = words[i];

    //! 현재 단어의 첫글자가 전 글자의 마지막 글자와 같은지 비교
    if (
      current.at(0) === before.at(-1) &&
      connectGame.indexOf(current) === -1
    ) {
      connectGame.push(current);
    } else {
      //? [탈락 번호, 몇 번째 차례]
      return [(i % n) + 1, parseInt(i / n) + 1];
    }
  }
  //? 탈락자가 없으면 [0, 0]
  return [0, 0];
}

실패코드랑 다른 점이 있다면 가장 큰 건 이미 말했던 단어라면 탈락시키는 부분이 다르다. 성공 코드에서는 indexOf를 통해서 해당 요소가 있는지 확인하였고, 실패 코드에서는 includes로 했다는 점이다... 아니면 내가 리턴 시키는 곳에서 잘못해 주었을까?,,, 나중에 처음부터 뜯어보고 다시 풀어야겠다.

/**
1. 이전에 나온 단어가 다시 나오는지
2. 직전에 나온 단어의 마지막 문자(character)가 이번에 보고 있는 단어의 첫번째 문자와 동일한지
 */
function solution(n, words) {
    let answer = [0,0];
    let last = words[0][words[0].length-1];
    let hs = new Set();

    hs.add(words[0]);
    console.log(hs)

    for (let i = 1; i < words.length; i++) {
        if (words[i][0] != last || hs.has(words[i])) { // hs배열에 word[i]를 갖고 있는지

            answer[0] = i%n+1;
            answer[1] = parseInt(i/n)+1; 
            console.log(answer[0])
            console.log(answer[1])
            break;
        }
        last = words[i][words[i].length-1];//마지막 글자 가져오기
        hs.add(words[i]);                   //hs배열에 단어 추가하기
    }
    return answer;
}
solution(3,["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"]);

동원님 코드! set에서 추가하고 has로 해당 인덱스가 있는지 확인하는 메서드를 알게 되었다! Set은 항상 중복 없애는 용도로만 사용했었는데 새로운 코드,, 굿굿

❤️‍🔥 구명보트

❌ 실패코드

function solution(people, limit) {
  // 가벼운 사람, 무거운 사람 정렬 후
  // 제일 무거운 사람 + 제일 가벼운 사람 넣어지면 shift! 해주기
  let light = [...people].sort((a, b) => a - b);
  let heavy = [...people].sort((a, b) => b - a);

  let boat = 0;

  for (let i = 0; i < heavy.length; i++) {
    // 무거운 사람, 가벼운 사람 되면 boat++ 해 주고 사람들이 보트를 탔으니 빼준다
    // 빼줬으니 다시 처음부터 비교해야 되므로 i--
    if (heavy[i] + light[i] <= limit) {
      heavy.shift();
      heavy.pop();
      light.shift();
      light.pop();
      boat++;
      i--;
    } else {
      heavy.shift();
      light.pop();
      boat++;
      i--;
    }
  }

  return boat;
}

solution([70, 80, 50], 100);

for문 안에서 shift(), pop()을 써줘서 시간초과로 실패한 코드이다. 동원님께서 스터디가 끝나고 공유해 주신 블로그를 통해서 배열 내에서의 메서드들의 시간 복잡도에 대해서 알 수 있었다. shift의 경우에는 앞의 값을 제거하고 나머지 인덱스들이 1만큼 앞으로 와야 되기 때문에 새로운 인덱스가 돼 전체 인덱스가 바뀌므로 시간복잡도가 O(N)이다!

push, pop : O(1)
shift, unshift : O(N)

참고: [시간복잡도](참고: https://parkparkpark.tistory.com/m/101)

⭕ 성공 코드

function solution(people, limit) {
  // 내림차순 정렬 후
  // 제일 무거운 사람 + 제일 가벼운 사람 넣어지면 boat++ 해주기
  let heavy = [...people].sort((a, b) => b - a);
  let boat = 0;

  console.log(heavy);
  // 투포인터로 풀기
  //  [80, 70, 50, 50]
  //!  i           j
  //?      i   j       i + j가 limit보다 작거나 같을 경우, j-- 해서 포인터 이동
  for (let i = 0, j = heavy.length - 1; i <= j; i++) {
    if (heavy[i] + heavy[j] <= limit) {
      j--;
    }
    boat++;
  }
  console.log(boat);
  return boat;
}

solution([70, 50, 80, 50], 100);

for문 내에서 선언하는 것을 두 번 하여 투포인터 개념으로 풀었다! 위에 실패코드에서는 직관적이게 풀었지만,,, 시간초과로 아쉽지만 투포인터를 해서 풀어본 건 이번이 처음이라 좋았따 ㅎㅎㅎ!!