[백준] 1919번: 애너그램 만들기 C++로 풀어보기

1919번 설명

어떻게 풀까? (문제를 풀고 처음 든 생각)

1. 일단 단어 두 개를 입력받고 각각 벡터에 넣는다.

2. 첫번째 벡터의 알파벳을 두번째 배열의 알파벳이 겹치는 것이 있는지 루프를 돌린다.(이중루프 이용)

3. 찾으면 첫번째 벡터과 두번째 벡터에서 그 알파벳을 뺀다.
4. 그리고 계속 루프를 돌린다.

5. 루프가 다 끝나면 첫번째 벡터, 두번째 벡터에서 남은 알파벳 개수를 더한다.

코드

#include <bits/stdc++.h>
using namespace std;


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vector <char> v1;
	vector <char> v2;
	string word1;
	string word2;
	int cnt = 0;

	// 단어 두 개 입력
	cin >> word1;
	cin >> word2;

	// 벡터에 알파벳 입력
	for (int i = 0; i < word1.length(); i++) {
		v1.push_back(word1[i]);
	}

	for (int i = 0; i < word2.length(); i++) {
		v2.push_back(word2[i]);
	}


	// v1의 첫글자부터 v2를 순회하면서 같은 알파벳이 있는지 찾는다.
	for (auto it1 = v1.begin(); it1 != v1.end(); it1++) {
		for (auto it2 = v2.begin(); it2 != v2.end(); it2++) {
			if (*(it1) == *(it2)) { // 만약 같은 알파벳을 찾으면
				cnt++;
				it2 = v2.erase(it2);
				break;
			}
		}
	}

	cout << v1.size() - cnt + v2.size();

}

원래는 cnt 변수를 만들지 않고 it1 = v1.erase(it1);을 사용해서 첫번째 벡터의 알파벳도 삭제했었다.

하지만 그러면 알파벳이 삭제되면서 벡터가 한 칸씩 당겨져서 it1은 다음 알파벳을 가리키게 된다.

그리고 break가 걸리고 for문의 it1++ 때문에 또 다음 알파벳을 가리키게 되어서, 본의 아니게 it1이 두 칸을 점프하게 된다.

그래서 v1은 erase를 쓰지 않고, v1.size()에서 일치하는 알파벳 개수 cnt를 빼는 걸로 바꾸게 되었다.

 

※ 벡터에서 iterator를 이용할 때 왜 erase의 반환값을 다시 iterator에 대입하는가?

->  erase는 삭제에 성공할시 삭제한 요소의 바로 다음 iterator를 return 하기 때문이다.

(출처: https://backhugger.tistory.com/45) 

[C++] 벡터에서 std::erase로 요소 삭제시 주의사항

 

 

결과

1919번 결과

 

후기

의외로 시간이 많이 걸렸다. 만약 벡터가 아니라 배열을 이용해야 했다면 풀기 어려웠을 것 같다.

vector에서 iterator를 쓸 때 erase하는 방법을 익히게 되어서 좋았다.