congcoding

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 

1. 문제 링크

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

2. 문제 설명

N명의 사람이 원형으로 앉아있을 때 순서대로 K번째 사람을 제거하는 순서를 출력하는 문제입니다.

3. 소스코드

BOJ 1158번 요세푸스 문제 C++ 풀이입니다.

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

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

	int N, K, idx;
	cin >> N >> K;
	vector<int> v(N);
	idx = K - 1;

	for (int i = 0; i < N; i++) v[i] = i + 1;
	cout << '<';
	while (v.size() != 1) {
		cout << v[idx] << ", ";
		v.erase(v.begin() + idx);
		idx = (idx + K - 1) % v.size();
	}
	cout << v[0] << '>';

	return 0;
}

먼저 vector와 인덱스를 이용한 풀이입니다.

인덱스는 0부터 시작하므로 13번 라인에서 idx를 K - 1로 초기화했습니다.

마지막 요소를 출력할 때는 ", "를 출력하지 않으므로 while문의 조건을 v.size() != 1로 설정했습니다.

먼저 idx에 있는 요소를 출력한 후, erase합니다.

idx를 K - 1만큼 증가시켰을 때, v의 범위를 초과하는 경우가 있으므로 size로 나눴을 때의 나머지를 대입합니다.

마지막으로 남은 요소를 출력하고 '>'를 같이 출력합니다.

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

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

	int N, K, idx;
	cin >> N >> K;
	vector<int> v(N);
	vector<int>::iterator t = v.begin();
	for (int i = 0; i < N; i++) v[i] = i + 1;

	cout << '<';
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < K - 1; j++)
			if (++t == v.end()) t = v.begin();
		cout << *t << ", ";
		t = v.erase(t);
		if (t == v.end()) t = v.begin();
	}
	cout << v[0] << '>';

	return 0;
}

vector와 iterator를 이용한 풀이입니다.

마지막 요소를 출력할 때는 ", "를 출력하지 않으므로 바깥쪽 for문을 N - 1전까지만 돌게 설정했습니다.

vector와 index를 이용한 풀이처럼 while문의 조건을 v.size != 1로 설정해도 됩니다.

안쪽 for문은 K - 1번 돌면서 t를 한칸씩 이동시켜줍니다.

이 때 t가 end에 도달하면 v.begin()을 대입해줍니다. 원형이라고 생각하면 이해하기 쉽습니다.

현재 t위치의 요소를 출력한 후, 삭제(v.erase(t))를 해줍니다.

erase함수는 삭제한 요소의 다음 요소를 return하므로 이를 다시 t에 대입했습니다.

이 때 t가 end에 도달했을 경우 v.begin()을 대입해줍니다.

이 과정을 생략하면 안쪽 for문을 돌 때 ++t하는 과정에서 segmentation fault가 발생하므로 주의해야 합니다.

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

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

	int N, K, idx;
	cin >> N >> K;
	list<int> l;

	for (int i = 0; i < N; i++) l.push_back(i + 1);
	cout << '<';
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < K - 1; j++) {
			l.push_back(l.front());
			l.pop_front();
		}
		cout << l.front() << ", ";
		l.pop_front();
	}
	cout << l.front() << '>';

	return 0;
}

list 이용한 풀이입니다.

마지막 요소를 출력할 때는 ", "를 출력하지 않으므로 바깥쪽 for문을 N - 1전까지만 돌게 설정했습니다.

vector와 인덱스를 이용한 풀이처럼 while문의 조건을 l.size != 1로 설정해도 됩니다.

안쪽 for문은 K - 1번씩 돌면서 list의 맨 앞에 있는 요소를 맨 뒤로 옮겨줬습니다.

이를 구현하려면 맨 앞에 있는 요소(l.front())를 맨 뒤에 넣고(l.push_back), 맨 앞의 요소를 삭제(l.pop_front())하면 됩니다.

