우당탕탕 게임개발 여행기

문제 접근법

문자열이 담겨진 배열을 하나하나 본 뒤 문자열 ex와 부분일치가 있는 문자열이 있는지 확인하면

간단한 문제라서 쉽게 풀었다

- C# 문제풀이

using System;

public class Solution {
    public string solution(string[] str_list, string ex) {
        string answer = "";
        
         for(int i = 0; i < str_list.Length; i++)
         {
             if(str_list[i].Contains(ex))
                 continue;
             else
                 answer += str_list[i];
         }

        return answer;
    }
}

- 문제 복기

문제 복귀 결과 성능적으로는 조금 아쉬운 부분이 존재했다.

C#에서 문자열은 'immutable(불변)'이기에 반복분 내 코드를 실행할 때마다

새 문자열을 계속 생성하게 된다

answer += str_list[i];

이 부분에서 메모리와 성능에 불리하게 작용된다.

권장하는 방법: StringBuilder 사용

using System;
using System.Text;

public class Solution {
    public string solution(string[] str_list, string ex) {
        StringBuilder sb = new StringBuilder();
        
        foreach (string s in str_list)
        {
            if (s.Contains(ex))
                continue;

            sb.Append(s);
        }

        return sb.ToString();
    }
}

이러면 반복해서 사용하더라도 성능 손해가 발생하지 않는다!

문제 접근법

왼쪽일 때와, 오른쪽일 때, 기본(없을 때) 3가지 방향으로 나누고

각 방향에 맞게 코드를 작성하기

핵심

Array.Copy의 매개변수의 의미

Array.Copy(sourceArray, sourceIndex, destinationArray, destinationIndex, length);

- C# 전체코드

using System;

public class Solution {
    public string[] solution(string[] str_list) 
    {        
        for(int i = 0; i < str_list.Length; i++)
        {
            // 왼쪽이면?
            if(str_list[i] == "l")
            {
                string[] answer = new string[i];
                Array.Copy(str_list, 0, answer, 0, answer.Length);
                return answer;
            }
            // 오른쪽이면?
            else if(str_list[i] == "r")
            {
                string[] answer = new string[str_list.Length - i - 1];
                Array.Copy(str_list, i + 1, answer, 0, answer.Length);
                return answer;
            }
        }
        
        return new string[] {};
    }
}

해당 방법으로 코드를 작성해보고 해석해보면

Array.Copy(str_list, i + 1, answer, 0, answer.Length);

str_list [i+1] 부터 끝까지

총 answer.Length개를
answer[0]부터 채운다.

문제 접근법

처음에는 지워야할 값을 가져와서 일일히 지워줘야 한다고 생각했는데

먼저 bool 값으로 지워야할 위치를 기억하고 있으면 나중에 관리하기 편해보였다.

핵심

제거 여부를 bool 배열로 관리 하기!

먼저 bool 배열로 삭제할 위치를 기억한 다음에 삭제할 위치가 아니라면 answer에 더하고

삭제할 위치면 추가하지 않는다!

using System;

public class Solution {
    public string solution(string my_string, int[] indices) {
        string answer = "";
        
        // 제거 여부를 bool 배열로 관리하기
        bool[] removeArr = new bool[my_string.Length];
        foreach (int index in indices)
        {
            removeArr[index] = true;
        }
    
        // 제거하기(true값이 아닐 때만 answer에 추가)
        for (int i = 0; i < my_string.Length; i++)
        {
            if (!removeArr[i])
                answer += my_string[i];
        }
        
        
        return answer;
    }
}

- 오답 코드(뒤집기가 아닌 교체만 함)

public class Solution {
    public string solution(string my_string, int[,] queries) {
        char[] charArr = my_string.ToCharArray();
        
        for (int i = 0; i < queries.GetLength(0); i++)
        {
            char temp = charArr[queries[i, 0]];
            charArr[queries[i, 0]] = charArr[queries[i, 1]];
            charArr[queries[i, 1]] = temp;
        }
        string answer = new string(charArr);
        return answer;
    }
}

처음 보고 풀때는 자리교체만 해줬다 ㅋㅋㅋㅋㅋㅋ

문제를 다시 읽어보니 뒤집는 문제다!

- 정답 코드(뒤집기로 풀기)

using System;

public class Solution {
    public string solution(string my_string, int[,] queries) {
        char[] charArr = my_string.ToCharArray();
        
        for (int i = 0; i < queries.GetLength(0); i++)
        {
            int start = queries[i, 0];
            int end = queries[i, 1];
            
            Array.Reverse(charArr, start, end - start + 1);
        }
        string answer = new string(charArr);
        return answer;
    }
}

Array.Reverse(시작, 뒤집을 원소 갯수);

원소 갯수 = end - start + 1;

(  3 ~ 7까지면, 3부터 4개(7-3+1)  )

using System;

public class Solution {
    public int solution(string number) {
        int answer = 0;
        for (int i = 0; i < number.Length; i++)
        {
            answer += int.Parse(number[i].ToString()); 
        }        
        answer %= 9;
        
        return answer;
    }
}

핵심 부분

C# 에서는 string을 배열같이 접근할 수 있는데

문자 하나를 출력하는 거라 char형으로 인식한다.

