서리 개인 개발 블로그

풀이코드

using System;

public class Solution {
    public int solution(int[] citations) {
        int answer = GetAnswer(citations);
        return answer;
    }
    
    private int GetAnswer(int[] citations)
    {
        Array.Sort(citations, (a, b) => {return b.CompareTo(a);});
        if(citations[0] == 0)
        {
            return 0;
        }
        
        int returnValue = 0;
        for(int i = 0; i < citations.Length; i++)
        {
            if(citations[i] < i + 1)
            {
                returnValue = i;
                break;
            }
        }
        
        return returnValue == 0 ? citations.Length : returnValue;
    }
}

• 내림차순 정렬을 한 뒤, 첫번째 원소가 0이면 H-Index는 0이다.
• 인용이 한번이상 되었다면 발표한 논문의 수와 인용된 수를 비교해서 인용된 수가 논문의 수보다 작으면 index값이 H-Index가 된다.
• 발표한 모든 논문의 인용된 수가 같으면 논문의 수가 H-Index가 된다.

기타

- H-Index만 제대로 이해하면 어려운 문제는 아닌데, 태어나서 처음보는 개념이라 헤맸다.

- H-Index

풀이 코드

using System;

public class Solution {
    public string solution(int[] numbers) {
        string answer = GetAnswer(numbers);
        return answer;
    }

    private string GetAnswer(int[] numbers)
    {
        Array.Sort(numbers, (a, b) =>
                   {
                       string combineAB = string.Format("{0}{1}", a, b);
                       string combineBA = string.Format("{0}{1}", b, a);
                       return combineBA.CompareTo(combineAB);
                   });

        return (GetZeroCount(numbers) == numbers.Length) ? 
            "0" : string.Join("", numbers);
    }

    private int GetZeroCount(int[] sortedNumbers)
    {
        int returnVal = 0;
        for(int i = 0; i < sortedNumbers.Length; i++)
        {
            if(sortedNumbers[i] == 0)
            {
                returnVal++;
            }
        }

        return returnVal;
    }
}

• 처음에는 문제에 나와있는대로 모든 경우의 수를 구하려다가 낭비가 너무 커지는것 같아서 포기했다.
• 원소의 자릿수가 같으면 내림차순 정렬이 가장 큰 값을 가지지만 원소의 자릿수가 달라지면 오름차순의 수가 가장 큰 값을 가지게된다. (ex. [10, 9], [9, 10] ▶ "109" < "910"), (ex. [2, 1], [1, 2] ▶ "21" > "12")
• 그래서 수로 정렬하지 않고, 두 원소의 값을 문자열로 합친 값을 비교하여 정렬함.
• 정렬한 배열의 값이 0만 있을경우 "0"으로만 반환되게끔 예외 처리를 함.

기타 사용한 함수들

- string.CompareTo(string)

- string.Join(string, object[])

using System;

public class Solution {
    public int[] solution(int[] array, int[,] commands) {
        int[] answer = new int[commands.GetLength(0)];
        for(int i = 0; i < answer.Length; i++)
        {
            int start = commands[i, 0];
            int end = commands[i, 1];
            int[] splitArr = SplitArray(array, start, end);
            Array.Sort(splitArr);
            answer[i] = splitArr[commands[i, 2] - 1];
        }
        return answer;
    }
    
    private int[] SplitArray(int[] arr, int start, int end)
    {
        int[] returnArr = new int[end - start + 1];
        Array.Copy(arr, start - 1, returnArr, 0, returnArr.Length);
        return returnArr;
    }
}

이차원 배열

- 2차원 배열은 [행, 열]로 이루어져있다.

- 각 차원에 대한 길이(Length)는 GetLength(N)으로 가져올 수 있는데 N의 값은 행(0), 열(1)이다.

배열의 복사

- Array.Copy(sourceArray(A), startIndex(B), destArray(C), copyStartIndex(D), copyLength(E))

- 원본 배열(A)의 인덱스(B)부터 원하는 갯수(E)만큼의 배열값을 복사될 배열(C)의 인덱스(D)부터 복사를 진행한다.

