굳건하게

문제 : https://www.acmicpc.net/problem/4949

기존풀이 : https://travelbeeee.tistory.com/73

[알고리즘풀이]

기존에는 괄호 종류에 따라 stack을 2개 선언해주고 ( [ ) ] 같이 잘못 짝꿍이 맞는 경우에 대해서

Index를 이용해서 검사를 해줬습니다.

하지만, stack을 하나만 선언하고 괄호 2가지 종류를 같은 stack에 Push 하면서 짝궁이 맞지 않는 경우나 짝궁이 없는 경우를 한 번에 검사할 수 있습니다. 따라서 If문으로 나누어 검사해야 되는 경우가 줄어들어 훨씬 편리합니다.

-Stack을 2개 이용한 기존 코드

#include<iostream>
#include<stack>
#include<string>

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
	while(1){
		bool flag = false;
		string input;
		getline(cin, input);
		if (input == ".")
			return 0;
		stack<int> s1, s2;
		for (int i = 0; i < input.length(); i++) {
			if (input[i] == '(') {
				s1.push(i);
			}
			else if (input[i] == '[') {
				s2.push(i);
			}
			else if (input[i] == ')') {
				if (s1.empty()) {
					flag = true;
					break;
				}
				if (s2.empty()) {
					s1.pop();
					continue;
				}
				int c1 = s1.top();
				int c2 = s2.top();
				if (c1 < c2) {
					flag = true;
					break;
				}
				s1.pop();
			}
			else if (input[i] == ']') {
				if (s2.empty()) {
					flag = true;
					break;
				}
				if (s1.empty()) {
					s2.pop();
					continue;
				}
				int c1 = s1.top();
				int c2 = s2.top();
				if (c1 > c2) {
					flag = true;
					break;
				}
				s2.pop();
			}
		}
		 if (flag || !s1.empty() || !s2.empty())
			cout << "no\n";
		else
			cout << "yes\n";
	}
}

-Stack 하나만을 이용한 개선된 코드

#include<iostream>
#include<string>
#include<stack>

using namespace std;

int main(void) {
	while (1) {
		bool flag = false;
		string input;
		getline(cin, input);
		if (input == ".")
			return 0;
		stack<char> c;
		for (int i = 0; i < input.size(); i++) {
			if (input[i] == '(' || input[i] == '[')
				c.push(input[i]);
			else if (input[i] == ')') {
				if (c.empty() || c.top() != '(') { // 짝꿍이 없거나 잘못된 짝꿍
					flag = true;
					break;
				}
				else
					c.pop();
			}
			else if (input[i] == ']') {
				if (c.empty() || c.top() != '[') { // 짝꿍이 없거나 잘못된 짝꿍
					flag = true;
					break;
				}
				else
					c.pop();
			}
		}
		if (flag || !c.empty()) {
			cout << "no\n";
		}
		else
			cout << "yes\n";
	}
}

문제 : https://www.acmicpc.net/problem/11650

[알고리즘풀이]

1) Algorithm Library Sort함수 이용

좌표를 다 입력받고, 기준에 맞춰서 sort하면 됩니다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<pair<int, int>> v;
bool compare(pair<int, int>, pair<int, int>);

int main(void) {
	int n;
    cin >> n;
	for (int i = 0; i < n; i++){
        int x, y;
        cin >> x >> y;
        v.push_back(make_pair(x,y));
    }
	sort(v.begin(), v.end());
	for (int i = 0; i < n; i++)
        cout << v[i].first << ' ' << v[i].second << '\n';
}

bool compare(pair<int, int> input1, pair<int, int> input2) {
	if (input1.first < input2.first)
		return true;
	else if (input1.first > input2.first)
		return false;
	else {
		if (input1.second < input2.second)
			return true;
		else
			return false;
	}
}

2) Queue Library Priority Queue 이용

우선순위큐를 문제에 맞춰 우선순위를 할당하고, 우선순위큐에 좌표를 다 넣는다.

#include<iostream>
#include<queue>

using namespace std;

struct cmp {
	bool operator()(pair<int, int>n1, pair<int,int> n2) {
		if (n1.first > n2.first)
			return true;
		else if (n1.first == n2.first)
			if (n1.second > n2.second)
				return true;
			else
				return false;
		return false;
	}
};

int main(void) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		pq.push(make_pair(x, y));
	}
	while (!pq.empty()) {
		cout << pq.top().first << ' ' << pq.top().second << '\n';
		pq.pop();
	}
}