그래서 Parse로 형변환 할 때는 ToString으로 문자열로 만든 다음 접근한다

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(string my_string) {
        List<int> numbers = new List<int>();
        char[] charArr = my_string.ToCharArray();
        for (int i = 0; i < charArr.Length; i++)
        {
            switch(charArr[i]) {
                case '1':
                    numbers.Add(1);
                    break;
                case '2':
                    numbers.Add(2);
                    break;
                case '3':
                    numbers.Add(3);
                    break;
                case '4':
                    numbers.Add(4);
                    break;
                case '5':
                    numbers.Add(5);
                    break;
                case '6':
                    numbers.Add(6);
                    break;
                case '7':
                    numbers.Add(7);
                    break;
                case '8':
                    numbers.Add(8);
                    break;
                case '9':
                    numbers.Add(9);
                    break;
                case '0':
                    numbers.Add(0);
                    break;
            }
        }
        numbers.Sort();
        return numbers.ToArray();
    }
}

나의 풀이 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

public class Solution {
    public int[] solution(string my_string) {
        List<int> numbers = new List<int>();
        
        foreach (char ch in my_string)
        {
            if (char.IsDigit(ch))   // 숫자인 경우만
                numbers.Add(ch - '0'); // 문자 → 정수 변환
        }
        
        return numbers.ToArray();
    }
}

GPT 행님이 알려주신 방법

뭐 방향성은 맞았으니 좋았쓰 ㅋㅋㅋㅋㅋㅋㅋ

선택 정렬은 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다.

현재 위치에 저장될 값의 크기가 작으면 최소 선택 정렬(Min-Selection Sort), 즉 오름차순 정렬

저장될 값의 크기가 크면 최대 선택 정렬(Max-Selection Sort), 즉 내림차순 정렬이다.

기본적인 방법은 정렬되지 않는 배열의 맨 앞에서 부터 뒤에 있는 값들을 비교하면서 가장 작은 값을 찾아 맨 앞으로 둔다.

즉, 정렬되지 않는 값들 중에서 가장 작은 값을 먼저 찾은 뒤에 정렬을 한다!

해당 순번의 정렬이 끝나면 모든 값들의 정렬이 끝날 때까지 이를 반복한다.

C# 으로 구현해보기

static void SelectionSort(int[] arr)
{
    int n = arr.Length;
    // 선택 정렬 알고리즘(오름차순)
    for (int i = 0; i < n - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        // 값 교환하기
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

static void Main()
{
	int[] arr = { 5, 3, 8, 4, 2 };
    SelectionSort(arr);
    Console.WriteLine(string.Join(", ", arr)); // 출력: 2, 3, 4, 5, 8
}

시간복잡도: O(N²) 

시간복잡도란?
→ 입력 크기 n에 따라 알고리즘이 걸리는 연산 횟수를 나타내는 것.
→ "대략 몇 번 반복되는지"를 보는 것.

배열 안에서 n-1, n-2, n-3 ... 1번 씩 비교를 하므로 O(n²) 의 시간복잡도를 가진다.

즉, n 크기의 배열에서 n번의 계산을 하므로 O(n²)의 시간 복잡도를 갖는다.

( n개의 데이터를 처리할 때 평균적으로 각 원소마다 n번 비교/연산을 하게 되면 시간복잡도는 O(n²) )

문제설명: 

정수 l과 r이 주어졌을 때, l 이상 r이하의 정수 중에서 숫자 "0"과 "5"로만 이루어진 모든 정수를 오름차순으로 저장한 배열을 return 하는 solution 함수를 완성해 주세요. 만약 그러한 정수가 없다면, -1이 담긴 배열을 return 합니다.

입출력 예 설명

입출력 예 #1

5 이상 555 이하의 0과 5로만 이루어진 정수는 작은 수부터 5, 50, 55, 500, 505, 550, 555가 있습니다. 따라서 [5, 50, 55, 500, 505, 550, 555]를 return 합니다.

입출력 예 #2

10 이상 20 이하이면서 0과 5로만 이루어진 정수는 없습니다. 따라서 [-1]을 return 합니다.

코드 풀이

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(int l, int r) {
        List<int> answer = new List<int>();
        bool isFive = false;
        
        for (int i = l; i <= r; i++)
        {
            foreach (char ch in i.ToString())
            {
                if (ch == '5' || ch == '0')
                {
                    isFive = true;
                    continue;
                }
                else
                {
                    isFive = false;
                    break;
                }                
            }
            if (isFive)
                answer.Add(i);
        }       
        if (answer.Count == 0) 
            answer.Add(-1);            
        return answer.ToArray();
    }
}

코드 해석

핵심은 foreach 부분이다. 이 부분은 숫자의 모든 자리수가 5 또는 0으로만 이루어진 숫자인지 검사하는 부분이다

우선 숫자 i를 문자열로 바꿔서 각 자릿수를 하나씩 확인한다

	foreach (char ch in i.ToString())
            {
                if (ch == '5' || ch == '0')
                {
                    isFive = true;
                    continue;
                }
                else
                {
                    isFive = false;
                    break;
                }                
            }

해당 자리가 5 또는 0이면 통과(충족)하며 (bool 값을 true값으로 바꿔준다)
하나라도 5 또는 0이 아니면 바로 중단(break)한다 → bool 값을 false값으로 바꾸고 해당 숫자는 불충족.