[Level2] 14. 65 ~ 67

in 코딩테스트 on 프로그래머스




연습문제 끝!! 내일부터 자료구조 👋👋👋


65. 올바른 괄호

프로그래머스 

function solution(s) {
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    if (s[i] === ")" && stack[stack.length - 1] === "(") stack.pop();
    else stack.push(s[i]);
  }
  return stack.length ? false : true;
}

예전에 괄호 문제를 스택으로 푸는 경우를 본 적이 있어서 비교적 쉽게 접근하고 풀 수 있었다.!


best 풀이

function is_pair(s){
  var result = s.match(/(\(|\))/g);
  return result[0] == '(' && result.length % 2 == 0 ? true : false
}

오우 정규식으로 풀어내셨다.
문자열 문제는 best 풀이에 항상 정규식이 하나는 들어가있는거 같다.
정규식 꾸준히 해야하는 이유~~


66. 짝지어 제거하기

programmers 

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

  return stack.length ? 0 : 1;
}

일부러 그런게 아닌데 앞 문제랑 풀이가 완전히 같다…
정규식으로 풀어보고자 했는데 동일한 문자를 묶는 법을 모르겠어서 stack으로 구현했다.
best 풀이도 stack이므로 아쉽지만 정규식은 넘어가자!



67. 영어 끝말잇기

programmers

잘못 접근한 방식

function solution(n, words) {
  let idx;
  let k = 0;
  for (let i = 0; i < words.length; i++) {
    // 끝말잇기 틀린 경우
    if (i !== 0 && words[i][0] !== words[i - 1][words[i - 1].length - 1]) {
      idx = i + 1;
      return [idx % n === 0 ? n : idx % n, Math.ceil(idx / n)];
    }
    // 중복 단어 말한 경우
    k = 0;
    for (let j = i + 1; j < words.length; j++) {
      k++;
      if (words[i] === words[j]) {
        idx = i + k + 1;
        console.log(i, k, idx); // 0 4 5
        return [idx % n === 0 ? n : idx % n, Math.ceil(idx / n)];
      }
    }
  }
  return [0, 0];
}

console.log(solution(2, ["abb", "baa", "ccc", "cda", "abb"]));

우선 이 풀이는 틀린 풀이이다.!
지금까지 풀어온 문제 중 나름 가장 애를 먹었다…
19번 테스트케이스에서 자꾸 걸렸었던 것…!
질문하기를 통해 다른사람의 조언을 들으니 테스트 예시처럼 틀린 단어도 있고, 중복 단어도 있을 때,
위의 코드처럼 풀면 abb 순회시 다른 것을 말한 ccc 보다 중복 단어인 abb가 먼저 오류로 발견 되는 문제였다.
따라서 중복문자를 찾을 때 오른쪽 문자를 순회하는 것이 아닌 왼쪽 문자를 순회하는 것으로 코드를 변경했다.

function solution(n, words) {
  let idx;
  for (let i = 0; i < words.length; i++) {
    // 끝말잇기 틀린 경우
    if (i !== 0 && words[i][0] !== words[i - 1][words[i - 1].length - 1]) {
      idx = i + 1;
      return [idx % n === 0 ? n : idx % n, Math.ceil(idx / n)];
    }
    // 중복 단어 말한 경우
    for (let j = i - 1; j >= 0; j--) {
      if (words[i] === words[j]) {
        idx = i + 1;
        return [idx % n === 0 ? n : idx % n, Math.ceil(idx / n)];
      }
    }
  }
  return [0, 0];
}

console.log(solution(2, ["abb", "baa", "ccc", "cda", "abb"])); //[1,2]

위와 같이 코드를 수정하니 19번 케이스도 무사히 통과하였다.!
사실 여기서도 애를 먹었는데 j를 평소 감소 for문을 쓸 때처럼 j > 0 까지 했다가, 처음 문자를 검색하지 않아서 오류가 났었다.
나중에야 깨닫고 후다닥 고치니 다행히 해결이 됐다 ^__^
이 한문제를 푸는데 꽤나 오랜 시간이 들어서 모든 테스트케이스를 통과했을 때 정말 뿌듯했다!!🤩🤩




best 풀이

function solution(n, words) {
    let answer = 0;
    words.reduce((prev, now, idx) => {
        answer = answer || ((words.slice(0, idx).indexOf(now) !== -1 || prev !== now[0]) ? idx : answer);
        return now[now.length-1];
    }, "")

    return answer ? [answer%n+1, Math.floor(answer/n)+1] : [0,0];
}

이중 for문을 쓰지 않고도 풀 수 있다니 놀랍다…

function solution(n, words) {

    var fail_i = -1;
    for(var i = 1; i < words.length; i++){
        var val = words[i];
        // 전단계의 끝말과 현단계 첫말이 다를 경우
        if(words[i-1].substring(words[i-1].length-1) != val.substring(0, 1)) {
            fail_i = i;
            break;
        } 
        // indexOf 함수는 첫번째로 값이 맞는 인덱스만 반환하므로
        // 현재 인덱스와 맞지 않을 경우 중복된 값
        if(words.indexOf(val) != i) {
            fail_i = i;
            break;
        }
    }

    if(fail_i == -1) return [0,0];

    var no = fail_i%n + 1;
    var turn = Math.floor(fail_i/n) + 1; 

    return [no, turn];
}

위의 베스트 풀이와 같은 맥락인데 내가 좀 더 이해하기 쉬운 코드여서 가져왔다.
이중 for문을 돌지 않을 수 있었던 이유가 indexOf 함수를 사용했기 때문이다.
indexOf 는 첫번째로 값이 맞는 인덱스만 반환하기 때문에 현재 인덱스와 다른 인덱스를 반환한다면 그건 중복됐다는 원리.
기억하고 지나가자!