이것 저것 &

어려웠습니다...

우선 첫번째로 고려하셔야 하는게 "문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다." 입니다

일반적인 방법으로 문제에 접근하면 "어 그냥 반복해서 문자열을 지워주다가 지울게 없으면 출력하면 되겠네" 겠죠.

이때, 최악의 경우 O(n^2)입니다. (n X n/2) 

시간제한범위를 한참 넘습니다. (1억번의 연산당 1초정도입니다.)

1000000 X 1000000/2 = 500000000000 > 200000000

따라서, 다른방법을 생각해보아야 합니다. 

스택을 사용해야합니다. 

1. 모든 문자열을 스택에 넣는다. 

2. 넣으면서 폭발문자열의 끝 문자와 같다면 스택을 검사합니다.

3. 폭발문자열이 있는지 확인하고, 있다면 해당문자열을 지워줍니다. 

위 의 방식으로 O(n) 번만에 값을 찾을 수 있습니다.  

두번째로 고려하셔야 할게 있습니다. 

저는 string의 erase함수를 사용하며 데이터를 지우면서 결과값을 도출했는데, 45%에서 시간초과가 났습니다. 

1. C의 strlen
2. C++의 string.erase
3. Java의 String.replaceAll
4. Python의 str.replace, str.find, list.pop(i) etc

굳이 내장함수가 아니더라도 단순히 문자열의 중간을 한 번 지울 때마다 거의 무조건 O(N)이 걸립니다. 즉 지우는 행위를 하면 안됩니다. 

곰곰히 생각해보니까 해당 스택자체가 결과값이더군요... ( 연결되는 모든 폭발 문자열을 지운 문자열 그자체..)

이거를 늦게 알아서, 고생한 문제 였습니다. 

#include <iostream>
#include <string>
using namespace std;

string basic,bomb;
char result[1000001];
int  result_cur = 0;
int main() {
	char lastword;
	cin >> basic;
	cin >> bomb;
	lastword = bomb[bomb.size() - 1];

	for (int i = 0; i < basic.size(); i++) {
		result[result_cur++] = basic[i];
	

		if (basic[i] == lastword) //마지막 문자열과 다르면 스택에 담습니다.
		 { 
			
				bool jud = true;
				for (int j = bomb.size() - 1; j >= 0; j--)
				{
					if (bomb[j] != result[result_cur - 1 - (bomb.size() - 1) + j]) { // 스택의 가장위쪽부터 한칸씩 내려오면서 검사
						jud = false; //즉 해당문자열이 아니면 false
						break;
					}
				}
				if (jud == false) {
					continue;
				}
				else { 
								
					for (int j = 0; j < bomb.size(); j++) {
						result_cur--;				
					}
				}	
		}
	}
	if (result_cur==0)
		cout << "FRULA" << '\n';
	else {
		
		for (int i = 0; i < result_cur; i++) {
			cout << result[i];
		}
		cout << '\n';
	}
}

result 는 스택, 결과값 입니다. 

for (int j = bomb.size() - 1; j >= 0; j--)
				{
					if (bomb[j] != result[result_cur - 1 - (bomb.size() - 1) + j]) { // 스택의 가장위쪽부터 한칸씩 내려오면서 검사
						jud = false; //즉 해당문자열이 아니면 false
						break;
					}
				}

3. 폭발문자열이 있는지 확인하고,

for (int j = 0; j < bomb.size(); j++) {
						result_cur--;				
					}

있다면 해당문자열을 지워줍니다. (스택에서 단순히 커서를 내려줌으로써 지울 수 있겠죠.)

화이팅:)

너무 쉬워서 설명은 생략입니다

#include <iostream>
#include <string>
using namespace std;
string arr;

int main() {
	cin >> arr;
	for (int i = 0; i < arr.size(); i++)
	{
		if (arr[i] == 'C' || arr[i] == 'A' || arr[i] == 'M' || arr[i] == 'B' || arr[i] == 'R' || arr[i] == 'I' || arr[i] == 'D' || arr[i] == 'G' || arr[i] == 'E'){
			arr.erase(i, 1);
		i--;
		}
	}
	if (arr.size() == 0)
		cout << ' ' << endl;
	else
		cout << arr << endl;
}

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이룰 수 있다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이룰 수 있다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