안녕하세요, 여행벌입니다.

오늘은 우선순위큐(Priority Queue)에 대해서 알아보도록 하겠습니다.

1. Priority_Queue(우선순위큐) 란?

Priority_Queue는 Queue의 한 종류로 이름 그대로 우선순위에 따라 정렬된 Queue입니다.

[Queue 포스팅 : https://travelbeeee.tistory.com/7?category=807507 ]

어떤 원소가 Push(삽입)된다면 주어진 우선순위에 맞춰서 Queue가 정렬되고, Pop(삭제)는 정렬된 Queue의 앞에서 이루어집니다. 자료구조 Heap으로 구현되었기 때문에, 특정 원소를 Push해 생기는 정렬 과정은 O(logN) 만에 이루어집니다.

2. C++ STL 우선순위큐 라이브러리 기본 명령어

#include<queue>

queue와 동일한 Library에서 지원해줍니다.

선언
- priority_queue<자료형, Container, 비교함수> 변수명
선언한 자료형 변수들을 비교함수에 따라 정렬하는 Priority_Queue(우선순위큐)를 선언.

- priority_queue<자료형> 변수명
선언한 자료형 변수들을 내림차순에 따라 정렬하는 Priority_Queue(우선순위큐)를 선언.

ex) priority_queue<int, vector<int>, cmp> pq 
int형 변수들을 cmp 우선순위에 따라 정렬하는 pq라는 이름의 Priority_queue(우선순위큐)를 선언.

추가 및 삭제
- push(element) : Priority_Queue(우선순위큐)에 원소를 삽입. ( 비교함수에 따라 내부적으로 정렬됨 )
- pop() : 맨 앞에 있는 원소를 삭제.

서칭
- top() : 맨 앞에 있는 원소를 반환.

기타
- empty() : Priority_Queue(우선순위큐)가 비어있으면 true 아니면 false를 반환
- size() : Priority_Queue(우선순위큐)의 크기를 반환

기본 함수는 다음과 같습니다.

이제, 예시를 통해서 익혀보겠습니다.

[예시1) 기본 - 내림차순]

#include<iostream>
#include<queue>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	priority_queue<int> pq;
	pq.push(5);
	pq.push(1);
	pq.push(7);
	for (int i = 0; i < 3; i++){
		cout << pq.top() << ' ';
		pq.pop();
	}
}

출력
7 5 1

int형 원소들을 내림차순에 따라 정렬하는 우선순위큐를 만들었습니다.

5 / 1 / 7 을 차례대로 입력하고 하나하나 출력해보니 7 / 5 / 1 순으로

비교기준(내림차순)에 따라 정렬되어있는 것을 확인할 수 있습니다.

#include<iostream>
#include<queue>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	priority_queue<char> pq;
	pq.push('5');
	pq.push('1');
	pq.push('7');
	for (int i = 0; i < 3; i++){
		cout << pq.top() << ' ';
		pq.pop();
	}
}

출력
7 5 1

이번에 char형 원소들을 내림차순에 따라 정렬하는 우선순위큐를 만들었습니다.

마찬가지로, 아스키코드값이 더 큰 '7', '5', '1' 순으로 정렬되어있는 것을 볼 수 있습니다.

[예시2) 기본 - 올림차순]

#include<iostream>
#include<queue>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	priority_queue<int, vector<int>, greater<int>> pq;
	pq.push(5);
	pq.push(1);
	pq.push(7);
	for (int i = 0; i < 3; i++){
		cout << pq.top() << ' ';
		pq.pop();
	}
}

출력
1 5 7

비교함수에 greater<int> 를 넣어주면 반대로 오름차순에 따라 정렬되는 우선순위큐를 만들 수 있습니다.

#include<iostream>
#include<queue>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	priority_queue<char, vector<char>, greater<char>> pq;
	pq.push('5');
	pq.push('1');
	pq.push('7');
	for (int i = 0; i < 3; i++){
		cout << pq.top() << ' ';
		pq.pop();
	}
}

출력
1 5 7

char형 변수에서도 greater<char>를 넣어주면 오름차순에 따라 정렬되는 우선순위큐를 만들 수 있습니다.

[예시3) 비교함수 선언1]

내림차순, 오름차순으로 정렬하는 우선순위큐는 쉽게 선언할 수 있습니다.

그렇다면, 내가 원하는 우선순위를 지정해주려면 어떻게 해야 될까요?

연산자 오버로딩을 통해 원하는 우선순위대로 구현할 수 있습니다.

