서리 개인 개발 블로그

풀이 코드

using System;
using System.Collections.Generic;

public class Solution {
    private HashSet<int> m_visited = new HashSet<int>();

    public int solution(int n, int[,] computers) {
        int answer = 0;
        for(int i = 0; i < n; i++)
        {
            if(!m_visited.Contains(i))
            {
                answer++;
                DFS(computers, i);
            }
        }
        return answer;
    }

    private void DFS(int[,] computers, int currentIndex)
    {
        m_visited.Add(currentIndex);
        for(int i = 0; i < computers.GetLength(0); i++)
        {
            if(m_visited.Contains(i) || currentIndex == i ||
              computers[currentIndex, i] == 0)
            {
                continue;
            }

            DFS(computers, i);
        }
    }
}

• 재귀함수를 이용하여 DFS를 구현하였다. (Stack 및 반복문을 이용하는 방법도 있지만, 코드가 복잡하게 보일까봐 재귀함수로 작성)

기타

- 그래프를 평소에 다루어 보지 않아서 한참을 헤맸다. (통과는 됐지만 이게 진짜 문제에서 요구하는게 맞는지 헷갈림)

풀이 코드

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(string[] operations) {
        Heap heap = new Heap();
        for(int i = 0; i < operations.Length; i++)
        {
            string[] split = operations[i].Split(" ");
            if(split[0] == "I")
            {
                heap.Add(Int32.Parse(split[1]));
            }
            else
            {
                if(split[1] == "1")
                {
                    heap.RemoveMax();
                }
                else
                {
                    heap.RemoveMin();
                }
            }
        }
        int[] answer = heap.GetAnswer();
        return answer;
    }
}

public class Heap
{
    private List<int> m_minHeap = new List<int>();
    private List<int> m_maxHeap = new List<int>();

    public void Add(int n)
    {
        m_minHeap.Add(n);
        SortUp(m_minHeap, CompareMin);
        m_maxHeap.Add(n);
        SortUp(m_maxHeap, CompareMax);
    }

    public void RemoveMin()
    {
        if(m_minHeap.Count <= 0 || m_maxHeap.Count <= 0)
        {
            return;
        }

        m_minHeap[0] = m_minHeap[m_minHeap.Count - 1];
        m_minHeap.RemoveAt(m_minHeap.Count - 1);
        SortDown(m_minHeap, CompareMin);

        m_maxHeap.RemoveAt(m_maxHeap.Count - 1);
    }

    public void RemoveMax()
    {
        if(m_minHeap.Count <= 0 || m_maxHeap.Count <= 0)
        {
            return;
        }

        m_maxHeap[0] = m_maxHeap[m_maxHeap.Count - 1];
        m_maxHeap.RemoveAt(m_maxHeap.Count - 1);
        SortDown(m_maxHeap, CompareMax);

        m_minHeap.RemoveAt(m_minHeap.Count - 1);
    }

    public int[] GetAnswer()
    {
        int[] answer = new int[] { 0, 0 };
        if(m_maxHeap.Count > 0 && m_minHeap.Count > 0)
        {
            answer[0] = m_maxHeap[0];
            answer[1] = m_minHeap[0];
        }

        return answer;
    }

    private void SortDown(List<int> list, Func<int, int, int> compare)
    {
        int currentIndex = 0;
        while(true)
        {
            int leftIndex = currentIndex * 2 + 1;
            int rightIndex = currentIndex * 2 + 2;
            int swapIndex = currentIndex;

            if(leftIndex < list.Count)
            {
                swapIndex = leftIndex;

                if(rightIndex < list.Count)
                {
                    if(compare.Invoke(list[leftIndex], list[rightIndex]) < 0)
                    {
                        swapIndex = rightIndex;
                    }
                }

                if(compare.Invoke(list[currentIndex], list[swapIndex]) < 0)
                {
                    Swap(list, currentIndex, swapIndex);
                    currentIndex = swapIndex;
                }
                else
                {
                    return;
                }
            }
            else
            {
                return;
            }
        }
    }

