알고리즘/프로그래머스 - JS

[프로그래머스] level.1 덧칠하기

개발자성장기 2023. 5. 16. 19:57
반응형

 

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

나의 풀이 

 

틀린 풀이

너무 단순하게 생각하고 풀었다.  

// 잘못된 풀이
// 예제는 통과하지만 필요없는 구역도 칠해버림

function solution(n, m, section) {
  // 1. early return 먼저 제거

  // 1) 롤러의 길이가 1이면 result = n 이 된다.
  if (m === 1) return n;

  // 2. 나머지 경우


  // 1) section에서 첫 번째 index와 마지막 index의 숫자를 가져온다.
  const firstIndexNum = section[0];
  const lastIndexNum = section.at(-1);
  let length = lastIndexNum - firstIndexNum + 1;
  let result = 0;
  while (length > 0) {
    length -= m;
    result += 1;
  }
  return result;
}

위 코드를 이런식으로 동작하게 된다.  

이 코드의 문제점은 페인트를 칠해야할 구역이 없어도 result가 카운트가 된다. 

즉 위 그림에서 10,11,12,13이 파란구역이라도 칠하게되어서 불필요하게 result가 카운트 된다. 

 

 

풀이 1)

 

이 풀이는  매번 칠해야 할 롤러를 미리 만들고 롤러에 해당되는 숫자가 section에 있으면 filter를 통해 제외시킨다.

하지만 이렇게 풀면 통과는 되지만 처리시간이 엄청나다.

왜냐하면 매번 removed 배열을 만들고 includes를 통해 같은 숫자가 있는지  확인해야하기때문이다. 

 

// 풀이 1
// 처리시간이 너무 오래 걸림
function solution(n, m, section) {
  // 1. early return 먼저 제거

  // 1) 롤러의 길이가 1이면 result = section.length 이 된다.
  if (m === 1) return section.length;

  let result = 0;
  while (section.length) {
    const removed = Array.from({ length: m }, (v, i) => section[0] + i);
    section = section.filter((value) => !removed.includes(value));
    result += 1;
  }
  return result;
}

 

 

엄청난 처리시간 ㄷㄷ

 

 

풀이 2)

 

시간을 단축하기위해 매번 새로운 배열을 만드는 것과 includes 메서드를 사용하지 않았다. 

그래서 이번에는 각 롤러의 마지막 숫자에 집중해보았다. 

 

예제 1을 가지고 예시를 들어보자 

 

먼저 첫 번째 롤러는 [2, 3, 4, 5] 가 된다. (m=4, section 2부터 다시 칠하기로 정한 구역)

그래서 첫 번째 롤러로 페인트 칠 하면 section중에서 2,3 구역을 칠할 수 있다. 

여기서 내가 주목한 것은 롤러의 마지막 숫자인 "5"이다. 

각 롤러의 마지막 숫자 까지 section안에 해당되는 숫자를 지우면서  result를 카운터 하면 간단하게 해결된다. 

 

즉 위 예제에서 첫 번째 롤러는 [2,3,4,5] 이기에 첫 번째 롤러의 마지막 숫자는 5이다.  

section안에 5이하 숫자는 모두 지운다.  그리고 result  + 1을 해준다. 

 

그럼 section안에는 6이 남는다.   

두 번째 롤러는 [6, 7, 8, 9] 가 된다.  따라서 마지막 숫자는 9이다. 

section안에 9이하 숫자는 모두 지우고  result + 1을 해준다. 

그럼 답 2가 나온다. 

 

 

다른 예시를 그림과 함께 보자

n = 16

m = 4

section = [2, 3, 6, 13]

result = 3

첫 번째 롤러는 m= 4이기에   [2,3,4,5] 이고 마지막 숫자는 5이기에  section안에 5이하 숫자는 모두 지우고 result + 1을 해준다 

두 번째 롤러는 [6,7,8,9] 이고 마지막 숫자는 9이다. 따라서 section안에 9이하 숫자는 모두 지우고 result + 1을 해준다. 

세 번째 롤러는 [13,14,15,16] 이고 마지막 숫자는 16이다. 따라서 section안에 16이하 숫자는 모두 지우고 result +1을 해준다. 

 

그래서 답은 3이다. 

 

 

아래는 이러한 풀이를 코드화 한 것이다. 

 

 

// 풀이 2
// 시간단축

function solution(n, m, section) {
  // 1. early return 먼저 제거
  // 1) 롤러의 길이가 1이면 result = section.length 이 된다.
  if (m === 1) return section.length;

  let result = 0;
  while (section.length) {
    const lastRollerNumber = section[0] + m - 1;
    const overIndex = section.findIndex(
      (sectionNumber) => sectionNumber > lastRollerNumber
    );
    
    //  -1은 못 찾았다는 것이고 그 뜻은 더 이상의 롤러를 필요하지않다 
    // 다시말해 마지막 페인트칠 이라는 뜻이다. 
    if (overIndex === -1) {
      result += 1;
      break;
    }
    section.splice(0, overIndex);
    result += 1;
  }
  return result;
}

 

 

 

 

다른 사람 풀이 

 

 

반응형