[C#] Practice_Data Structure

요세푸스 문제 - List

---

두 자연수 n과 k가 주어졌을 때, 1부터 n까지의 자연수를 원형으로 배치한 다음, 1부터 시작하여 k−1개의 수를 건너뛰고 그 다음 k번째 수를 제거하는 것을 숫자가 하나만 남을 때까지 반복했을 때, 마지막으로 남는 수가 무엇인지 구하여라.

public int Yose(int n, int k)
{
    int j = k-1;
    
    List<int> list = new(n);  
    
    for (int i = 1; i <= n; i++)
    {
        list.Add(i);
    }
    
    while (list.Count > 1)
    {
        while (j >= list.Count)
        {
            j -= list.Count;
        }
        list.RemoveAt(j);
        j += k-1;
    }
    return list[0];
}

1. for : List 에 숫자를 추가해주는 행동
2. while(list.count > 1) : 1개가 남을 때까지 반복 수행
3. while(j >= list.count) : 한 바퀴 돌면 다시 처음으로 돌아가는 행동
4. list.RemoveAt(j) : k번째 수 제거
5. j += k - 1 : k - 1개의 수 건너뛰기

괄호 검사 - Stack, Queue

---

1. 왼쪽과 오른쪽의 괄호의 개수가 같아야 한다.
2. 같은 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
3. 서로 다른 타입의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안 된다.

public bool CheckParen(string str)
{
    if (str.Length % 2 == 1) return false;
    
    Stack<char> strFront = new();
    Queue<char> strBack = new();
    char modifier;

    for (int i = 0; i< str.Length / 2; i++)
    {
        strFront.Push(str[i]);                
    }
    
    for (int i = str.Length / 2; i < str.Length; i++)
    {
        strBack.Enqueue(str[i]);
    }

    for(int i = 0; i < str.Length / 2; i++)
    {
        switch(strFront.Pop())
        {
            case '(':
                modifier = ')';
                if (!modifier.Equals(strBack.Dequeue())) return false;
                break;
            case '{':
                modifier = '}';
                if (!modifier.Equals(strBack.Dequeue())) return false;
                break;
            case '[':
                modifier = ']';
                if (!modifier.Equals(strBack.Dequeue())) return false;
                break;
        }               
    }
    return true;
}

1. if (str.Length % 2 == 1) return false; : 1번 조건 부합 여부 확인
2. Stack<char> strFront = new();
for (int i = 0; i< str.Length / 2; i++)
{ strFront.Push(str[i]); }
   괄호의 왼쪽 절반은 Stack으로 재배열
3. Queue<char> strBack = new();
for (int i = str.Length / 2; i < str.Length; i++)
{ strBack.Enqueue(str[i]); }
   괄호의 오른쪽 절반은 'Queue`로 재배열
4. switch : 왼쪽과 오른쪽 괄호 순서쌍 일치 여부 확인
   순서쌍을 올바르게 맞추기 위해서 한쪽을 스택, 다른 한쪽을 큐로 만들어 하나씩 꺼내며 비교할 수 있도록 구현. 만약 모두 일치하는 경우 true 반환

Stact구현 - Array

---

기본 필드, Clear

public class MyStack<T>
{
    public T[] array = new T[10];

    public int Length => array.Length;
    
    public void Clear()
	{
    	this.array = new T[array.Length];
	}
}

1. 인스턴스 최초 크기 10
2. Clear() : 배열 내 모든 요소 초기화

Push, Duplicate

public void Push(T element)
{
    if (IsFulled())
    {
        Duplicate();
        for (int i = array.Length / 2; i < array.Length; i++)
        {
            if (this.array[i].Equals(default(T)))
            {
                this.array[i] = element;
                break;
            }
        }
    }
    else
    {
        for (int i = 0; i < array.Length; i++)
        {
            if (this.array[i].Equals(default(T)))
            {
                this.array[i] = element;
                break;
            }
        }
    }                    
}

public void Duplicate()
{
    T[] arrayBase = new T[this.array.Length];
    arrayBase = this.array;
    this.array = new T[this.array.Length * 2];
    for(int i = 0; i < arrayBase.Length; i++)
    {
        this.array[i] = arrayBase[i];
    }
}

public bool IsFulled()
{
    for(int i = 0; i < array.Length; i++)
    {
        if (this.array[i].Equals(default(T)))
        {
            return false;
        }
    }
    return true;
}

Isfulled() : 배열의 모든 인덱스에 요소가 있는지 확인
Duplicate() : 요소가 다 차있는 경우, 크기를 2배로 늘리는 함수
Push() : 배열에 요소를 추가하는 함수

Pop, Peek

public T Pop()
{
    T temp;
    for(int i = this.array.Length - 1; i >= 0; i--)
    {
        if (!this.array[i].Equals(default(T)))
        {
            temp = this.array[i];
            this.array[i] = default(T);
            return temp;
        }               
    }
    return default(T);
}

public T Peek()
{
    for (int i = this.array.Length - 1; i >= 0; i--)
    {
        if (!this.array[i].Equals(default(T)))
        {
            return this.array[i];
        }
    }
    return default(T);
}

Pop() : 가장 마지막에 추가한 요소를 확인하고 배열에서 제거.
peek() : 가장 마지막에 추가한 요소를 확인