congcoding

1. 문제 링크

www.acmicpc.net/problem/2309

2. 문제 설명

아홉 난쟁이의 키를 입력받아 키의 합이 100이 되는 일곱 난쟁이를 찾아 오름차순으로 출력하는 문제입니다.

3. 소스코드

BOJ 2309번 일곱 난쟁이 C++ 풀이입니다.

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

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

	int arr[9];
	int sum = 0;
	for (int i = 0; i < 9; i++) {
		cin >> arr[i];
		sum += arr[i];
	}

	sort(arr, arr + 9);
	for (int i = 0; i < 8; i++) {
		for (int j = i + 1; j < 9; j++) {
			if (sum - arr[i] - arr[j] == 100) {
				for (int k = 0; k < 9; k++) {
					if (k != i && k != j)
						cout << arr[k] << '\n';
				}
				return 0;
			}
		}
	}

	return 0;
}

13, 14번 라인 : 아홉 난쟁이의 키를 입력받으면서 동시에 키의 합을 구합니다.

17번 라인 : 오름차순으로 출력하기 위해 정렬합니다.

18, 19번 라인 : i, j에 0~8까지 수에서 2개를 뽑는 조합을 모두 대입합니다. (0,1 ~ 7,8)

20번 라인 : 아홉 난쟁이의 키의 합에서 i번째 난쟁이와 j번째 난쟁이의 키를 빼서 100이 되는지 확인합니다.

21 ~ 24번 라인 : 20번 라인에서 100이 된다면 정답이므로 i번째 난쟁이와 j번째 난쟁이를 제외한 난쟁이의 키를 출력합니다.

25번 라인 : 정답이 여러 개인 경우 하나만 출력해야 하므로 프로그램을 종료합니다. (break를 사용할 경우 19번 for문만 탈출합니다.)

1. 문제 링크

www.acmicpc.net/problem/10814

2. 문제 설명

나이와 이름을 입력받은 후, 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하여 출력하는 문제입니다.

3. 소스코드

BOJ 10814번 나이순 정렬 C++ 풀이입니다.

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

pair<int, string> p[100000];

bool comp(pair<int, string> p1, pair<int, string> p2)
{
	return p1.first < p2.first;
}

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

	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> p[i].first >> p[i].second;

	stable_sort(p, p + N, comp);
	for (int i = 0; i < N; i++)
		cout << p[i].first << ' ' << p[i].second << '\n';

	return 0;
}

나이가 같으면 가입한 순서대로 정렬되어야 하므로 stable_sort함수를 이용하여 풀었습니다.

sort함수를 사용하면 나이가 같을 때, 가입한 순서와 다르게 정렬되는 경우가 있으므로 틀립니다.

pair의 경우 first(나이), second(이름) 순서로 정렬되는데,

이 문제에서 second(이름)는 정렬되면 안 되기 때문에 직접 comp함수를 만들어서 first만 비교하도록 구현했습니다.

1. 문제 링크

www.acmicpc.net/problem/2751

2. 문제 설명

N개의 수를 입력받은 후, 오름차순으로 정렬하여 출력하는 문제입니다.

3. 소스코드

BOJ 2751번 수 정렬하기 2 C++ 풀이입니다.

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

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

	int N;
	int arr[1000000];
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	sort(arr, arr + N);
	for (int i = 0; i < N; i++)
		cout << arr[i] << '\n';

	return 0;
}

sort함수를 이용한 풀이입니다.

sort함수를 사용하기 위해서는 <algorithm> 헤더 파일을 include 해줘야 합니다.

sort함수의 사용법은 sort(시작 지점, 끝 지점) 입니다.

시작 지점을 포함하고, 끝 지점을 포함하지 않는 범위까지 오름차순으로 정렬을 해줍니다.

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

void quick_sort(int *arr, int start, int end)
{
	int pivot = arr[start];
	int left = start + 1;
	int right = end;

	if (start >= end)
		return;
	while (true) {
		while (left <= right && arr[left] <= pivot)
			left++;
		while (left <= right && arr[right] >= pivot)
			right--;
		if (left > right)
			break;
		swap(arr[left], arr[right]);
	}
	swap(arr[start], arr[right]);
	quick_sort(arr, start, right - 1);
	quick_sort(arr, right + 1, end);
}

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

	int N;
	int arr[1000000];
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	random_shuffle(arr, arr + N);
	quick_sort(arr, 0, N - 1);
	for (int i = 0; i < N; i++)
		cout << arr[i] << '\n';

	return 0;
}

퀵 정렬을 이용한 풀이입니다.

퀵 정렬의 시간 복잡도는 평균적으로 O(nlogn)이지만, 최악의 경우 O(n^2)입니다.

이 문제의 경우 O(nlogn)으로만 풀 수 있기 때문에 38번 라인을 주석 처리하면 시간 초과가 납니다.

퀵 정렬의 최악의 경우는 순서대로 정렬되어있거나, 거꾸로 정렬되어 있는 경우이므로

38번 라인에서 random_shuffle(arr, arr + N); 을 사용하여 랜덤으로 섞어서 이러한 경우를 방지했습니다.

