tenid's dev

1. 문제 설명

길이가 n이고, "수박수박수박수...."와 같은 패턴을 유지하는 문자열을 리턴하는 함수, solution을 완성하세요. 예를들어 n이 4이면 "수박수박"을 리턴하고 3이라면 "수박수"를 리턴하면 됩니다.

- 제한 사항

• n은 길이 10,000이하인 자연수입니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

string solution(int n) {
	string answer = "";

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

		i % 2 ? answer += "박" : answer += "수";

	}


	return answer;
}

3. 정리

n만큼 for문으로 순회하면서 인덱스가 홀수 일 때 "박", 짝수 일 때 "수" 문자를 추가하여 준다.

전체 시간 복잡도는 n만큼 순회하므로  O(n) 이다.

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

1. 문제 설명

단어 s의 가운데 글자를 반환하는 함수, solution을 만들어 보세요. 단어의 길이가 짝수라면 가운데 두글자를 반환하면 됩니다.

- 제한 사항

• s는 길이가 1 이상, 100이하인 스트링입니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

string solution(string s) {
	string answer = "";
	int a = s.size() / 2;


	if (s.size() % 2 == 0) {

		answer += s[a - 1];
		answer += s[a];
	}
	else {
		answer += s[a];
	}


	return answer;
}

3. 정리

2와 나머지 연산을 통해 짝수와 홀수 로직을 분리하여 구현한다.

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

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

1. 문제 설명

프로그래머스 모바일은 개인정보 보호를 위해 고지서를 보낼 때 고객들의 전화번호의 일부를 가립니다.
전화번호가 문자열 phone_number로 주어졌을 때, 전화번호의 뒷 4자리를 제외한 나머지 숫자를 전부 *으로 가린 문자열을 리턴하는 함수, solution을 완성해주세요.

- 제한 사항

• phone_number는 길이 4 이상, 20이하인 문자열입니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

string solution(string phone_number) {
    
    int LastIndex = phone_number.length()-4;
    
    
    for(int i=0; i<LastIndex ; i++)
        phone_number[i]='*';
    
    
    return phone_number;
}

3. 정리

문자열 전체 길이에서 뒷 4개의 문자는 변경하지 않아야 하므로 [전체 문자열 길이-4] 까지의 문자열 인덱스까지 for문으로 순회하여 '*' 문자로 변경하여 준다.

전체 시간 복잡도는 문자열의 원소의 갯수-4만큼 순회하므로  O(n) 이다.

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

1. 문제 설명

0부터 9까지의 숫자 중 일부가 들어있는 정수 배열 numbers가 매개변수로 주어집니다. numbers에서 찾을 수 없는 0부터 9까지의 숫자를 모두 찾아 더한 수를 return 하도록 solution 함수를 완성해주세요.

- 제한 사항

• 1 ≤ numbers의 길이 ≤ 9
• 0 ≤ numbers의 모든 원소 ≤ 9
• numbers의 모든 원소는 서로 다릅니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> numbers) {
	int answer = 45;


	for (int i = 0; i < numbers.size(); i++) 
        answer -= numbers[i];

	return answer;

}

3. 정리

제한 사항을 보면 길이는 최대 9이며, 원소는 서로 다르다. 즉, 최악의 경우 배열안에 0~9까지의 숫자가 각각 들어간다. 이 문제는 간단히 해결하기 위해 최악의 경우 원소들의 총합인 45에서 numbers 배열에 있는 원소들을 빼면 없는 숫자들의 총합이 나오게 된다!

전체 시간 복잡도는 배열의 원소의 갯수만큼 순회하므로  O(n) 이다.

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

1. 문제 설명

1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될 때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다.

1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.

예를 들어, 주어진 수가 6이라면 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 이 되어 총 8번 만에 1이 됩니다. 위 작업을 몇 번이나 반복해야 하는지 반환하는 함수, solution을 완성해 주세요. 단, 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 –1을 반환해 주세요.

- 제한 사항

• 입력된 수, num은 1 이상 8,000,000 미만인 정수입니다

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

int solution(int num) {
	long numL = num;
	int cnt = 0;


	while (numL != 1) {
    
            if (cnt >= 500){
                    cnt = -1;
                    break;
                }

            numL = (numL % 2 == 0) ? numL / 2 : numL * 3 + 1;
            cnt++;

	}

	return cnt;
}

3. 정리

while문을 통해 주어진 작업을 그대로 수행하며 cnt(횟수)를 체크 한다 이 때 종료 조건은 1이 될 때까지와 cnt(횟수)가 500이 되었을 경우이다.

전체 시간 복잡도는

• 짝수(numL % 2 == 0) → numL /= 2 → 크기가 절반으로 감소 → O(log n)
• 홀수(numL % 2 == 1) → numL = numL * 3 + 1 → 크기가 커질 수도 있음.
• 하지만, 일반적으로 크기가 커지더라도 몇 단계 후 짝수가 되어 감소.
• 따라서 반복 횟수는 대략 O(log n).

현실적으로는 O(log n), 하지만 최악의 경우 O(1)으로 제한됨.

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

1. 문제 설명

String형 배열 seoul의 element중 "Kim"의 위치 x를 찾아, "김서방은 x에 있다"는 String을 반환하는 함수, solution을 완성하세요. seoul에 "Kim"은 오직 한 번만 나타나며 잘못된 값이 입력되는 경우는 없습니다.  

- 제한 사항

• seoul은 길이 1 이상, 1000 이하인 배열입니다.
• seoul의 원소는 길이 1 이상, 20 이하인 문자열입니다.
• "Kim"은 반드시 seoul 안에 포함되어 있습니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

string solution(vector<string> seoul) {
	string answer = "김서방은 ";

	for (int i = 0; i < seoul.size(); i++) {
		if (seoul[i] == "Kim") {
			answer += to_string(i) ;
			break;
		}

	}
    
	return answer+="에 있다";
}

3. 정리

for문을 이용하여 배열을 순회하여 "Kim" 문자열이 있는 인덱스를 찾아낸다.

전체 시간 복잡도를 단계별로 분석하면

최종적으로 O(n) 이다.

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