[백준 25400] 제자리

제자리(25400)

문제 출처 : https://www.acmicpc.net/problem/25400
 
이 문제는 2022년 정보 올림피아드 2차 초등부 1번 문제 입니다.

문제 이해하기

제자리 상태가 된다는 것은 최종적으로는 1, 2, 3, … 순으로 남아있어야 한다는 뜻입니다.
만약 아래와 같은 숫자들이 있습니다.

5, 4, 3, 2, 1

이숫자들을 제자리 상태로 만든다는 것은 1 하나만 남기는 것입니다. 왜냐하면 어떤 숫자를 빼도 오름차순으로 정렬할 수 없기 때문 입니다. 만약 숫자들 중에 1이 존재하지 않는다면 제자리 상태를 만들 수 없고 결국 모든 카드를 제거해야 합니다.
결국 이 문제를 해결하기 위해서는 제일 먼저 1을 찾고, 다음은 2를 찾고, 또 3을 찾아 순서대로 정렬하고 정렬이 되지 않는 카드들은 전부 버리면 됩니다.
그럼 예제를 통해 좀 더 알아보겠습니다.

6, 1, 2, 3, 2, 4, 5, 10

문제의 예제와 같은 숫자들이 있다면 리스트를 돌면서 1을 찾습니다. 1을 만나기 전 다른 숫자들은 모두 삭제 합니다. 처음 만나는 6은 1이 아니기 때문에 제거 합니다.

1, 2, 3, 2, 4, 5, 10 (제거 1)

6을 제거하자 1을 찾을 수 있습니다. 순서대로 3까지 나오고 순서대로 정렬되지 않는 4번째 숫자 2는 제거합니다.

1, 2, 3, 4, 5, 10 (제거 2)

다음으로 정렬된 숫자가 5까지 존재하고 나머지 10은 삭제 합니다.

1, 2, 3, 4, 5 (제거 3)

이렇게 모든 숫자가 제자리를 찾았고 총 3개의 숫자를 삭제하였습니다. 이렇게 3을 출력하면 문제가 해결 됩니다.

코드 작성하기

그럼 코드를 작성해 보겠습니다.

입력 받기

N = int(input())
arr = list(map(int, input().split()))

전체 카드의 개수 N을 입력 받습니다. 다음으로 제자리를 찾아야 할 숫자들의 리스트 arr을 입력 받습니다.

제자리가 아닌 카드 제거하기

start = 1
cnt = 0
for a in arr:
    if a == start:
        start += 1
    else:
        cnt += 1

print(cnt)

start는 1부터 시작하여 찾아야할 숫자들 입니다. cnt는 제거해야할 숫자들의 카운트 입니다. 최종적으로 cnt를 출력할 것입니다. arr에 있는 원소들을 하나하나 start와 비교합니다. 즉 1이 어디있는지 찾는 것입니다. 만약 1을 만나게 되면 start는 2가 됩니다. 그렇게 다음 숫자를 찾고, 2를 찾으면 3을 찾는 것입니다. 이렇게 전체 리스트를 뒤져가며 제자리 상태의 카드만 남겨둡니다.
만약 start와 비교해서 같지 않다면 제거해야할 숫자입니다. cnt 값을 늘려가며 제거해야할 숫자들의 카운트값을 올려줍니다. 마지막으로 cnt 값을 출력하면 이 문제는 해결 됩니다.

전체 코드

전체 코드를 확인해 보겠습니다.

N = int(input())
arr = list(map(int, input().split()))

start = 1
cnt = 0
for a in arr:
    if a == start:
        start += 1
    else:
        cnt += 1

print(cnt)