week10 (실습 문제)

Quicksort Array

• 사용자로부터 입력받을 숫자들의 수 N을 입력 받고, 다음 행에서 공백으로 구분된 N개의 숫자를 입력받아서 이를 내림차순으로 정렬한 결과를 출력하세요.
• 임의의 N에 대해서 처리 가능하도록 동적 할당을 사용하세요.
• 입력받는 N개의 숫자들은 모두 int 의 범위 내에 존재한다고 가정합니다.
• 정렬할 때는 stdlib.h에 있는 qsort 함수를 활용하세요.
• qsort 함수는 주어진 배열을 오름차순으로 정렬합니다.
• qsort 함수의 원형은 다음과 같습니다.

void qsort( void *ptr, size_t count, size_t size, int (*comp)(const void *, const void *) );

• 위의 함수에서 각 인자들은 다음과 같습니다.
• ptr: 정렬할 array의 첫 번째 요소에 대한 주소(포인터)
• count: 정렬할 요소들의 개수(배열의 크기)
• size: 각 요소들의 크기(byte 단위 크기)
• comp: 2개의 요소들을 비교하는 함수를 가리키는 포인터

비교하는 함수 comp 의 경우 오름차순 정렬을 기준으로, 두 개의 인자로 받은 값에 대해 비교하여 다음과 같이 정수를 return해야 합니다.

첫 번째 요소가 두 번째 요소보다 작은 경우 음수를 반환
첫 번째 요소와 두 번째 요소가 같다면 0을 반환
첫 번째 요소가 두 번째 요소보다 크다면 양수를 반환

입력1

5
97 23 100 38 15​

출력1

100 97 38 23 15​

정답 코드

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

int comp(const void *a, const void *b) {
      if (*(int*)a<*(int*)b) return 1;
      if(*(int*)a==*(int*)b) return 0;
      return -1;
}

int main(){
      int n;
      scanf("%d", &n);
      
      int *a=(int*)malloc(sizeof(int)*n);
      for(int i=0;i<n;i++){
            scanf("%d", &a[i]);
      }
      
      qsort(a, n, sizeof(int), comp);

      for(int i=0;i<n;i++){
            printf("%d", a[i]);
            if(i != n - 1) printf(" ");
      }

      free(a);
}​

Transpose Matrix

• 사용자로부터 행렬의 행(N)과 열(M)을 나타내는 자연수 N과 M을 공백으로 구분하여 입력받은 후, 줄 단위로 공백으로 구분된 각 행에 들어갈 원소의 값을 입력받으세요. 그 후 입력받은 행렬에 대해 전치(Transpose)를 수행한 행렬을 한 줄에 한 행씩 각 열을 공백으로 구분하여 출력하세요.
• 임의의 N과 M 값에 대해 동작할 수 있도록 동적 메모리 할당을 사용하세요.
• 각 원소의 값은 int 범위 내에 있는 정수로 입력받는다고 가정합니다.
• 전치연산을 수행하는 코드는 배열을 전달받아 연산하는 별도의 함수를 선언하여 처리하세요.
• 함수의 원형은 수업에서 배운 2차원 배열을 전달하는 방법 중 어떠한 형태를 사용해도 무방합니다.

입력1

2 2
1 2
3 4​

출력1

1 3
2 4​

입략2

3 2
1 2
3 4
5 6​

출력2

1 3 5
2 4 6​

정답 코드

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

int main() {
	int n,m;
	scanf("%d%d", &n, &m);

	int **a=(int**)malloc(sizeof(int*)*n);
	for(int i=0; i<n; i++) {
		a[i]=(int*)malloc(sizeof(int)*m);
	}

	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			scanf("%d", &a[i][j]);
		}
	}

	for(int i=0; i<m; i++) {
		for(int j=0; j<n; j++) {
			printf("%d ", a[j][i]);
		}
		printf("\n");
	}

	for(int i=0; i<n; i++) {
		free(a[i]);
	}
	free(a);
}​

Word Search

