[Novice Mid : 프로그래밍 연습] 정렬 : 객체 정렬 - 정렬된 숫자 위치 알아내기

 

 

★ "왜?" 라는 질문을 스스로에게 하면서 학습하자.

 

 

0. 문제 풀이 순서

• 논리적 순서 확정
• 관련 카테고리 혹은 문제 끌어오기
• 필요한 자료연산 리스트업
• 이에 제일 유리한 자료구조 선택
• 구현

 

1. 설명

 

문제 링크 : https://www.codetree.ai/missions/5/problems/indices-of-sorted-array?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 사진 :

 

 

문제 설명 : 양의 정수를 원소값으로 갖는 길이가 N인 수열이 입력으로 주어졌을 때 해당 수열을 오름차순 했을 때 오름차순 하기 전에 있떤 원소가 현재 어느 위치로 이동했는지 출력하는 코드를 작성하시오. 🤦‍♀️

 

 

---

 

 

나의 소스 코드 :

 

 

코드 설명 : 해당 문제 챕터가 객체 정렬 문제 챕터임을 알았지만, 이전의 여러 문제들과 달리 키, 몸무게 등의 정보가 없고, 단순히 수열 내부의 원소값만 있다보니 클래스를 사용헤야 하나? 라는 생각이 들었다. 그러나 정렬을 사용하기 위해서는 클래스의 존재 여부가 필요하다는 것을 알아 일단 선언하여 사용하였다.

 

 또한 어느 위치로 이동했는지를 알아야 하기 때문에 인덱스를 이용했어야 했다. 그래서 메인 함수에서 idx를 선언하여 해당 값을 이용하여 어느 위치로 이동하는 지를 출력하고자 했다. 

 

    // 출력 확인용 로그
    cout << "num : ";
    for (int i = 0; i < n; i++)
    {
        cout << t[i].num << " ";
    }
    cout << endl;

    cout << "idx : ";
    for (int i = 0; i < n; i++)
    {
        cout << t[i].idx << " ";
    }
    cout << endl;

 

 그러나 정렬한 이후 아래 이미지와 같이 Arr가 1, 1, 2, 3, 6, 7, 30이 되는 것은 확인했으나 왜 Index의 값이 2, 7, 4, 1, 3, 5, 6이였는지 이해가 되지 않았다. 또한 정렬 이 후 특정 값이 어디에서 어느 위치로 이동을 했는지의 대한 처리도 구현하기가 힘들었다. 당장 값을 정렬하는 함수 cmp 내부에서 a가 3, b가 1이 들어올 때 정렬을 해주어야하는데 '어디에 어떤 값을 어떻게 넣어서 처리해야 하는가?'를 생각해보았을 때 쉽사리 답이 생각나지 않았다.

 

 결국 시간 내에 문제를 풀지 못해서 해설을 보았다. 해설을 보니 내가 풀고자 했던 것과 같이 인덱스를 먼저 구하길래 적어도 내 방법이 틀리지 않았구나. 생각했다. 그러나 일전에 말한 것처럼 Index의 값이 2, 7, 4, 1, 3, 5, 6이였는지 이해가 되지 않았다. 해설 이미지를 차근차근 살펴보니 아래 이미지와 같이 처리 된 것을 알 수 있었다.

 

 

 그러나 이후에 정렬을 할 때에도 1. 먼저 입력으로 주어진 원소가 더 앞에 와야한다. 2. 숫자가 같을 경우 인덱스를 비교해준다. 라는 조건을 맞춰주어야 한다. 나는 숫자 값을 비교할 때 대/소(>, <) 비교만 하여 문제를 풀이하려고 하였으나 단순히 대/소 비교만으로는 문제를 풀 수 없었다. 따라서 해답 코드를 보니 대/소 비교를 하는 것이 아닌 같은/같지 않은 경우를 이용하여 문제를 풀어주고 있었다. (==, !=)

 

 같지 않을 경우 리턴을 통해 a.number < b.number를 이용해 b의 값이 더 뒤에 나오게 정렬을 진행한다. 만약 같은 경우(= 위 이미지에서 1, 1이 들어온 것 처럼) 인덱스 값을 통해 정렬을 진행하여 처리한다.

 

// Custom Comparator
bool Cmp(Number a, Number b)
{
    if(a.number != b.number)
        return a.number < b.number;
    return a.index < b.index;
}

 

 마지막으로 해설 소스코드에서는 답을 출력하기 위해 배열 answer를 선언하여 정렬된 인덱스의 값을 정답 배열인 answer에 값을 저장해주었다. 이 후 answer를 출력하여 문제를 풀이하였다.

 

    // 정렬된 인덱스를 활용하여 정답 배열 내부에 값을 저장한다.
    for (int i = 0; i < n; i++)
    {
        answer[t[i].idx] = i + 1; // 인덱스 위치 보정.
    }

    // 정답 배열 내부 값 출력
    for (int i = 0; i < n; i++)
    {
        cout << answer[i] << " ";
    }

 

 anwer[t[i].idx] 까지는 이해가 되는데 anwer[t[i].idx]에 i + 1가 잘 이해되지 않았다. 물론 해설 코드를 보면 i가 0부터 시작하기 떄문에 i + 1을 하여 보정을 해주는 것이 머릿속으로는 이게 맞지 싶다가도 anwer[t[i].idx] 내부에 i + 1의 값이 어떻게 저장되는지 쉽게 이해가 되지 않는다. 😥.. 

 

 

2. 시간

• 문제 풀이를 위해 설정한 시간 : 37분
• 실제 풀이 시 걸렸던 시간 : 1시간 10~30분

 

 

3. 질문

• 시간 복잡도 : 단순 for문을 n만큼 반복문을 수행하였기 때문에 O(n)의 시간이 걸린다.
• 공간 복잡도 : 2개의 int 변수를 사용하였으므로 2n + 8의 값을 가진다. 따라서 입력 값에 따라 선형적으로 복잡도가 증/감 하기 때문에 O(n)이 걸린다.
• 어려웠던 부분 : '정렬을 대/소 비교로 어떻게 처리하지?'와 '정렬된 결과 값을 어디에 어떻게 저장해야 하지?'가 어려웠다. 새로운 배열을 사용하면 될 것 같은데.. 까지는 생각해보았지만 값을 어떻게 넣어줘야 하는지에 대한 해답도 제대로 내지 못했다.

 

 

4. 기타

• 최초 풀이 : 23.09.20
• 재 풀이 : -
• 왜? : -