STL의 sort함수의 경우 퀵 정렬, 힙 정렬, 삽입 정렬을 혼합해서 사용하는 인트로 정렬로 구현되어 있어 최악의 경우에도 O(nlogn) 입니다.

1. 문제 링크

www.acmicpc.net/problem/2750

2. 문제 설명

N개의 수를 입력받은 후, 오름차순으로 정렬하여 출력하는 문제입니다.

3. 소스코드

BOJ 2750번 수 정렬하기 C++ 풀이입니다.

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

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

	int N;
	int arr[1000];
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	sort(arr, arr + N);
	for (int i = 0; i < N; i++)
		cout << arr[i] << '\n';

	return 0;
}

sort함수를 이용한 풀이입니다.

sort함수를 사용하기 위해서는 <algorithm> 헤더 파일을 include 해줘야 합니다.

sort함수의 사용법은 sort(시작 지점, 끝 지점) 입니다.

시작 지점을 포함하고, 끝 지점을 포함하지 않는 범위까지 오름차순으로 정렬을 해줍니다.

#include <iostream>
using namespace std;

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

	int N;
	int arr[1000];
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	for (int i = 1; i < N; i++) {
		int temp = arr[i];
		int j;
		for (j = i - 1; j >= 0; j--) {
			if (arr[j] > temp)
				arr[j + 1] = arr[j];
			else
				break;
		}
		arr[j + 1] = temp;
	}
	for (int i = 0; i < N; i++)
		cout << arr[i] << '\n';

	return 0;
}

삽입 정렬을 이용한 풀이입니다.

1. 문제 링크

https://www.acmicpc.net/problem/1874

2. 문제 설명

스택 수열을 입력받은 후 push와 pop으로 해당 수열을 만들 수 있는 경우 push는 +, pop은 -로 표현하고,

불가능한 경우 NO를 출력하는 문제입니다.

3. 소스코드

BOJ 1874번 스택 수열 C++ 풀이입니다.

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

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

	int n, num, cnt = 1;
	stack<int> s;
	string result = "";
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> num;
		if (num >= cnt) {
			while (num + 1 != cnt) {
				s.push(cnt++);
				result += "+\n";
			}
			s.pop();
			result += "-\n";
		}
		else {
			if (s.top() == num) {
				s.pop();
				result += "-\n";
			}
			else {
				result = "NO";
				break;
			}
		}
	}
	cout << result;

	return 0;
}

먼저 스택에 넣을 수 cnt를 1로 초기화합니다.

17번 라인 if문을 통해 입력받은 수 num이 cnt와 같거나 크면

cnt가 num과 같아질 때 까지 스택에 cnt를 push하고 result에 +를 이어 붙입니다.

그리고 해당 수를 출력하기 위해 pop을 하고 result에 -를 이어 붙입니다.

예를 들어 처음에 4를 입력받으면 스택에 1, 2, 3, 4를 push하므로 +를 4번 출력하고, 4를 pop하고 -를 1번 출력합니다.

25번 라인 else문을 통해 입력받은 수 num이 cnt보다 작으면

스택의 top이 num과 같은지 확인하고, 같으면 해당 수를 출력하기 위해 pop을 하고 result에 -를 이어 붙입니다.

스택의 top이 num과 같지 않으면 주어진 스택 수열을 만들 수 없으므로 result에 NO를 저장하고 for문을 탈출합니다.

최종적으로 result를 출력하면 됩니다. 

1. 문제 링크

https://www.acmicpc.net/problem/10866

2. 문제 설명

덱을 구현하는 문제입니다.

3. 소스코드

BOJ 10866번 덱 C++ 풀이입니다.

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

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

	int N, X;
	deque<int> D;
	string op;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> op;
		if (op == "push_front") {
			cin >> X;
			D.push_front(X);
		}
		else if (op == "push_back") {
			cin >> X;
			D.push_back(X);
		}
		else if (op == "pop_front") {
			if (D.empty()) cout << -1 << '\n';
			else {
				cout << D.front() << '\n';
				D.pop_front();
			}
		}
		else if (op == "pop_back") {
			if (D.empty()) cout << -1 << '\n';
			else {
				cout << D.back() << '\n';
				D.pop_back();
			}
		}
		else if (op == "size") {
			cout << D.size() << '\n';
		}
		else if (op == "empty") {
			cout << D.empty() << '\n';
		}
		else if (op == "front") {
			if (D.empty()) cout << -1 << '\n';
			else cout << D.front() << '\n';
		}
		else if (op == "back") {
			if (D.empty()) cout << -1 << '\n';
			else cout << D.back() << '\n';
		}
	}

	return 0;
}

STL에 있는 deque을 이용해서 풀었습니다.

pop_front, pop_back, front, back함수를 호출할 때 덱이 비어있으면 에러가 발생하므로,

empty함수로 덱이 비어있는지 먼저 확인한 후 사용해야 합니다.

1. 문제 링크

https://www.acmicpc.net/problem/10845

2. 문제 설명

