코드업(codeup) 3109 : 정올 참여 학생 리스트 만들기 2 C언어

▶문제 : 정올 참여 학생 리스트 만들기 2 (codeup.kr)

정올 참여 학생 리스트 만들기 2

 

▶코드 작성

#include <stdio.h>
#include <string.h>

typedef struct {
    char id;
    int num;
    char name[11];
    int f;
} INFO;

INFO info[20000];

int main()
{
    int n, dig[5];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf(" %c %d %s", &info[i].id, &info[i].num, info[i].name);
        info[i].f = 0;//정렬 때 사용
    }
    for (int i = 0; i < 5; i++) {
        scanf("%d", &dig[i]);
    }

    for (int i = 0; i < n; i++)//id가 D일 때 맨 앞 데이터 삭제
    {//여기서 나는 같은 num을 맨 앞으로 넣지 않았으므로 순서가 거꾸로 -> 맨 뒤가 맨 앞임
        if (info[i].id == 'D')
        {
            for (int j = i - 1; j >= 0; j--)//D가 지금 들어왔다 생각하여 j = i - 1
            {//뒤에서부터 D와 같은 num값을 찾음
                if (info[i].num == info[j].num)
                {
                    info[j].num = 0;//맨 앞(맨 뒤)값 삭제
                    break;
                }
            }
            info[i].num = 0;//D값 또한 삭제
        }
    }

    int cnt = 0;//새로 만든 배열의 최대값
    for (int i = 0; i < n; i++)//삭제된 I,D값을 제외한 I값들 다시 배열로 만듬
    {
        if (info[i].id == 'I' && info[i].num > 0)
        {
            info[cnt++] = info[i];
        }
    }

    INFO temp;
    int min;
    for (int i = 0; i < cnt - 1; i++)//선택정렬
    {
        min = i;
        for (int j = i + 1; j < cnt; j++)
        {
            if (info[min].num > info[j].num)//작은 num값 찾기
            {
                min = j;
            }
            else if (info[min].num == info[j].num && info[j].f == 0)
            {//num값이 같으면 f가 0인지 확인하여 교환
                min = j;
            }//f가 0이면 맨 앞 값이라는 증명
        }
        if (min != i)
        {
            temp = info[i];
            info[i] = info[min];
            info[min] = temp;
            info[min].f = 1;
        }//f를 1로 하여 맨 뒤 값이라는 증명을 함
    }

    for (int i = 0; i < 5; i++)
    {
        printf("%d %s\n", info[dig[i] - 1].num, info[dig[i] - 1].name);
    }

    return 0;
}

 

▶해석

테스트 케이스를 그대로 구조체 배열에 입력받아서 첫 번째로 한 일은 id가 D인 데이터를 찾아서 D는 같은 num값을 가진 I의 맨 앞 데이터를 삭제하는 역할이므로 맨 앞 데이터를 num=0으로 하여 삭제하였다. 여기서 맨 앞 데이터는 구조체 배열에서 같은 num값을 가진 I 중 맨 뒤 데이터를 말한다. 맨 뒤가 가장 최근에 입력받은 데이터이기 때문이다. 그런데 진짜 맨 뒤가 아니라 D를 입력받은 자리( i ) 이전에 입력받은 값들 중 맨 뒤 데이터를 말하는 것이다.

for (int i = 0; i < n; i++) //id가 D일 때 맨 앞 데이터 삭제
{ //여기서 나는 같은 num을 맨 앞으로 넣지 않았으므로 순서가 거꾸로 -> 맨 뒤가 맨 앞임
    if (info[i].id == 'D')
    {
        for (int j = i - 1; j >= 0; j--) //D가 지금 들어왔다 생각하여 j = i - 1
        { //뒤에서부터 D와 같은 num값을 찾음
            if (info[i].num == info[j].num)
            {
                info[j].num = 0; //맨 앞(맨 뒤)값 삭제
                break;
            }
        }
        info[i].num = 0; //D값 또한 삭제
    }
}

 

두 번째로는 위 과정으로 삭제된 I,D데이터들을 제외한 I데이터들로만 이루어진 배열을 다시 만들었다.

int cnt = 0; //새로 만든 배열의 최대값
for (int i = 0; i < n; i++) //삭제된 I,D값을 제외한 I값들 다시 배열로 만듬
{
    if (info[i].id == 'I' && info[i].num > 0)
    {
        info[cnt++] = info[i];
    }
}

 

세 번째로는 선택정렬을 이용하여 제일 작은 값을 맨 앞으로 교환하여 정렬하였다. 여기서 교환할 때 맨 앞이었던 데이터가 뒤로 밀려나는 것이므로 이 데이터가 같은 num값을 비교할 때 맨 앞으로 가야 하는지 맨 뒤로 가야 하는지 알 수가 없다. (물론 맨 앞에 있었으므로 맨 뒤로 가야 한다) 그것을 방지하기 위해 f를 1로 하여 맨 뒤로 정렬시켜야 한다는 것을 알려준다. 그래서 2중 for문 안에서 같은 num값을 찾았을 때 f가 0이면 한 번도 교환된 적이 없으므로 맨 앞으로 가야 한다는 결론이 난다. 반대로 f가 1이면 앞에서 왔다는 것이므로 최대한 뒤쪽으로 배치해야 된다.

INFO temp;
int min;
for (int i = 0; i < cnt - 1; i++) //선택정렬
{
    min = i;
    for (int j = i + 1; j < cnt; j++)
    {
        if (info[min].num > info[j].num) //작은 num값 찾기
        {
            min = j;
        }
        else if (info[min].num == info[j].num && info[j].f == 0)
        { //num값이 같으면 f가 0인지 확인하여 교환
            min = j;
        } //f가 0이면 맨 앞 값이라는 증명
    }
    if (min != i)
    {
        temp = info[i];
        info[i] = info[min];
        info[min] = temp;
        info[min].f = 1;
    } //f를 1로 하여 맨 뒤 값이라는 증명을 함
}