뒤로 다 옮긴 후 맨 앞에 있는 요소(l.front())를 출력한 후, 맨 앞의 요소를 삭제(l.pop_front())하면 됩니다.

1. 문제 링크

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

2. 문제 설명

숫자를 입력받은 후 이를 표현하기 위해 0부터 9까지 숫자가 하나씩 들어있는 세트의 최소 필요 개수를 출력하는 문제입니다.

3. 소스코드

BOJ 1475번 방 번호 C++ 풀이입니다.

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

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

	int N;
	vector<int> v(9);
	cin >> N;

	if (N == 0) v[0]++;
	while (N > 0) {
		if (N % 10 == 9) v[6]++;
		else v[N % 10]++;
		N /= 10;
	}
	v[6] = ceil((double)v[6] / 2);
	cout << *max_element(v.begin(), v.end());

	return 0;
}

6은 9를 뒤집어서 이용할 수 있기 때문에 9를 입력받으면 6의 자리에 +1을 해줬습니다.

한 세트에 6과 9가 들어있으므로 v[6]은 /2를 해준 후 ceil함수를 이용해 올림했습니다.

마지막으로 max_element함수를 이용해 최댓값을 출력해주면 됩니다.

1. 문제 링크

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

2. 문제 설명

수학여행에 참가하는 학생의 정보를 입력받아, 학년과 성별로 방을 배정할 때 필요한 최소한의 방의 수를 출력하는 문제입니다.

3. 소스코드

BOJ 13300번 방 배정 C++ 풀이입니다.

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

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

	int N, K, r, c, result = 0;
	int arr[2][6] = {};
	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		cin >> r >> c;
		arr[r][c - 1]++;
	}
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 6; j++) {
			result += ceil((double)arr[i][j] / K);
		}
	}
	cout << result;

	return 0;
}

학생의 정보를 성별과 학년으로 저장하기 위해 11번 라인에서 arr[2][6]을 선언하고 0으로 초기했습니다.

학생의 성별은 0, 1이지만 학년이 1부터 6까지 이므로 arr에 학년 정보를 저장할 때는 -1을 해줬습니다.

arr의 각 요소들을 방에 배정할 수 있는 최대 인원 수로 나누고 ceil함수를 이용해서 올림해줬습니다.

이때 arr[i][j]나 K를 double로 형변환해주지 않으면 int끼리 연산돼서 이미 내림된 결과에

ceil함수를 적용하는 것이기 때문에 올림이 되지 않으니 주의해야 합니다.

1. 문제 링크

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

2. 문제 설명

string을 2개씩 입력받은 후 서로 재배열할 수 있는지 여부를 출력하는 문제입니다.

3. 소스코드

BOJ 11328번 Strfry C++ 풀이입니다.

#include <iostream>
using namespace std;

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

	int N;
	int arr[26];
	bool is_possible;
	string s1, s2;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> s1 >> s2;
		is_possible = true;
		fill(arr, arr + 26, 0);
		for (int j = 0; j < s1.length(); j++) {
			arr[s1[j] - 'a']++;
			arr[s2[j] - 'a']--;
		}
		for (int j = 0; j < 26; j++) {
			if (arr[j] != 0) {
				is_possible = false;
				break;
			}
		}
		if (is_possible) cout << "Possible\n";
		else cout << "Impossible\n";
	}

	return 0;
}

알파벳의 개수를 세기 위하여 10번 라인에서 arr[26]을 선언했습니다.

for문을 돌 때 마다 arr을 0으로 초기화하기 위해 18번 라인에서 fill함수를 사용했습니다.

문자열의 길이만큼 for문을 돌면서 s1에 있는 알파벳들의 인덱스에는 +1을 해주고

s2에 있는 알파벳들의 인덱스에는 -1을 해줬습니다.

결과적으로 arr의 요소가 0이 아니면 재배열해서 만들 수 없는 문자열이므로 이를 is_possible 변수를 이용해서 판단했습니다.