큐를 구현하는 문제입니다.

3. 소스코드

BOJ 10845번 큐 C++ 풀이입니다.

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

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

	int N, X;
	queue<int> Q;
	string op;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> op;
		if (op == "push") {
			cin >> X;
			Q.push(X);
		}
		else if (op == "pop") {
			if (Q.empty()) cout << -1 << '\n';
			else {
				cout << Q.front() << '\n';
				Q.pop();
			}
		}
		else if (op == "size") {
			cout << Q.size() << '\n';
		}
		else if (op == "empty") {
			cout << Q.empty() << '\n';
		}
		else if (op == "front") {
			if (Q.empty()) cout << -1 << '\n';
			else cout << Q.front() << '\n';
		}
		else if (op == "back") {
			if (Q.empty()) cout << -1 << '\n';
			else cout << Q.back() << '\n';
		}
	}

	return 0;
}

STL에 있는 queue를 이용해서 풀었습니다.

pop, front, back함수를 호출할 때 큐가 비어있으면 에러가 발생하므로,

empty함수로 큐가 비어있는지 먼저 확인한 후 사용해야 합니다.

1. 문제 링크

https://www.acmicpc.net/problem/10828

2. 문제 설명

스택을 구현하는 문제입니다.

3. 소스코드

BOJ 10828번 스택 C++ 풀이입니다.

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

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

	int N, X;
	stack<int> S;
	string op;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> op;
		if (op == "push") {
			cin >> X;
			S.push(X);
		}
		else if (op == "pop") {
			if (S.empty()) cout << -1 << '\n';
			else {
				cout << S.top() << '\n';
				S.pop();
			}
		}
		else if (op == "size") {
			cout << S.size() << '\n';
		}
		else if (op == "empty") {
			cout << S.empty() << '\n';
		}
		else if (op == "top") {
			if (S.empty()) cout << -1 << '\n';
			else cout << S.top() << '\n';
		}
	}

	return 0;
}

STL에 있는 stack을 이용해서 풀었습니다.

pop, top함수를 호출할 때 스택이 비어있으면 에러가 발생하므로,

empty함수로 스택이 비어있는지 먼저 확인한 후 사용해야 합니다.

1. 문제 링크

https://www.acmicpc.net/problem/1919

2. 문제 설명

두 단어를 입력받은 후 서로 애너그램 관계에 있도록 만들기 위해서 제거해야하는 최소 개수의 문자 수를 출력하는 문제입니다.

3. 소스코드

BOJ 1919번 애너그램 만들기 C++ 풀이입니다.

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

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

	string s1, s2;
	int result = 0;
	int arr[26] = {};
	cin >> s1 >> s2;

	for (int i = 0; i < s1.length(); i++) arr[s1[i] - 'a']++;
	for (int i = 0; i < s2.length(); i++) arr[s2[i] - 'a']--;
	for (int i = 0; i < 26; i++) result += abs(arr[i]);
	cout << result;

	return 0;
}

s1에 있는 알파벳들은 arr배열의 해당 인덱스에 +1 해주고,

s2에 있는 알파벳들은 arr배열의 해당 인덱스에 -1 해줍니다.

arr배열의 요소가 0이 아닌 경우에는 삭제해야 애너그램을 만들 수 있으므로 절댓값만큼 result에 더해주면 됩니다.

1. 문제 링크

https://www.acmicpc.net/problem/5397

2. 문제 설명

키보드를 누른 명령어를 입력받은 후 규칙에 따라 비밀번호를 출력하는 문제입니다.

3. 소스코드

BOJ 5397번 키로거 C++ 풀이입니다.

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

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

	int T;
	list<char> l;
	list<char>::iterator t;
	string L;
	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> L;
		l.clear();
		t = l.begin();
		for (int j = 0; j < L.length(); j++) {
			if (L[j] == '<' && t != l.begin()) t--;
			else if (L[j] == '>' && t != l.end()) t++;
			else if (L[j] == '-' && t != l.begin()) t = l.erase(--t);
			else if (L[j] != '<' && L[j] != '>' && L[j] != '-') l.insert(t, L[j]);
		}
		for (t = l.begin(); t != l.end(); t++) cout << *t;
		cout << '\n';
	}

	return 0;
}

string L을 for문으로 돌면서 list l에 insert하거나 erase하는 방식으로 풀었습니다.

우선, 각 케이스마다 list를 초기화해줘야 하므로 18번 라인에서 clear함수로 초기화했습니다.

iterator t는 l.begin()으로 초기화해줬지만, 현재 list가 비어있어 l.begin() == l.end()이므로 아무거나 사용해도 됩니다.

L의 길이만큼 안쪽 for문을 돌면서 각각의 케이스에 맞게 l의 iterator인 t를 움직이거나, erase하거나, insert해주면 됩니다.

이 과정이 잘 이해가 되지 않는다면 비슷한 문제인 1406번 에디터 문제를 풀어보시면 좋을 것 같습니다.

해당 문제의 제 풀이는 아래와 같습니다. https://congcoding.tistory.com/43