해당규칙들을 만족시켜야한다. 

즉, '(' 과 ')' 의 개수가 일치하여야 하고 '(' 가 이전에 있어야한다. (대괄호도 마찬가지)

((())) -> yes이고 (())) , ((()) -> no 이다. 

짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다. 

해당규칙에 따라 ([] [] )(()) ->yes  이고 (([(])) -> no가 된다.

#include <iostream>
#include <string>
using namespace std;

string arr;

int main() {

	while (1) {
		int	stacked[100] = { 0 };
		bool jud = true;
		int small_bracket = 0, big_bracket = 0, stack_index = 0;
		
		getline(cin, arr);
		if (arr[0] == '.'&& arr.size()==1)
			break;

		for (int i = 0; i < arr.size(); i++) {
		
			if (arr[i] == '(') {
				small_bracket++;
				stacked[stack_index++] = 1; // 1이 small 2가 big
			}
			else if (arr[i] == '[') {
				big_bracket++;
				stacked[stack_index++] = 2; // 1이 small 2가 big
			}
			else if (arr[i] == ')') {
				if (small_bracket < 0) {
					jud = false;
					break;
				}
				if (stacked[stack_index-1] != 1) {
					jud = false;
					break;
				}
				else 
					stacked[--stack_index] = 0,small_bracket--;

			}

			else if (arr[i] == ']') {
				if (big_bracket < 0) {
					jud = false;
					break;
				}
				if (stacked[stack_index - 1] != 2) {
					jud = false;
					break;
				}
				else
					stacked[--stack_index] = 0, big_bracket--;

			}

		}

		if (small_bracket != 0 || big_bracket != 0)
			jud = false;

		if (jud == false)
			cout << "no" << endl;
		else
			cout << "yes" << endl;

	}
}

전형적인 낚시문제.. 

앞, 뒤에 공백이 있을 수 있다는 사실을 모른채 뉴비들의 정답률을 뺏어간 25퍼짜리 문제입니다..

쉽습니다.  앞뒤 공백을 제외한 공백의 갯수 + 1이 단어의 개수가 됩니다.

(공백이 연속해서 나오는 경우는 없다. ) 라는 조건 때문입니다. 이것을 고려해서 코드를 짜면 

#include <iostream>
#include <string>
using namespace std;

string arr;
int cnt = 0;
int main() {
	getline(cin,arr);

	for (int i = 0; i < arr.size(); i++)
		if (arr[i] == ' ')
			cnt++;
	if (arr[0] == ' ')
		cnt--;
	if (arr[arr.size() - 1] == ' ')
		cnt--;
	cnt++;
	cout << cnt << endl;

}

이렇게 간단한 코드가 나옵니다.

c언어의 strtok이라는 함수를 이용해서 단어를 구분하는 방법도 있습니다. 

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

int main() {
	int count = 0,k=0;
	char arr[1000001];
	gets(arr);
	char *a;
	a = strtok(arr, " ");
	while (a != NULL) {
		count++;
		a = strtok(NULL, " ");
	}
	printf("%d\n", count);
	
}

꼭 직접 손으로 짜보시면서 연습하시길 바랍니다. 

정말 쉬운 문자열 처리문제입니다. 

푸는방법도 다양합니다.

저는 가장 긴 문자열 기준으로 값을 비교하면서 다른값이거나 문자열이 없다면, ? 

모두 같은 문자라면 해당문자를 추가하는식으로 결과값을 도출했습니다. 

#include <iostream>
#include <string>
using namespace std;

int n = 0;
string arr[50];
string result; 

int main() {
		
	int len = 0,len_index=-1;
	// input 
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (arr[i].size() > len) len = arr[i].size(), len_index = i;
	}

	for (int i = 0; i < len; i++) {
		char word = arr[len_index][i];
		bool jud = false;
		for (int j = 0; j < n; j++) {
			if (i > arr[j].size() - 1) {
				result += '?';
				jud = true;
				break;
			}
			else if(word != arr[j][i]) {
				result += '?';
				jud = true;
				break;
			}
				
		}
		if (jud == false)
			result += word;

	}
	
	cout << result << endl;
}