- 여기서 (E)의 값은 인덱스값이 아니라 원소의 갯수를 의미한다. 즉 (D)와 (E)의 값이 destArray의 범위를 벗어나면 안된다. (복사될 원소의 갯수가 배열의 범위를 벗어나므로 에러 발생)

배열 정렬

- 기본적으로 오름차순으로 정렬되게 되어있다.

- 내림차순으로 정렬을 하려면 Sort한 뒤 Reverse함수를 호출해주거나 IComparer를 지정해서 내림차순 정렬이 가능하다.

using System;

public class ReverseComparer : IComparer
{
    public int Compare(object x, object y)
    {
        return (new CaseInsensitiveComparer()).Compare(y, x);
    }
}

void main()
{
    int[] arr = new int[] { 3, 7, 43, 7, 32, 5, 9, 11, 4, 2 };
    
    //case 1
    Array.Sort(arr);
    Array.Reverse(arr);
    
    //case 2
    IComparer revCompare = new ReverseComparer();
    Array.Sort(arr, revCompare);
    
    //case 3
    Array.Sort(arr, (a, b) =>
    {
        return b.CompareTo(a);
    });
}

가비지 컬렉터(GC, Garbage Collector)

- C/C++와 다르게 CLR(Common Language Runtime)이 자동 메모리 관리 기능을 제공한다.

- 객체를 힙에 할당을 하면 가비지 컬렉터는 이 중 쓰레기인것을 분리해서 수거해건다.

- 가비지 컬렉터 역시 소프트웨어이기 때문에 CPU와 메모리 자원을 소모한다.

   ※ 이 때, 별도의 공간에서 자원을 소모하는것이 아닌 사용자가 사용하는 자원을 같이 사용한다.

- unsafe 키워드를 사용한 비관리형 코드는 CLR이 제공하는 서비스를 받을 수 없다.

CLR의 메모리 관리

- C#으로 작성한 실행파일을 실행하면, CLR은 프로그램을 위한 일정 크기의 메모리(Managed Heap)를 마련한다.

- 그 뒤, CLR은 Managed Heap의 첫번째 주소에 객체를 할당할 메모리의 포인터를 위치시킨다.

- 힙에 객체를 할당하면 메모리 포인터를 할당된 객체가 차지하고 있는 공간 바로 뒤로 위치시킨다.

- Heap에 할당된 object 객체를 참조하고 있는 변수 obj가 Stack에서 소멸되버리면 object 객체는 어디에서도 접근할 수 없기 때문에 쓰레기가 되어버린다. (이런 객체들을 가비지 컬렉터가 수거해간다.)

- 위치 참조 객체(obj)를 Root라고 하고, 이 Root는 스택, 힙 아무데서나 생성될수 있다.

- .Net 어플리케이션이 실행되면 JIT 컴파일러(Just-In-Time Compile)가 이 Root들을 목록으로 만들고, CLR이 Root목록을 관리하면서 상태를 갱신한다.

   ※ 가비지 컬렉터가 CLR이 관리하는 루트의 목록을 참조해서 쓰레기를 수거해간다.

가비지 컬렉터 객체 정리 과정

1. 작업을 시작하기 전, 가비지 컬렉터는 모든 객체를 수거 대상으로 가정한다.

2. 루트 목록을 순회하면서 각 루트가 참조하고 있는 힙 객체와의 관계 여부를 조사한다. 만약 루트가 참조하고 있는 힙의 객체가 또다른 힙을 참조하고 있다면, 또 다른 힙 역시 루트와 관계있는것으로 판단하고 수거 대상에서 제외된다.

3. 쓰레기 객체가 차지하고 있던 메모리 공간은 비어있는 공간이 된다.

4. 루트 목록에 대한 조사가 끝나면, 가비지 컬렉터는 힙을 순회하면서 비어있는 공간에 쓰레기의 인접 객체들을 이동시켜서 채워넣는다.

세대별 가비지 컬렉션

