1. Understand the problem

  • 문제를 자신의 방식으로 다시 말할 수 있는지?
  • 문제에 들어가는 입력 데이터는 무엇인지?
  • 해결책에서 얻을 수 있는 결과는 무엇인지?
  • 문제를 해결할 충분한 정보를 가지고 있는지?
  • 함수나 변수 등의 이름은 어떻게 정할 것인가?

2. Explore examples

  • 간단한 예제로 시작하기
  • 더 복잡한 예제 진행하기
  • 빈 입력값을 가진 예제로 테스트하기
  • 잘못된 입력값을 가진 예제로 테스트하기

3. Break it down

  • 수행해야 할 단계를 명시적으로 기록하기

4. Solve or Simplify

  • 문제를 해결하거나 더 간단한 문제 해결하기

5. Look back and Refactor

  • 결과를 확인할 수 있는지?
  • 결과를 다르게 할 수 있는지?
  • 한번에 코드를 이해할 수 있는지?
  • 다른 문제에서도 결과값이나 함수를 사용할 수 있는지?
  • 수행 시간이 적절한지?
  • 다른 방법으로 문제를 해결할 수 있는지?
  • 다른 사람들은 이 문제를 어떻게 풀었는지?

제출 코드

function solution(answers) {
  let matchCount = new Object();
  const supoza1 = [1, 2, 3, 4, 5];
  const supoza2 = [2, 1, 2, 3, 2, 4, 2, 5];
  const supoza3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
  for (let i = 0; i < answers.length; i++) {
    let order1 = i % supoza1.length;
    let order2 = i % supoza2.length;
    let order3 = i % supoza3.length;

    if (answers[i] === supoza1[order1]) {
      matchCount[1] = ++matchCount[1] || 1;
    }

    if (answers[i] === supoza2[order2]) {
      matchCount[2] = ++matchCount[2] || 1;
    }

    if (answers[i] === supoza3[order3]) {
      matchCount[3] = ++matchCount[3] || 1;
    }
  }
  let result = whoIsBest(matchCount);
  return result;
}

function whoIsBest(matchCount) {
  let result = new Array();
  let max = Math.max(...Object.values(matchCount));
  for (const [key, value] of Object.entries(matchCount)) {
    if (value === max) {
      result = result.concat(Number.parseInt(key));
    }
  }
  result.sort();
  return result;
}

수포자가 가진 배열 인덱스에 answers 배열 인덱스를 맞추기 위해 나머지 연산(%)을 사용하였습니다.

    let order1 = i % supoza1.length;
    let order2 = i % supoza2.length;
    let order3 = i % supoza3.length;

정답이라면 matchCount Object에 수포자에 해당되는 번호를 key로 하고

1을 더하거나 key가 없을 때는 1로 초기화합니다. 

    if (answers[i] === supoza1[order1]) {
      matchCount[1] = ++matchCount[1] || 1;
    }

whoIsBest 함수는 matchCount Object를 받아 결과값(ex [2,3])을 반환합니다.

function whoIsBest(matchCount) {
  let result = new Array();
  let max = Math.max(...Object.values(matchCount));
  for (const [key, value] of Object.entries(matchCount)) {
    if (value === max) {
      result = result.concat(Number.parseInt(key));
    }
  }
  result.sort();
  return result;
}

Object 가 가진 value 들 중에 가장 큰 값을 max로 선정합니다.

let max = Math.max(...Object.values(matchCount));

Object.entries method를 사용해 key와 value를 얻어내어 

value가 max와 같다면 key를 Number로 바꾸어 result 배열에 추가합니다.

for (const [key, value] of Object.entries(matchCount)) {
    if (value === max) {
      result = result.concat(Number.parseInt(key));
    }
  }

 

Solution with using filter

배열 filter 함수를 사용한 방법

function solution2(answers) {
  let matchCount = new Object();
  const supoza1 = [1, 2, 3, 4, 5];
  const supoza2 = [2, 1, 2, 3, 2, 4, 2, 5];
  const supoza3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];

  matchCount[1] = answers.filter(
    (answer, index) => answer === supoza1[index % supoza1.length]
  ).length;
  matchCount[2] = answers.filter(
    (answer, index) => answer === supoza2[index % supoza2.length]
  ).length;

  matchCount[3] = answers.filter(
    (answer, index) => answer === supoza3[index % supoza3.length]
  ).length;
 
  let result = whoIsBest(matchCount);
  return result;
}

Solution not using Object and fuction whoIsBest

Object와 whoIsBest 메소드를 사용하지 않은 방법

 

function solution(answers) {
  let result = new Array();
  const supoza1 = [1, 2, 3, 4, 5];
  const supoza2 = [2, 1, 2, 3, 2, 4, 2, 5];
  const supoza3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];

  const match1 = answers.filter(
    (answer, index) => answer === supoza1[index % supoza1.length]
  ).length;
  const match2 = answers.filter(
    (answer, index) => answer === supoza2[index % supoza2.length]
  ).length;
  const match3 = answers.filter(
    (answer, index) => answer === supoza3[index % supoza3.length]
  ).length;
  
  let max = Math.max(match1, match2, match3);
  
  [match1, match2, match3].forEach((match, index) => {
    if (match === max) {
      result = result.concat(index + 1);
    }
  });
  
  return result;
}

'코딩 테스트 > 프로그래머스' 카테고리의 다른 글

LEVEL 1 크레인 인형뽑기 게임  (0) 2020.07.02

What does better mean?

1. Faster?

2. Less memory-intensive?

3. More readable?

 

The Problem with Time

1. Different machines will record different times

2. The same machine will record different times

 

다른 performance 측정법

Counting Operations이 있지만 연산자를 세는 방법은

힘들고 시간이 오래 걸린다.

 

Big O 정의

간단한 연산들은 컴퓨터가 최대 f(n)번 해야한다면 알고리즘은 O(f(n))이다.

f(n)은 상수형, 선형 등 형태가 다양하다.

 

1. f(n)이 2n일 때 상수는 무시되고 O(n)이 된다.

2. f(n)의 최고차항만 남긴다.

 

O(1)

O(n)과 같이 보이지만 i가 10 이후부터 연산 개수가 증가하지 않기 때문에 O(1)이다!!

function logAtMost10(n) {
  for (var i = 1; i <= Math.min(n, 10); i++) {
    console.log(i);
  }
}

 

Space Complexity

boolean, number, undefined, null은 상수이다.

String 공간 복잡도는 O(n)이다.

참조형은 일반적으로 O(n)이고 n은 배열 길이나 object key 개수이다.

+ Recent posts