문자 "집합" 들의 같음을 판단하는 로직
글쓴이: Sailor_moon / 작성시간: 목, 2013/04/18 - 10:31오전
안녕하세요,
알고리즘 책 등을 보면서 공부하다가 한가지 궁금한 부분이 생겨서 문의드립니다.
문자들의 "집합"을 입력받아 그 같음을 보이는 함수를 작성하라 , 라는 질문이 있더라구요.
단 순서는 상관하지 않고 , 중복도 상관하지 않을때,
예를들어
{"가", "나"} 와 {"나","가"} , {"가","가","나"} 는 모두 같다고 취급하는 형식입니다.
제가 생각했던 방법은,
가장 짧은 길이의 집합을 하나 가져와서
배열 등에 저장을 해둔뒤에, 다음 인풋이 들어와서 존재하는지를 판단해서 모두 true 가 되면
같다 라고 판단하려고 했는데, 웬지 너무 심플하고 별로 이런 걸 묻는게 아니고, 세련된 방법을 묻는것 같아서
질문 드립니다.
혹시 다른 접근 방법이 있을까요 ?
Forums:
먼저 "집합"을 어떻게 구현할지부터 생각하는 게
먼저 "집합"을 어떻게 구현할지부터 생각하는 게 중요할 것 같네요.
집합인데 {"가", "가", "나"} 같은 식으로 정말 저장할 것인지 등등요.
사실 중복을 제하고 정렬해서 가지고 있으면 비교는 매우 쉽겠죠.
비트필드를 사용하는게 가장 깔끔해 보이는데요 n개의
비트필드를 사용하는게 가장 깔끔해 보이는데요
n개의 문자에 대해 n개의 자리를 가지는 비트필드를 c[n]으로 정의하고
가=0
나=1
다=2
...
이렇게 해 놓고
집합을 입력받으면 처음부터 끝까지 스캔하면서 "가"가 나오면 c[0]=1||c[0], "나"가 나오면 c[1]=1||c[1], 이런식으로 스캔해서 저장해 두면 중복은 무시되고 하나라도 있으면 해당 비트가 1이 되겠죠.
어떤 집합을 입력 받아도 이 과정을 통해서 하나의 고유한 수를 만들어 낼 수 있으므로, 이제 두 집합의 비교는 두 정수의 비교를 하면 됩니다.
피할 수 있을때 즐겨라! http://melotopia.net/b
gilgil.net
set template를 사용하면 됩니다.
[예제]
#include <set> #include <string> #include <iostream> using namespace std; typedef set<string> MySet; int main() { MySet set1, set2, set3; set1.insert("가"); set1.insert("나"); set2.insert("나"); set2.insert("가"); set3.insert("가"); set3.insert("가"); set3.insert("나"); if (set1 == set2) cout << "set1 == set2" << endl; else cout << "set1 != set2" << endl; if (set1 == set3) cout << "set1 == set3" << endl; else cout << "set1 != set3" << endl; }[결과]
www.gilgil.net
댓글 달기