- CLR의 메모리는 구역을 나누어 메모리에서 바로 없어질 객체와 오래 있을 객체를 따로 담아 관리한다.

- 메모리를 0, 1, 2의 3개 세대로 나누고 0세대에서는 빨리 사라질 객체, 마지막 세대에서는 오래 있을 객체로 채워진다.

- 객체에 대한 세대를 나누는 기준은 가비지 컬렉션을 겪은 횟수이다.

- 각 세대는 가비지 컬렉션 수행을 위한 임계치가 있으며, 이 임계치에 도달하면 가비지 컬렉터가 해당 세대에 대해 가비지 컬렉션을 수행하고, 살아남은 객체들을 다음 세대로 옮긴다.

- 상위 세대의 가비지 컬렉션이 수행되면 가비지 컬렉터는 해당 세대를 포함한 하위 세대에 대해서도 가비지 컬렉션을 수행한다.

• 1세대 가비지 컬렉션 : 0, 1세대 가비지 컬렉션 수행.
• 2세대(전체) 가비지 컬렉션 : 0, 1, 2세대 가비지 컬렉션 수행.

- 2세대 힙이 가득차게 되면, CLR은 어플리케이션의 실행을 잠시 멈추고 전체 가비지 컬렉션(Full GC)을 수행하여 메모리 확보하기 때문에, 어플리케이션의 메모리가 크면 클수록 Full GC시간이 길어지므로 유의해야한다.

가비지 컬렉션을 위한 효율적인 코드 작성법

1. 객체를 너무 많이 할당하지 말 것.

 - 객체 생성 코드를 작성할 때 곡 필요한 객체인지, 필요 이상으로 많은 객체를 생성하는 코드가 아닌지의 여부를 고려해야한다.

2. 너무 큰 객체 할당을 피한다.

 - CLR은 보통 크기의 객체를 할당하는 힙과는 별도로 85kb이상의 대형 객체를 할당하기 위한 대형 객체 힙(LOH : Large Object Heap)을 따로 유지한다. (사용자가 평소에 사용하는 힙은 소형 객체 힙(SOH : Small Object Heap)이다.)

 - SOH는 객체를 할당할 포인터가 위치한 메모리에 바로 객체를 할당하지만 LOH는 객체의 크기만큼의 여유 공간이 있는지 힙을 탐색하여 할당한다.

 - LOH는 메모리 정리를 위한 복사 비용이 비싸기 때문에, SOH처럼 정리된 힙에 객체들을 차곡차곡 모으지 않고 해제된 공간을 그대로 둔다.

 - 또한 LOH는 2세대 가비지 컬렉션이 수행되어야 쓰레기 객체가 수거되기 때문에 어플리케이션의 순간 정지를 불러온다.

3. 너무 복잡한 참조 관계는 만들지 말 것.

 - 객체끼리 너무 복잡한 참조관계를 만들어두면, 가비지 컬렉터는 가비지 컬렉션 수행 이후, 살아님은 객체의 세대를 옮기기 위해 메모리 복사를 수행하는 과정에서 객체를 구성하고 있는 각 필드 객체 간의 참조를 일일이 조사해서 참조 메모리 수조를 전부 수정하기 때문에 자원이 많이 소모된다.

 - 2세대의 객체의 멤버에 새로은 객체를 만들게될 경우 이 새로운 객체은 0세대 가비지 컬렉션에 의해 수거될 가능성이 있다. 이때 쓰기 장벽(Write barrier)이라는 장치를 통해 가비지 컬렉션의 대상에서 제외가 되는데, 여기서 발생하는 오버헤드가 크므로 참조관계를 최소한으로 하면 이러한 오버헤드를 줄일 수 있다.

4. 루트를 너무 많이 만들지 말 것.

 - 가비지 컬렉터는 루트 목록을 돌면서 쓰레기를 찾아내기 때문에, 루트 목록이 작아지면 그만큼 검사 수행 횟수가 줄어들므로 가비지 컬렉션이 빨리 끝나게된다.