Q1. 2346 풍선 터뜨리기 > 문제 링크
덱을 이용해서, 터뜨릴 풍선을 가장 앞으로 오도록 회전을 시켜준 후에 앞을 pop하고, 이 과정을 덱이 빌 때까지 반복하는 형식으로 문제를 풀었다.
3만큼 뒤에 있는 풍선을 터뜨려야 하므로, 이 경우에는 4번 풍선이 가장 앞으로 와야 한다.
1번 풍선은 삭제가 되었고, 앞에 있는 두 풍선이 뒤로 이동하면 세 번째 풍선이 제일 앞에 올 수 있다. (터진 풍선까지 세서 그 풍선을 제외하고 두 번 이동하는 것이다)
4번 풍선이 삭제가 되고, 이 다음엔 4번 풍선보다 뒤에서 세번째에 있는 풍선이 삭제가 되어야 하는데, 이 경우 뒤에 있는 풍선을 세 번 앞으로 이동시키면 가장 앞에 있는 풍선이 터질 풍선이 된다.
#include <iostream>
#include <deque>
using namespace std;
int main() {
int n;
cin >> n;
deque<pair<int, int>> d;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
d.push_back(make_pair(i+1, num));
}
while (true) {
cout << d.front().first << " ";
int num = d.front().second;
d.pop_front();
if (d.empty()) break;
if (num > 0) {
for (int i = 0; i < num - 1; i++) { // 양수일 경우 이동숫자-1 만큼 뒤로 이동시킨다
d.push_back(d.front());
d.pop_front();
}
}
else {
for (int i = 0; i < abs(num); i++){ // 음수일 경우 역방향으로 절댓값만큼 앞으로 가져온다
d.push_front(d.back());
d.pop_back();
}
}
}
}Q2. 1543 문서 검색 > 문제 링크
babababa라는 큰 문자열이 있을 때, aba 같은 작은 문자열이 몇번 등장하는지 찾는 간단한 문자열 비교 문제다.
이 문제는 문자열의 모든 지점에서 문자열을 비교하고, 만약 일치하는 경우 해당 문자열 전체를 건너뛰는 방식으로 구현하였다.
c++에 존재하는 substr 함수를 통해서 시작점에서 작은 문자열의 길이만큼 문자를 자르고, 이 문자가 작은 문자열과 같은지를 비교하는 방식으로 구현했다.
i=0 일 때 작은 문자열의 크기만큼 문자열을 자르면 bab가 되는데, 이는 작은 문자열 aba와 일치하지 않는다. 그러므로 다음 인덱스에서 다시 탐색을 진행한다.
다음 인덱스에서 작은 문자열의 크기만큼 자르면, 작은 문자열과 일치함을 확인할 수 있다. 이러면 단어를 찾은 것이므로 결과값을 1 증가시키고, 탐색 된 문자열의 끝 지점의 다음 인덱스로 탐색 지점을 옮겨준다
이후 계속해서 탐색을 진행해서 결과값의 개수를 출력하면 된다.
#include <iostream>
#include <string>
using namespace std;
int main(){
string s1, s2;
// 문제에서 단어에 공백도 포함이라고 했으므로 getline으로 문자열을 입력받는다.
getline(cin, s1);
getline(cin, s2);
int cnt = 0;
for (int i = 0; i < s1.length(); i++) {
if (s1.substr(i, s2.length()) == s2) {
cnt++;
// 인덱스를 탐색 된 문자열의 끝 지점의 다음 인덱스로 옮겨준다
// s2.length() 만큼 옮기고 -1인 이유는 for문을 진행하면서 한번 더 i가 증가하기 때문
i += s2.length() - 1;
}
}
cout << cnt << endl;
}