7월 10일 [4일차] 알고리즘 코딩 테스트(51번~70번)

📙 학습 자료

💡 재귀, 정렬, 해시

51. 중복된 문자 제거
52. 모스부호(1)
53. 2차원으로 만들기
54. 팩토리얼
55. A로 B 만들기
56. 가까운 수
57. k의 개수
58. 진료순서 정하기
59. 숨어있는 숫자의 덧셈(2)
60. 한 번만 등장한 문자
61. 이진수 더하기
62. 컨트롤 제트
63. 7의 개수
64. 소인수 분해
65. 공 던지기
66. 영어가 싫어요
67. 잘라서 배열로 저장하기
68. 문자열 계산하기
69. 구슬을 나누는 경우의 수
    • 조합 ➡️ 참고 사이트 : https://coding-factory.tistory.com/606
70. 외계어 사전

---

🏆 오늘의 미션

• 없는 숫자 더하기 - Level 1
• 완주하지 못한 선수 - Level 1

---

☢️ 풀이예시 - 먼저 풀어보고 나서 참고하기 🐸

• 중복된 문자 제거

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

int hasIT(const char *list, const char alpha) {
    for(int i=0;  ;i++) {
        char c = list[i];
        if(!c) break;
        if(c == alpha) return 1;
    }
    return 0;
}

char* solution(const char* my_string) {
    int l = strlen(my_string);
    char* answer = (char*)calloc(l+1, sizeof(char));
    int countA = 0;

    for(int i=0; i<l ;i++) {
        char c = my_string[i];
        if(!hasIT(answer, c)) answer[countA++] = c;
    }

    return answer;
}

• 모스부호(1)

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

char* solution(const char* letter) {
    int l = strlen(letter);
    char* cpyLetter = (char*)calloc(l+1, sizeof(char));
    strcpy(cpyLetter, letter);
    char* answer = (char*)calloc(l+1, sizeof(char));
    char* ptr = 0;
    int countA = 0;

    const char* morse[] = { ".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.." };

    ptr = strtok(cpyLetter, " ");
    while (ptr) {
        printf("%s\n", ptr);
        for (int i = 0; i < 26; i++) {
            if (!strcmp(morse[i], ptr)) {
                answer[countA++] = i + 'a';
                break;
            }
        }
        ptr = strtok(NULL, " ");
    }

    return answer;
}

• 2차원으로 만들기

  2차원 동적 배열만들기 (포인터의 배열을 만들고, 각 포인터에 몸체를 붙여넣는다)

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int** solution(int num_list[], size_t num_list_len, int n) {
    int row = num_list_len / n;
    int** answer = (int**)calloc(row, sizeof(int *));
    
    for(int i=0; i<row; i++) {
        answer[i] = (int*)calloc(n, sizeof(int));
        for(int j=0; j<n; j++){
            answer[i][j] = num_list[i*n + j];
        }
    }
    return answer;
}

• 팩토리얼

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int solution(int n) {
    int answer = 1;
    int facto = 1;
    
    for( ; ; answer++) {
        facto *= answer;
        if(facto > n) break;
    }
    return answer-1;
}

• A로 B 만들기

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

int compare(char *a, char *b) {
    return *a - *b;
}
int solution(const char* before, const char* after) {
    int answer = 0;
    int lb = strlen(before);
    int la = strlen(after);
    char *b = (char *)calloc(lb+1, sizeof(char));
    char *a = (char *)calloc(la+1, sizeof(char));

    strcpy(b, before);
    strcpy(a, after);

    qsort(b, lb, sizeof(char), compare);
    qsort(a, la, sizeof(char), compare);
    printf("%s : %s", b, a);

    if(strcmp(b,a) == 0) answer = 1;

    return answer;
}

• 가까운 수

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int solution(int array[], size_t array_len, int n) {
    int answer = 0;
    int min = 100;
    
    for(int i=0; i<array_len; i++) {
        int gap = array[i] - n;   // n과의 거리 저장
        if(gap < 0) gap *= -1;    // gap이 음수이면, 양수로 변환
        if(gap == min) {          // 이미 최소거리가 있더라도, 작은 수라면 교체해야 함
            if(answer > array[i]) {
                answer = array[i];
            }
        } else if(gap < min) {    // 현재 최소거리보다 더 가까운 수가 있으면 교체해야 함
            min = gap;
            answer = array[i];
        }
    }
    
    return answer;
}

• k의 개수

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int solution(int i, int j, int k) {
    int answer = 0;
    
    for(int num=i; num<=j; num++) {
        int n = num;
        for( ; n ; n/=10) {
            if(n%10 == k) answer++;
        }
    }
    
    return answer;
}

• 진료 순서 정하기

  구조체 필요

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct _patient {
    int em;
    int index;
} P;

int compare(P *a, P *b) {
    // return (*b).em - (*a).em;
    return b->em - a->em;
}

int* solution(int emergency[], size_t emergency_len) {
    int l = emergency_len;
    int* answer = (int*)calloc(l, sizeof(int));
    P* patient = (P*)calloc(l, sizeof(P));
    
    for(int i=0; i<l; i++) {
        patient[i].em = emergency[i];
        patient[i].index = i;
    }
    
    qsort(patient, l, sizeof(P), compare);
    
    for(int i=0; i<l; i++) {
        answer[patient[i].index] = i+1;
    }
    return answer;
}

• 숨어 있는 숫자의 덧셈(2)

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

int solution(const char* my_string) {
    int answer = 0;
    int l = strlen(my_string);
    char *str = (char*)calloc(l+1, sizeof(char));
    strcpy(str, my_string);
    
    char *ptr;
    char *delimeter = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    ptr = strtok(str, delimeter);
    while(ptr) {
        answer += atoi(ptr);
        ptr = strtok(NULL, delimeter);
    }
    return answer;
}

• 한번만 등장한 문자

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

char* solution(const char* s) {
    int l=strlen(s);
    char* answer = (char*)calloc(l+1, sizeof(char));
    int* alpha = (int*)calloc(26, sizeof(int));
    int countA=0;
    
    for(int i=0; i<l; i++) {     // 한번 쭉 읽으면서 alphabet 출현 횟수 카운트
        char c = s[i];
        alpha[c-'a']++;
    }

    for(int i=0; i<26; i++) {    // 알파벳 출현횟수가 1인 경우만 answer에 덧붙여주기
        if(alpha[i] == 1)
            answer[countA++] = i + 'a';
    }
    return answer;
}