[C#] 백준 25400번 제자리

[ 문제 ]

$N$장의 카드가 좌우 일렬로 놓여있다. 각 카드에는 하나의 정수가 적혀있는데, 왼쪽에서 i번째 카드에 적혀있는 정수는 A_i다. (1 ≤ i ≤ N)

여러분은 N장의 카드 중 몇 장을 골라 제거할 수 있다. 이때, 제거되지 않은 카드의 순서는 유지된다.

예를 들어, N = 5, A = [3, 1, 4, 1, 5]라고 하자. 여러분이 두 번째와 다섯 번째 카드를 제거한다면, 남은 카드들에 적혀있는 수들은 왼쪽부터 차례대로 3,4,1이 된다. 즉, 남은 카드들 중 왼쪽에서 세 번째 카드에 적혀있는 수는 1이 된다.

몇 장의 카드를 골라 제거한 후, 남은 카드들 중 왼쪽에서 x번째 카드에 적혀있는 수가 정확히 x라면, 그 카드를 제자리 카드라고 부르자. 모든 남은 카드가 제자리 카드라면, 제자리 상태가 되었다고 하자.

예를 들어, N = 8, A = [6, 1, 2, 3, 2, 4, 5, 10]라고 하자. 여러분이 첫 번째, 다섯 번째, 여덟 번째 카드를 제거하면, 남은 카드들에 적혀있는 수들은 차례대로 1,2,3,4,5가 된다. 이때, 모든 남은 카드는 제자리 카드가 되며, 따라서 제자리 상태가 되었다.

만약, N = 6, A = [3, 4, 6, 10, 2, 5]라면, 제자리 상태가 되기 위해서는 모든 카드를 제거하여 남은 카드가 하나도 없도록 해야 한다.

모든 카드를 제거하면 항상 제자리 상태가 됨에 유의하라.

최소 몇 장의 카드를 제거해야 제자리 상태가 되는지 계산하는 프로그램을 작성하라.

 

[ 코드 ]

1. 내 코드

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

int n = int.Parse(sr.ReadLine());
int[] inputArr = sr.ReadLine().Split().Select(int.Parse).ToArray();
int count = 0;
int value = 1;

for (int i = 0; i < n; i++)
{
    if (inputArr[i] != value)
    {
        count++;
    }
    else
    {
        value++;
    }
}

sw.Write(count);
sw.Flush();
sw.Close();
sr.Close();

 

2. 틀린 코드(부분점수 49점) - 리스트

- 아마 시간이 오래걸려서 인듯 싶다.

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

int n = int.Parse(sr.ReadLine());
List<int> list = sr.ReadLine().Split().Select(int.Parse).ToList();
int count = 0;

for (int i = 0; i < n; i++)
{
    if (list[i] != i + 1)
    {
        count++;
        list.RemoveAt(i);
        i--;
        n--;
    }
}

sw.Write(count);
sw.Flush();
sw.Close();
sr.Close();

 

3. 틀린 코드 (부분점수 49점) - 배열

- 리스트라서 그런가 하고 배열을 써봤는데 배열도 아니였다.

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

int n = int.Parse(sr.ReadLine());
int[] inputArr = sr.ReadLine().Split().Select(int.Parse).ToArray();
int count = 0;
int i = 0;

while(n > i)
{
    if (inputArr[i] == i + 1)
    {
        i++;
    }
    else
    {
        count++;
        for (int j = i; j < n - 1; j++)
        {
            inputArr[j] = inputArr[j + 1];
        }
        n--;
    }
}

sw.Write(count);
sw.Flush();
sw.Close();
sr.Close();

 

간단한 문제였는데 바보같이 ㅜㅜ

 

[ 실행화면 ]

casae: 1

case: 2

case: 3

 

 

 

 

 

---

문제링크: https://www.acmicpc.net/problem/25400

25400번: 제자리