tenid's dev

1. 문제 설명

문자열 s의 길이가 4 혹은 6이고, 숫자로만 구성돼있는지 확인해주는 함수, solution을 완성하세요. 예를 들어 s가 "a234"이면 False를 리턴하고 "1234"라면 True를 리턴하면 됩니다.

- 제한 사항

• s는 길이 1 이상, 길이 8 이하인 문자열입니다.
• s는 영문 알파벳 대소문자 또는 0부터 9까지 숫자로 이루어져 있습니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

bool solution(string s) {
	bool answer = true;

	if (s.size() != 4 && s.size() != 6)
		return false;

	for (int i = 0; i < s.size(); ++i) {
		
		if ('0' > s[i] || '9' < s[i])
			return false;
	}

	return answer;
}

3. 정리

먼저 빠르게 판단할 수 있는 조건인 4 혹은 6이 아니면 false를 바로 리턴하고 해당 조건에 걸리지 않으면 문자열중에 0~9문자가 있는지를 검사한다.

전체 시간 복잡도는 최대 문자열의 길이가 8이기 때문에 상수시간 O(1) 이다.

출처 :https://school.programmers.co.kr/learn/courses/30/lessons/12918

1. 문제 설명

새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이용료가 100이었다면 2번째에는 200, 3번째에는 300으로 요금이 인상됩니다.
놀이기구를 count번 타게 되면 현재 자신이 가지고 있는 금액에서 얼마가 모자라는지를 return 하도록 solution 함수를 완성하세요.
단, 금액이 부족하지 않으면 0을 return 하세요.

- 제한 사항

• 놀이기구의 이용료 price : 1 ≤ price ≤ 2,500, price는 자연수
• 처음 가지고 있던 금액 money : 1 ≤ money ≤ 1,000,000,000, money는 자연수
• 놀이기구의 이용 횟수 count : 1 ≤ count ≤ 2,500, count는 자연수

2. 풀이 코드

using namespace std;

long long solution(int price, int money, int count)
{
	long long answer = 0;

	long long payTotal = 0;

	for (int i = 1; i <= count; i++)
	{
		payTotal += i * price;
	}

	answer = payTotal > money ? payTotal - money : 0;


	return answer;
}

3. 정리

for문을 이용하여 지불할 금액의 총합을 구한 후 지불할 금액이 소지 금액보다 크다면 payTotal - money = 부족한 금액을 아니라면 0을 리턴한다. 

전체 시간 복잡도는 O(n) 이다.

출처 :https://school.programmers.co.kr/learn/courses/30/lessons/82612

1. 문제 설명

문자열 s에 나타나는 문자를 큰것부터 작은 순으로 정렬해 새로운 문자열을 리턴하는 함수, solution을 완성해주세요.
s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 간주합니다.

- 제한 사항

• str은 길이 1 이상인 문자열입니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

string solution(string s) {
	int n = s.length();

	for (int i = 1; i < n; i++)
	{
		char key = s[i];
		int j = i - 1;

		while (j >= 0 && s[j] < key)
		{
			s[j + 1] = s[j];
			j--;
		}

		swap(s[j + 1], key);

	}

	return s;
}

3. 정리

문자들은 정렬 알고리즘(삽입정렬) 구현하여 정렬 하였다.

전체 시간 복잡도는 삽입 정렬의 시간 복잡도인 O(n²) 이다.

출처 :https://school.programmers.co.kr/learn/courses/30/lessons/12917

1. 설명

• pivot을 하나 설정하여 작은 값은 왼쪽, 큰 값은 오른쪽에 배치
• 평균적으로 O(n log n), 최악의 경우 O(n²)
• 메모리 추가 사용 없이 빠른 속도 제공 (제자리 정렬)

2. 코드

#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            swap(arr[++i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    quickSort(arr, 0, arr.size() - 1);

    for (int num : arr) cout << num << " ";
}

1. 설명

• 현재 요소를 앞쪽 정렬된 부분과 비교하여 적절한 위치에 삽입.
• O(n²)의 시간복잡도이지만, 거의 정렬된 경우 매우 빠름 (O(n)).
• 데이터가 적거나 정렬이 거의 완료된 경우에 적합.

2. 코드

#include <iostream>
#include <vector>

using namespace std;

void insertionSort(vector<int>& arr) {
    int n = arr.size();

    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    insertionSort(arr);

    for (int num : arr) cout << num << " ";
}

1. 설명

• 가장 작은(혹은 가장 큰) 값을 찾아 **제일 앞(혹은 뒤)**으로 이동.
• O(n²)의 시간복잡도를 가짐.
• 작은 데이터에 적합하지만, 성능이 좋지 않음.

2. 코드

#include <iostream>
#include <vector>

using namespace std;

void selectionSort(vector<int>& arr) {
	int n = arr.size();

	for (int i = 0; i < n - 1; i++) {
		int minIndex = i;

		for (int j = i + 1; j < n; j++)
		{
			if (arr[j] < arr[minIndex])
				minIndex = j;
		}
		swap(arr[i], arr[minIndex]);
	}

}


int main() {
	vector<int> arr = { 64, 25, 12, 22, 11 };
	selectionSort(arr);

	for (int num : arr) cout << num << " ";

}