두 단어를 입력받은 후 서로 애너그램 관계에 있도록 만들기 위해서 제거해야하는 최소 개수의 문자 수를 출력하는 문제입니다.
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에 더해주면 됩니다.
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())하면 됩니다.
string을 입력받은 후 명령어에 따라 기능을 수행한 후 남아있는 string을 출력하는 문제입니다.
3. 소스코드
BOJ 1406번 에디터 C++ 풀이입니다.
#include <iostream>
#include <list>
using namespace std;
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
string s;
char op;
int M;
cin >> s >> M;
list<char> l(s.begin(), s.end());
list<char>::iterator t = l.end();
// auto t = l.end();
for (int i = 0; i < M; i++) {
cin >> op;
if (op == 'L' && t != l.begin()) t--;
else if (op == 'D' && t != l.end()) t++;
else if (op == 'B' && t != l.begin()) t = l.erase(--t);
else if (op == 'P') {
cin >> op;
l.insert(t, op);
}
}
for (t = l.begin(); t != l.end(); t++) cout << *t;
// for (auto c : l) cout << c;
return 0;
}
연결 리스트를 사용하면 쉽게 풀 수 있는 문제이므로 14번 라인에서 입력받은 문자열을 list<char>에 대입했습니다.
문제에서 커서는 문장의 맨 뒤에 위치하고 있다고 했기 때문에 15번 라인에서 iterator t를 l.end()로 초기화했습니다.
16번 라인처럼 auto를 사용해도 됩니다.
명령어가 L이고 커서가 문장의 맨 앞(l.begin())이 아니면 커서를 한칸 앞으로 이동합니다. (t--)
명령어가 D이고 커서가 문장의 맨 뒤(l.end())가 아니면 커서를 한칸 뒤로 이동합니다. (t++)
명령어가 B이고 커서가 문장의 맨 앞(l.begin())이 아니면 커서 왼쪽에 있는 문자(--t)를 삭제합니다.
list의 erase함수를 사용할 때 return값은 지운 요소의 다음 요소를 반환하므로 이를 다시 t에 대입해줍니다.
return값을 활용하지 않으려면 t--; l.erase(t++);과 같이 사용하면 됩니다.
명령어가 P이면 커서 왼쪽에 문자를 추가하므로 t위치에 insert하면 됩니다.
list의 insert함수는 iterator가 가리키는 곳의 왼쪽에 삽입하고, iterator는 원래 요소를 그대로 가리킵니다.