[Programmers]롤케이크 자르기/JS

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

접근방법

배열을 잘라서 두 배열에 있는 원소 종류가 몇 개인지 구한 다음 같으면 answer + 1 해주면 되겠구나.

어쩐지 단순하다 싶었다.. 

오답

function solution(topping) {
  var answer = 0;

  for (let i = 1; i < topping.length; i++) {
    let front = topping.slice(0, i);
    let back = topping.slice(i, topping.length);
    let frontResult = front.filter((value, index)=>front.indexOf(value)===index);
    let backResult =back.filter((value, index)=>back.indexOf(value)===index);    
    if(frontResult.length == backResult.length) answer++;

  }

  return answer;
}

위의 코드는 filter 함수를 이용한 코드이다.

배열을 잘라서 앞 뒤 배열의 토핑 종류가 몇 개인지를 구하는건데

시간초과..ㅠㅠ 

1<=topping의 길이<=1,000,000

1<=topping의 원소<=10,000

조건을 보니까 이렇게 하면 시간이 엄청 오래걸릴거 같긴하넹..

function solution(topping) {
  var answer = 0;

  for (let i = 1; i < topping.length; i++) {
    let front = topping.slice(0, i);
    let back = topping.slice(i, topping.length);
    let frontResult = [...new Set(front)];
    let backResult = [...new Set(back)];   
    if(frontResult.length == backResult.length) answer++;

  }

  return answer;
}

혹시 Set으로 풀면 되지 않을까?라는 희망을 가지고 Set으로도 풀어봤지만

똑같이 시간 초과.. 여기서부터 멘탈이 나갔다..

도저히 고민해봐도 어떻게 풀어야할지 감이 안와서 결국 구글링해봤다.

 

map 쓰는 사람들이 많던데 나는 위에서 Set을 사용해서 그런지 Set을 사용한 코드가 더 끌렸다.

정답코드

function solution(topping) {
  var answer = 0;
  const len = topping.length;
  const frontCnt = Array(len).fill(0);
  const backCnt = Array(len).fill(0);

  const frontSet = new Set();
  const backSet = new Set();

  for (let i = 0; i < len; i++) {
    frontSet.add(topping[i]);
    backSet.add(topping[len - 1 - i]);
    frontCnt[i] = frontSet.size;
    backCnt[len - 1 - i] = backSet.size;
  }

  for (let i = 0; i < len - 1; i++) {
    if (frontCnt[i] === backCnt[i + 1]) answer++;
  }

  return answer;
}

frontCnt와 backCnt는 토핑의 종류가 몇 개인지를 저장한다.

frontCnt는 앞에서부터, backCnt는 뒤에서부터 개수를 세서 저장한다.

frontSet과 backSet은 중복을 제거해서 개수를 세기 위해서 사용한다.

 

ex) topping[1, 2, 1, 3, 1, 4, 1, 2]일때

frontCnt[1, 2, 2, 3, 3, 4, 4, 4]

backCnt[4, 4, 4, 4, 3, 3, 2, 1] => frontCnt[3] == backCnt[4], frontCnt[4]==backCnt[5]이므로 answer은 2!!

 

첫번째 for문을 다 돌고 나면

두번째 for문에서 frontCnt[i]와 backCnt[i+1]의 값이 같으면 

공평하게 나눠진걸로 간주해서 answer++를 해준다.

 

 

시간복잡도를 생각해야했던 문제이다..ㅠ
내가 제일 못하는 부분이라서 어려웠당...