[프로그래머스] 가장 가까운 글자, 문자열 나누기 (feat. JavaScript)

---

가장 가까운 글자

문제 설명

입출력 예

본인의 답

function solution(s) {
    var answer = [];
    for(let i=0; i<s.length; i++){
        var str = s[i]
        if(s.indexOf(s[i])===i){
            answer.push(-1)
        }
     for(let j=i-1; j>=0; j--){
         if(s[j] === str){
             answer.push(i-j)
             break;
         }
     }
    }
    return answer;
}

2중 for문으로 해결했지만 시간복잡도가 n^2라 좋지 않은 풀이라 생각이 되었다.

다른 사람의 풀이를 몇 개 봤는데, 대부분 map+spread를 사용하거나 객체, 배열, for문을 이용해 풀었다.

 

map과 spread 연산자를 이용한 풀이

function solution(s) {
    const hash={};
    return [...s].map((v,i)=>{
        let result = hash[v] !== undefined ? i - hash[v] : -1;
        hash[v] = i;
        return result;
    });
}
    //[b,a,n,a,n,a] 
    //result = [-1], hash={b:0}
    //result = [-1,-1], hash={b:0, a:1}
    //result = [-1,-1,-1], hash={b:0, a:1, n:2}
    //result = [-1,-1,-1,2], hash={b:0, a:3, n:2}
    //result = [-1,-1,-1,2,2], hash={b:0, a:3, n:4}
    //result = [-1,-1,-1,2,2,2], hash={b:0, a:5, n:4}


const solution = (s) =>
  [...s].map((char, i) => {
    const count = s.slice(0, i).lastIndexOf(char);
    return count < 0 ? count : i - count;
  });
  
  //[b,a,n,a,n,a]
  //slice(0,0) => 빈배열 => count = -1 [-1]
  //slice(0,1) => [b].lastIndexOf(a) => -1 [-1,-1]
  //slice(0,2) => [b,a].lastIndexOf(n) => -1 [-1,-1,-1]
  //slice(0,3) => [b,a,n].lastIndexOf(a) => 1 return 2 [-1,-1,-1,2]
  //slice(0,4) => [b,a,n,a].lastIndexOf(n) => 1 return 2 [-1,-1,-1,2,2]
  //slice(0,5) => [b,a,n,a,n].lastIndexOf(a) => 1 return 2 [-1,-1,-1,2,2,2]

객체와 배열 + for문

function solution(s) {
  const obj = {};
  const answer = [];
  for (let i = 0; i < s.length; i++) {
    if (obj[s[i]] !== null) answer[i] = i - obj[s[i]];
    else answer[i] = -1;
    obj[s[i]] = i;
  }
  return answer;
}

//s = "banana";
// answer = [-1], obj = {b:0}
// answer = [-1,-1], obj = {b:0, a:1}
// answer = [-1,-1,-1], obj = {b:0, a:1, n:2}
// answer = [-1,-1,-1,2], obj = {b:0, a:3, n:2}
// answer = [-1,-1,-1,2,2], obj = {b:0, a:3, n:4}
// answer = [-1,-1,-1,2,2,2], obj = {b:0, a:5, n:4}

---

문자열 나누기

문제 설명

입출력 예

 

본인의 답

function solution(s) {
    var count = 0;
    var answer = 0;
    var result = 0;
    var str = ""
    for(let i=0; i<s.length; i++){
        if(!str){
            str = s[i];
        }
        if(str!==s[i])
            answer++;
         else {
            count++;
        }
       if(count===answer){
            result++;
            count =0;
            answer=0;
            str = "";
        }
   
    }
     if(str) result++;
    return result;
}

처음 str에 빈 문자열을 주고, if문으로 첫 글자에 씌워주면 자연스럽게 answer=1이 될텐데,

이 과정없이 처음부터 answer=1을 주고 count=1이 되면 배열을 자르고, 자른 배열 외의 부분을 가지고 풀 수 있지 않을까 해서 그렇게 풀어보려다가 오래 걸렸다.

문자열을 빼낸 뒤에 다시 str을 빈 문자열로 바꿔주면서 자연스럽게 다음에 빼낼 문자열을 시작할 수 있도록 했다.

 

내가 처음 했던 생각이랑 비슷한 풀이가 있나 봤는데 이걸 재귀로 푸신분이 계셔서 가져와봤다 ㄷㄷㄷㄷ...

 

재귀를 이용한 풀이

function solution(s, count=0) {
    if(!s) return count
    let [first, ...rest] = s.split("")
    let countSame = 1
    let countInSame = 0
    let i=0
    for(; i<rest.length; i++){
        if(rest[i] === first) countSame++
        else countInSame++
        if(countSame === countInSame) break
    }
    return solution(rest.slice(i+1).join(""), count+1)
}

비교대상인 첫 글자와 나머지로 구분을 하는게 키 포인트인 거 같다. spread 연산자를 이렇게 사용하는 건 처음 본 것 같다.

마지막에 join으로 다시 string으로 만들어준 다음 count를 하나 올려준 모습