[백준/C언어] 5597번 - 과제 안 내신 분..?

백준 웹사이트 "5597번 - 과제 안 내신 분..?" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

5597번: 과제 안 내신 분..?

---

소스 코드

#include <stdio.h>

int main(void){
    int arr[30] = {0};  // initialize all elements to 0
    for(int i=0; i<28; i++){
        int n;
        scanf("%d", &n);
        arr[n-1]++;
    }

    for(int j=0; j<30; j++){
        if(arr[j]==0)
            printf("%d\n", j+1);
    }
}

---

문제 풀이

  1 부터 30까지 숫자 중, 등장하지 않는 숫자 2개를 찾는 문제입니다. 이 문제를 쉽게 푸는 방법은 바로 '인덱스를 적극적으로 활용해주는 것'입니다. 우선, 길이 30의 배열 arr을 선언하고 모든 배열 요소의 값을 0으로 초기화합니다. 그 후, 입력으로 주어지는 28개의 숫자를 각각 살펴보고, 해당 숫자보다 1만큼 작은 인덱스의 배열 값을 1로 올려줍니다. 예를 들어, 3이라는 숫자가 입력되었다면 arr[2]의 값을 0에서 1로 바꿔줍니다. 그 다음 입력되는 숫자가 1이라면, arr[0]을 0에서 1로 바꿔줍니다. 이를 28개의 숫자에 대해 반복하면, 배열 arr 내에서 28개의 배열 값은 1로 바뀌고, 2개의 배열 값은 0으로 남아있을 것입니다. 이 2개의 배열 요소는 등장하지 않는 2개의 숫자를 의미하겠죠? 둘의 인덱스를 구하고 1만큼 더하면, 등장하지 않는 두 숫자를 찾을 수 있습니다.

  설명이 좀 헷갈릴 수 있어, '예제 입력 2'로 전체 코드를 살펴보겠습니다. 입력되는 28개의 숫자는 '9, 30, 6, 12, ... , 1, 24, 25' 입니다. 각 숫자 n이 입력될 때마다 arr[n-1]의 값이 0에서 1로 바뀝니다. 따라서, 순서대로 'arr[8], arr[29], arr[5], arr[11], ... , arr[0], arr[23], arr[24]'의 값이 1이 됩니다. 그러면 배열 arr은 arr[1], arr[7]을 제외한 모든 배열 요소가 1인 상태입니다. 여기까지가 소스 코드의 Line 9입니다. Line 11 ~ 14의 for문은 다시 배열 arr을 확인하여, 값이 0인 배열 요소들을 찾습니다. arr[1], arr[7]이 찾아지겠죠? 마지막 출력은 인덱스보다 1 큰 숫자가 출력되어, 숫자 2와 8이 차례로 출력됩니다.