[algorithm/ 정렬 ] 현수는 장난꾸러기, 바뀐 요소 찾기

5219 단어 algorithmalgorithm

문제 : N명의 학생을 작은 키부터 큰 키 순으로 줄을 세웠다. 그런데 현재 줄에서 현수가 짝꿍이랑 자리를 바꿨다.
이 상태에서 선생님은 둘이 자리를 바꾼 줄 모르고 맨 앞에 작은 키인 학생부터 1번 => 가장 큰 키 n번까지 번호를 줬다.
현수가 받은 번호와 현수 짝꿍이 받은 번호를 차례로 출력해라.

입력

  • N : (5<=N<=100)
  • 키 : (120<=키<=180)
  • 제일 앞에부터 일렬로 서있는 학생들의 키가 주어진다.

접근방식

  • 정렬을 생각해라! 현수로 인해 바뀐 줄, 배열과 해당 줄, 배열을 원래 키순으로 정렬했을 경우 두가지를 생각해라
  • 바뀐 배열과 키순 배열의 요소를 비교해서 같은 위치에 다른 요소가 있다면? 현수와 현수의 짝꿍의 키인 것이다.

풀이

  1. 현수와 짝꿍의 키순, 번호를 담아줄 변수를 선언하고 [] 을 할당한다.
  2. 전달 받은 배열(현수와 짝꿍키가 바뀐) sortArr 변수에 복사해서 담아준다.
    => arr 원본 배열에 영향 안줄려고 복사
  3. 원래의 키 순으로 배열을 정렬한다. sort((a, b) => a - b);
  4. for문) 으로 arr(현수와 짝꿍키가 바뀐)배열의 요소를 조회한다.
  5. if 조건) arr[i] 해당 요소의 인덱스와 키순으로 정렬한 요소의 인덱스가 틀린경우?
    => 바뀐 요소라는 뜻! (현수와 짝꿍의 키를 발견!)
    5-1. answer [] 에 둘의 해당 키번호를 i+1 담아준다. => push
    => 키순은 length 번호이기 떄문에 인덱스에 +1을 더해주는것
  6. 현수와 짝꿍의 키 번호(순서)를 담은 answer을 출력한다.
      function solution(arr) {
        let answer = [];
        let sortArr = [...arr];
        sortArr.sort((a, b) => a - b);
        // console.log(sortArr);
        for (let i = 0; i < arr.length; i++) {
          if (arr[i] !== sortArr[i]) {
            answer.push(i + 1);
          }
        }
        return answer;
      }

      let arr = [120, 125, 152, 130, 135, 135, 143, 127, 160];
      console.log(solution(arr)); //[3, 8]
```**

좋은 웹페이지 즐겨찾기