• 사용자로부터 단어를 입력받아서 해당 단어가 주어진 파일 내에 존재하는지 확인하여, 그 위치를 출력하세요.
• 대소문자는 구분하지 않습니다.
• 알파벳으로만 구성된 파일들의 예시는 input01.txt, input02.txt, input03.txt에서 확인할 수 있습니다.
• 사용자가 입력한 단어를 주어진 문서에서 찾아주되, 첫 줄에서 첫 글자의 위치, 두 번째 줄에는 마지막 글자의 위치를 출력하세요.
• 위치를 출력할 때의 기준은 2차원 배열에서의 index로 상정합니다.
• 예를 들어 아래의 예제에서 CBA를 검색할 경우에는 시작 위치의 index는 0,2, 끝 위치는 0,0이 됩니다.

ABCD
BCDA
FDAB
EABG

• 위치 출력 시의 각 차원의 값은 쉼표(,)로 구분해주세요. 
• 해당 단어가 여러 개 존재할 경우 2차원 행렬 기준으로 행이 가장 0에 가까운 것부터 열이 가장 0에 가까운 것을 찾아서 하나만 출력하세요. 
• 단어 내에 포함된 글자 사이의 연결관계는 상/하/좌/우이며, 대각선 방향으로도 연결될 수 있습니다. 
• 단, 연결 방향은 탐색 도중에 바뀌지 않습니다. 
• 찾는 단어가 파일 내에 존재하지 않을 경우 -1, -1을 출력하세요.

입력1

parallel​

출력1

0,3
0,10

정답 코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

int dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };

int main(int argc, char *argv[]) {
    FILE *fp;
    fp = fopen("input1.txt", "r");

    if (fp == NULL) {
        printf("NULL");
        return 1;
    }

    char d[104][104] = { 0 };
    int row = 0, col = 0;

    while (fgets(d[row], sizeof(d[row]), fp) != NULL) {
        d[row][strcspn(d[row], "\n")] = '\0';
        for (int i = 0; d[row][i]; i++) {
            d[row][i] = tolower(d[row][i]);
        }
        col = strlen(d[row]);
        row++;
    }

    fclose(fp);

    char line[104];
    scanf("%s", line);
    int len = strlen(line);
    for (int i = 0; i < len; i++) {
        line[i] = tolower(line[i]);
    }

    for (int x = 0; x < row; x++) {
        for (int y = 0; y < col; y++) {
            if (d[x][y] == line[0]) {
                for (int dir = 0; dir < 8; dir++) {
                    int nx = x, ny = y;
                    int k;
                    for (k = 1; k < len; k++) {
                        nx += dx[dir];
                        ny += dy[dir];
                        if (nx < 0 || ny < 0 || nx >= row || ny >= col) break;
                        if (d[nx][ny] != line[k]) break;
                    }
                    if (k == len) {
                        printf("%d,%d\n", x, y);
                        printf("%d,%d\n", nx, ny);
                        return 0;
                    }
                }
            }
        }
    }

    printf("-1,-1\n");

    return 0;
}

Anagram

• Anagram은 단어나 문장을 구성하고 있는 문자의 순서를 바꾸어 다른 단어나 문장을 만드는 것입니다. (예시: heart <=> earth / I am Lord Voldemort <=> Tom Marvolo Riddle) 사용자로부터 문자열을 입력받아서 주어진 사전 내에서 anagram을 이루는 단어가 있는지 확인하여 출력하세요.
• 사전은 repository에 주어진 american-english-large.txt 파일을 읽어서 사용하세요.
• 입력으로는 영문 대소문자로 구성된 한 단어만 들어온다고 가정합니다. (특수문자 및 공백 입력은 없습니다.)
• 매칭 시에 대소문자는 무시하고 처리하세요.
• 사전에서 anagram을 이루는 첫 번째 단어만 모두 소문자로 출력하세요.
• Anagram을 이루는 단어가 없을 경우 -1을 출력해주세요.

ex)
input1.txt

appalachia
gaja​

입력1

ahalaaicpp​

출력1

appalachia​

입력2

gajae

출력2

-1

정답 코드

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

int comp(const void *a, const void *b) {
    return (*(char *)a - *(char *)b);
}