    private void SortUp(List<int> list, Func<int, int, int> compare)
    {
        int currentIndex = list.Count - 1;
        int parentIndex = currentIndex / 2;
        while(true)
        {
            if(compare.Invoke(list[currentIndex], list[parentIndex]) > 0)
            {
                Swap(list, currentIndex, parentIndex);
                currentIndex = parentIndex;
                parentIndex = currentIndex / 2;
            }
            else
            {
                break;
            }
        }
    }

    private void Swap(List<int> list, int indexA, int indexB)
    {
        int tmp = list[indexA];
        list[indexA] = list[indexB];
        list[indexB] = tmp;
    }

    private int CompareMax(int a, int b)
    {
        return a.CompareTo(b);
    }

    private int CompareMin(int a, int b)
    {
        return -CompareMax(a, b);
    }
}

• 최소값을 루트에 갖는 List와 최대값을 루트에 갖는 List 2개를 만들어주고, 값이 들어가거나 빠질때마다 SortUp, SortDown으로 리스트를 갱신해준다.
• 최종 결과값은 최소 List와 최대 List의 루트값을 출력해주면 된다.

기타

- 문제 카테고리가 힙으로 분류되어있어서 힙을 구현해서 사용했다. (다른사람 풀이를 보니 Linq를 사용해서 짧게 작성했던데, 카테고리 생각하면 Linq사용하는게 정답같아보이지는 않는다.)

- 힙에 대한 설명은 아래 포스팅 참조

풀이 코드

using System;

public class Solution {
    public bool solution(string s) {
        int count = 0;
        for(int i = 0; i < s.Length; i++)
        {
            count = s[i] == '(' ? count + 1 : count - 1;
            if(count < 0)
            {
                return false;
            }
        }

        return count == 0;
    }
}

• 문자열을 순회하면서 '('값이면 count 값을 올리고, ')'이면 값을 내린다.
• 순회 도중 count가 음수가 되면 괄호 짝이 안맞는것이므로 false로 출력한다.
• 모든 문자열을 순회하였을 시, count 값이 0이면 true, 아니면 false로 출력한다.

기타

- 카테고리가 Stack/Queue로 되어있어서 스택을 써야하나 고민했는데, 굳이 스택을 써야하나 싶어서 위와 같은 과정으로 풀이함.

풀이 코드

using System;

public class Solution {
    public int[] solution(string s) {
        int zeroCount = 0;
        int loopCount = 0;
        while(s != "1")
        {
            string replaceStr = s.Replace("0", string.Empty);
            int lengthDiff = s.Length - replaceStr.Length;
            zeroCount += lengthDiff;
            loopCount++;
            s = Convert.ToString(replaceStr.Length, 2);
        }
        
        int[] answer = new int[] {loopCount, zeroCount};
        return answer;
    }
}

• string.Replace()를 사용해서 0값을 지워준다.
• 지운 문자열(replaceStr) 길이와 인수로 들어온 문자열(s)의 길이를 빼서 그 값을 전부 더해준다.
• 다음 루프에서 이 과정을 다시 처리하기 위해 s값을 replaceStr 문자열 길이를 2진수로 변환한 문자열로 변경해준다.
• 위 과정을 s가 "1"이 될때까지 반복 후, 결과를 출력한다.

기타

- Convert.ToString() : 첫번째 인수에 변환할 값을, 두번째 인수에 몇진수로 변환할건지 값을 입력하면 변환된 값을 문자열로 받을 수 있다.

풀이코드

using System;

public class Solution {
    public int solution(int[] A, int[] B) {
        Array.Sort(A);
        Array.Sort(B, (a, b) => b.CompareTo(a));
        
        int answer = 0;
        for(int i = 0; i < A.Length; i++)
        {
            answer += A[i] * B[i];
        }
        
        return answer;
    }
}

• 핵심 요지는 배열 A의 최소값과 배열 B의 최대값을 곱해주면 최종적으로 최소값이 나온다.
• 그렇기 때문에, 배열 A는 오름차순, 배열 B는 내림차순으로 정렬한뒤 각 배열의 i번째 값들을 순서대로 곱해준 뒤, 더한값을 결과로 출력한다.