정렬 문제를 풀어봤다
간단히 풀렸다. 저번내용을 복습하자면 문자열을 출력 할 때 일일이 console.log 하는 것이 아니라 항상 answer = '' 빈 문자열을 만들어서 거기에 출력해서 한번만 추가하자.
- 주어진 인풋값이 x좌표 y좌표를 따로 가지고 있는 형태이기 때문에 input값 순서대로 x좌표 y좌표로 분리해 객체로 만들어서 저장했다.
- sort 로직에 의해 객체 요소가 비교될때 x값이 같으면 y값을 비교해서 리턴하도록 했다.
(return a-b 이 로직이 정확히 어떠한 순서로 돌아가길래 저기 compare안에 if문으로 저런 조건을 동시에 걸었는지 아직 모르겠어서 더 찾아봐야겠다)
- 중복을 제거하기 위해 배열을 집합에 넣고 spread 연산자를 통해 객체 안 요소를 전부 풀어 다시 배열로 집어넣었다.
- 이제까지 함수를 만들어 sort안에 넣었는데 그냥 직접 sort()안에다 작성 할 수 있다.
- a.length - b.length = 길이가 짧은순대로 리턴
- 길이가 같다면 사전순으로 리턴
- for x of arr 문으로 사용해서 간단히 출력
접근법 : 처음에는 반복문으로 현재 인덱스 보다 큰 값이 있을시 카운트를 증가시켜 카운트값을 배열에 넣는거라고 생각했는데 1 ≤ N ≤ 1,000,000의 범위를 가지고 있기 때문에 첫번째 인덱스부터 1,000,000의 범위까지 일일이 비교하는 과정은 시간 오류가 났다.
해결법 : 먼저 N log N의 시간복잡도를 가진 sort를 사용해서 값들을 오름차순으로 정렬한다. 가장 작은값은 다른 값들과 비교해도 카운트가 0이고 그 다음작은값은 제일 작은값보다 1 더 큰값이기 때문에 단순히 제일작은값부터 0에서 i값으로 쭉쭉 매핑시키면 아무리 큰 배열이 들어와도 직선상에서의 매핑된 값만 찾고 그 인덱스만 리턴하면 되니까 시간 초과가 되지 않는다.
1.중복값을 없애기 위해 직전 문제처럼 집합에 넣었다가 다시 배열로 만들어준다. arr = 원본 배열, set = 오름차순된 배열
2.mySet 이라는 Map 객체를 만든다. 처음에는 그냥 객체를 만들어서 [${set[i}] 에 인덱스를 매칭하려고 했는데 그냥 일반 객체는 키값이 오직 문자열로만 저장된다. 그래서 나중에 원본배열에서 키값을 통해 찾을 때 오류가 발생할 수 있으므로 키값으로 숫자를 지정할 수 있는 map 객체를 사용한다.
map 객체의 사용법.
3.이제 map.set으로 map 객체의 키값으로 오름차순된값과 0부터 시작하는 인덱스를 매핑시켜줬다.
4.마지막으로 arr안에 x (키)에 해당하는 값(인덱스)를 찾아서 answer에 넣어 연결시켜준다.
접근법 빈 배열에 원본 배열의 age index value값을 가진 객체를 넣고 age 먼저 정렬을 진행하고 age가 같을시 뒤에 있는 index를 내림차순 하고 맞게 정렬된 값을 반복문으로 age와 value를 answer 문자열에 추가
해결법 정답이 맞긴 맞았는데, 자바스크립트는 기본적으로 stable sort (정렬을 하고 같은 값이 있을 시 원본 인덱스 순서대로 정렬됨)기능을 갖고 있기 때문에 굳이 객체에 index값을 만들어서 sort해 줄 필요없이 사용해도 된다.
0개의 댓글