int main() {
    FILE *fp;
    fp = fopen("input1.txt", "r");

    if (fp == NULL) {
        printf("NULL\n");
        return 1;
    }

    char c[104], line[104];
    fgets(c, sizeof(c), stdin);
    c[strcspn(c, "\n")] = '\0';

    for (int i = 0; i < strlen(c); i++) {
        c[i] = tolower(c[i]);
    }

    int len = strlen(c);
    qsort(c, len, sizeof(char), comp);

    while (fgets(line, sizeof(line), fp) != NULL) {
        line[strcspn(line, "\n")] = '\0';

        if (strlen(line) != len) continue;

        char temp[104];
        for (int i = 0; i < len; i++) {
            temp[i] = tolower(line[i]);
        }
        temp[len] = '\0';

        qsort(temp, len, sizeof(char), comp);

        if (strcmp(temp, c) == 0) {
            for (int i = 0; i < strlen(line); i++) {
                line[i] = tolower(line[i]);
            }
            printf("%s\n", line);
            fclose(fp);
            return 0;
        }
    }

    fclose(fp);
    printf("-1\n");
    return 0;
}

Sudoku Validator

• 사용자로부터 9x9 크기의 스도쿠 판을 입력받아 아래의 규칙에 어긋난 부분이 없는지 확인하여 올바르게 채워진 경우 true, 규칙에 어긋난 부분이 있는 경우 false를 출력하세요.
• 각 행은 1부터 9까지의 숫자가 중복없이 배치됩니다.
• 각 열에도 1부터 9까지의 숫자가 중복없이 배치됩니다.
• 3x3의 크기로 나누어진 9개의 내부 구획 내에서도 1부터 9까지의 숫자가 중복없이 배치됩니다.
• 각 숫자는 쉼표(,)로 구분합니다.
• 비어있는 칸은 마침표(.)로 나타냅니다.
• 입력으로 주어지는 스도쿠 판은 일부만 채워져 있을 수 있습니다. (비어있는 칸을 추론하여 채우기 위한 충분한 숫자가 채워져 있지 않을 수 있습니다.) 이번 과제에서는 입력으로 주어진 스도쿠 판에서 값이 채워진 곳들만 위의 규칙에 어긋난 부분이 없는지 확인하여 출력하시면 됩니다.

입력1

5,3,.,.,7,.,.,.,.
6,.,.,1,9,5,.,.,.
.,9,8,.,.,.,.,6,.
8,.,.,.,6,.,.,.,3
4,.,.,8,.,3,.,.,1
7,.,.,.,2,.,.,.,6
.,6,.,.,.,.,2,8,.
.,.,.,4,1,9,.,.,5
.,.,.,.,8,.,.,7,9​

출력1

true​

입력2

5,3,.,.,7,.,.,.,.
6,.,.,1,9,5,.,.,.
.,9,8,.,.,.,.,6,.
8,.,.,.,6,.,.,.,3
4,.,.,8,.,3,.,.,1
7,.,.,.,2,.,.,.,6
.,6,.,.,.,.,2,8,.
.,.,.,4,1,9,.,.,5
.,.,.,.,8,.,.,7,3​

 

출력2

false​

정답 코드

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

int d[14][14]={0};
int main(){
      for(int i=0;i<9;i++){
           char line[24];
           scanf("%s", line);
           
           char *token=strtok(line, ",");
           int idx=0;
           while(token!=NULL){
                 if(token[0]!='.') d[i][idx]=atoi(token);
                 token=strtok(NULL,",");
                 idx+=1;
           }
      }
      
      for(int i=0;i<9;i++){
            int a[14]={0};
            for(int j=0;j<9;j++){
                  if(a[d[i][j]]&&d[i][j]!=0) {
                        printf("false");
                        return 0;
                  }
                  a[d[i][j]]+=1;
            }
      }
      
      for(int i=0;i<9;i++){
            int a[14]={0};
            for(int j=0;j<9;j++){
                  if(a[d[j][i]]&&d[j][i]!=0){
                        printf("false");
                        return 0;
                  }
                  a[d[j][i]]+=1;
            }
      }
      
      printf("true");
      return 0;
}