69. 가장 큰 수 Javascript

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

 

 

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요
• 주어진 자료는 무엇인가?
   - 0 또는 양의 정수가 담긴 배열 numbers
• 조건은 무엇인가?
   - numbers의 길이는 1 이상 100,000 이하입니다.
   - numbers의 원소는 0 이상 1,000 이하입니다. 
   - 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

2. 계획

• 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
   - 버블정렬
   - sort()
• 비슷한 문제를 풀어본 적이 있다면 그 것을 활용할 수 있는가?
   - 버블 정렬 구현한 코드를 활용할 수 있을것같다.

 

첫번째 풀이

1. 주어진 numbers를 문자열로 바꾼다.
2. 배열을 순회하면서 현재 인덱스에 그 다음 인덱스를 앞에 붙였을때와 뒤에 붙였을때의 크기를 비교한다.
3. 작은 수를 배열 맨 앞으로 가게끔 한다.
4. 새로 정렬된 배열을 뒤집는다
5. 이 숫자들을 join해서 스트링으로 만든다.

 

두번째 풀이

1. 주어진 숫자가 전부 0인 경우가 있다. 이럴때 예외처리를 해준다
2. every를 사용해서 배열의 요소가 모두 0이면 '0'을 리턴한다.
3. 주어진 숫자 배열을 정렬을 한다.
4. 숫자 a와 b가 주어졌을때 ba - ab를 한 값이 음수이면 a를 리턴하고 양수이면 b를 리턴한다.
5. 이렇게 정렬된 배열을 join해서 스트링으로 만든다.

 

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

첫번째 풀이

const solution = (numbers) => {
  bubble sort and reverse
  for (i = 0; i < numbers.length - 1; i++) {
    for (j = i + 1; j < numbers.length; j++) {
      if (Number.parseInt(`${numbers[i]}${numbers[j]}`) > Number.parseInt(`${numbers[j]}${numbers[i]}`)) {
        const temp = numbers[j];
        numbers[j] = numbers[i];
        numbers[i] = temp;
      }
    }
  }
  return numbers.reverse().join('');
};

test('findNumber', () => {
  expect(solution([1, 2])).toEqual('21');
  expect(solution([6, 10, 2])).toEqual("6210");
  expect(solution([101, 10, 232, 23])).toEqual('2323210110');
});

test('findNumber', () => {
  expect(solution([3, 30, 34, 5, 9])).toEqual('9534330');
});

test('findNumber', () => {
  expect(solution([3, 55, 51, 5, 9])).toEqual('9555513');
  expect(solution([3, 56, 51, 5, 9])).toEqual('9565513');
  expect(solution([3, 53, 51, 5, 9])).toEqual('9553513');
  expect(solution([3, 56, 579, 5, 9])).toEqual('95795653');
});

 

 

 

두번째 풀이

const solution = (numbers) => {
  if (numbers.every(cur => cur === 0)) return '0'; 
  const number = numbers.sort((a, b) => {
    return `${b}${a}` - `${a}${b}`
  });
  return number.join('');
};

 

 

이 문제를 풀기 전에 버블정렬을 코드로 구현해봤었는데 마침 코테 문제가 버블 정렬을 사용해서 해결할 수 있는 문제였다.
그래서 버블 정렬을 사용해서 이 문제를 해결 할 수 있었다.
이 문제를 풀면서 버블정렬이 정말 효율성이 없다는 것을 몸소 느낄 수 있었다.
배열의 길이가 길어지는 경우 시간 초과가 떴다.

그래서 다른 효율성이 좋은 정렬 방법을 사용해보려고 찾아보다가 
merge sort를 사용해보려고 했는데 숫자를 크기대로 정렬 시킨다음에 그것을 반으로 나누고 정렬한다는게 
이 문제를 풀기 위한 방법이 아니라 생각해서 다른 방법을 찾아보았다.

그러다가 생각난것이 sort를 사용해서 간단하게 풀 수 있겠다는 생각이 들었고 
현재 인덱스의 수에 그 다음 인덱스의 수를 앞에 붙인것과 뒤에 붙인것의 크기에 따라서 정렬 순서가 바뀐다는 것을 활용해서 (이 방법은 버블 정렬에서도 사용한 것) 해결 할 수 있었다.

다양한 방법으로 문제를 해결해보니까 좋았는데 마침 버블 정렬을 배운날 관련된 코테 문제를 풀게되어서 신기하고 재밌었다.