아래 예시를 통해서 익혀보겠습니다.

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;

struct cmp {
	bool operator()(int n1, int n2) {
		if (abs(n1) > abs(n2))
			return true;
		else if (abs(n1) == abs(n2))
			if (n1 > n2)
				return true;
			else
				return false;
		return false;
	}
};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	priority_queue<int, vector<int>, cmp> pq;
	pq.push(1);
	pq.push(-1);
	pq.push(7);
	pq.push(-4);
	pq.push(15);

	for (int i = 0; i < 5; i++){
		cout << pq.top() << ' ';
		pq.pop();
	}
}

먼저 struct cmp 부분을 살펴보겠습니다.

struct cmp {
	bool operator()(int n1, int n2) {
		if (abs(n1) > abs(n2))
			return true;
		else if (abs(n1) == abs(n2))
			if (n1 > n2)
				return true;
			else
				return false;
		return false;
	}
};

위의 코드는 '절대값이 더 작은 값에 우선순위를 높게 주고, 절대값이 같다면 더 작은 값에 우선순위를 높게 줄 거예요!' 

라고 선언한 것과 같습니다.

따라서, 다음과 같이 출력됩니다.

출력
-1 1 -4 7 15

우선순위큐 포스팅은 여기서 마치겠습니다.

안녕하세요, 여행벌입니다.

오늘은 저번 포스팅에 이어서 String Library 함수들을 소개해보겠습니다.

[String Library 소개(1)]

https://travelbeeee.tistory.com/123

6. append() 함수

append() 함수는 하나의 문자열의 끝에 다른 문자열을 추가하는 함수입니다.

저번 포스팅에서 다뤘던 '+' 연산자랑 같은 기능을 하지만,

조금 더 다양한 기능을 할 수 있어서 상황에 따라 유용하게 사용할 수 있습니다.

-append() 함수

1. 문자열.append(추가할문자열);

// 추가할 문자열을 맨 끝에 추가함.

 

2.문자열.append(추가할문자열, 시작위치, 개수);

// 추가할 문자열의 시작 위치부터 개수만큼만 맨 끝에 추가함.

 

3.문자열.append(개수, 추가할문자);

//추가할 문자를 개수만큼 맨 끝에 추가함.

예제를 통해 3가지 유형을 다 익혀보도록 하겠습니다.

#include<iostream>
#include<string>

using namespace std;

int main(void) {
	string input1, input2, input3, input4;
	input1 = "abcde";
	input2.append(input1); //input2에 input1을 복사한다.
	cout << "input2는 : " << input2 << '\n';
	input3.append(input1, 3, 2);
	cout << "input3는 : " << input3 << '\n';
	input4.append(3, 'x');
	cout << "input4는 : " << input4 << '\n';
}

먼저 input1 에 "abcde"를 저장하고,

input2에 input2.append(input1)을 이용하여 input2의 끝에 input1을 추가해보겠습니다.

예상 결과는 input2 = "abcde" 입니다.

input3 에는 input1에 저장된 "abcde" 문자열의 3번 인덱스부터 2글자를 추가해보겠습니다.

예상 결과는 input3 = "de"입니다.

input4에는 문자 'x'를 3번 반복해서 추가해보도록 하겠습니다.

예상 결과는 input4 = "xxx" 입니다.

과연 예상대로 결과가 나올까요?

결과 :
input2는 : abcde
input3는 : de
input4는 : xxx

예상대로 잘 나오네요!

여기서 주의할 점은, 3번째 함수 원형은 문자열이 아닌 문자만 가능하다는 점입니다.

input4에 "abc"를 4번 추가하고 싶어도, input4.append(4,"abc") 라고 입력하면 오류가 발생합니다.

7. find() 함수

find 함수는 특정 문자열을 찾아, 그 시작 위치(int 형)을 반환하는 함수입니다.

-find() 함수 

1.문자열.find(찾을 문자열)

// 인덱스 0부터 찾을 문자열을 찾아, 그 시작 위치를 반환함.

 

2. 문자열.find(찾을 문자)

// 인덱스 0부터 찾을 문자를 찾아, 그 시작 위치를 반환함.

 

3. 문자열.find(찾을문자열, 시작위치)

// 시작 위치부터 찾을 문자열을 찾아, 그 시작 위치를 반환함.

예시를 통해서 익혀볼까요?

#include<iostream>
#include<string>

using namespace std;

int main(void) {
	string input1 = "abcdefghijklmnopqrstuvwxyz";
	cout << "문자열 efg 의 첫 시작 인덱스는 : " << input1.find("efg") << '\n';
	cout << "문자열 afg 의 첫 시작 인덱스는 : " << input1.find("afg") << '\n';
	cout << "문자 k 의 첫 시작 인덱스는 : " << input1.find('k') << '\n';
	cout << "문자 A 의 첫 시작 인덱스는 : " << input1.find('A') << '\n';
	cout << "문자열 efg 를 인덱스 10번 부터 찾았을 때 : " << input1.find("efg", 10) << '\n';
	cout << "문자열 afg 를 인덱스 3번 부터 찾았을 때 : " << input1.find("afg", 3) << '\n';
}

input1에서 "efg" 문자열을 찾고 싶습니다.

input1에 "efg" 문자열이 인덱스 4~6 에 있으므로, 4를 반환할 것 같습니다.

두 번 째로는, input1에서 "afg" 문자열을 찾고 싶습니다.

그런데 input1에 "afg" 문자열이 없으므로, 쓰레기 값이 반환되겠죠?

그다음으로는 input1에서 'k', 'A' 문자를 찾고 싶습니다.

'k' 는 인덱스 10 이므로 10을 반환하고, 'A' 는 input1에 없으므로, 쓰레기 값을 반환하겠죠?

마지막으로 "efg" 문자열을 10번 인덱스부터 찾고 싶습니다.

"efg" 문자열은 인덱스 4~6에 존재하므로, 쓰레기 값이 반환될 것 같습니다.

마찬가지로 "afg" 문자열은 존재하지 않으므로, 쓰레기 값이 반환될 것 같습니다.

문자열 efg 의 첫 시작 인덱스는 : 4
문자열 afg 의 첫 시작 인덱스는 : 4294967295
문자 k 의 첫 시작 인덱스는 : 10
문자 A 의 첫 시작 인덱스는 : 4294967295
문자열 efg 를 인덱스 10번 부터 찾았을 때 : 4294967295
문자열 afg 를 인덱스 3번 부터 찾았을 때 : 4294967295

8. compare() 함수

compare() 함수는 두 문자열을 비교하는 함수 입니다.

-compare() 함수 

문자열1.compare(문자열2)
// 문자열1과 문자열2를 비교해서 상황에 따라 다른 int형 값을 반환합니다.

만약 문자열1과 문자열2가 같다면, int형 0을 반환합니다.

문자열1과 문자열2가 다르다면, 달라지는 그 순간의 문자에 대해서

문자열1 이 문자열2 보다 사전 순으로 앞에 있을 경우 -1

뒤에 있을 경우 1을 반환합니다.

사전 순으로 계산하는 방법이 생각보다 복잡하므로,

같으면 0 다르면 0이 아닌 숫자가 나온다고 생각하고 사용해도 좋을 것 같습니다.

#include<iostream>
#include<string>

using namespace std;

int main(void) {
	string input1 = "abc", input2 = "ade", input3 = "a\c", input4 = "abc";
	std::cout << input1.compare(input2) << " " << input1.compare(input3) << '\n';
	std::cout << input1.compare(input4);
}

출력 결과 :
-1 -1
0

input2, input3를 input1이랑 다르므로 0이 아닌 값, input4는 같으므로 0이 출력되는 것을 볼 수 있습니다.

9. replace() 함수

replace() 함수는 특정 문자열을 찾아 그 문자열을 다른 문자열로 대체하는 함수입니다.

-replace() 함수

문자열.replace(대체할 문자열의 시작 위치, 대체할 문자열의 길이, 새로운 문자열)
//전달된 시작 위치부터 대체할 문자열의 길이만큼 삭제 후 새로운 문자열을 추가한다.

바로 예시를 통해 익혀볼까요?

#include<iostream>
#include<string>

using namespace std;

int main(void) {
	string input1 = "I am a good student.";
	std::cout << input1.replace(5, 4, "bad");
}

input1 = "I am good student." 에서 5번 째 인덱스 g 부터 4글자, 즉 good을 bad로 대체해보았습니다.

출력 결과 :
I am a bad student.

예상한 대로 잘 출력되는 것을 확인할 수 있습니다.

이처럼 C++은 C와는 달리 String Library를 통해서 Python만큼 문자열을 쉽게 다룰 수 있습니다.

잘 익혀두는 게 좋겠죠?

이상으로 String Library 소개를 마치겠습니다.