문자 "집합" 들의 같음을 판단하는 로직

Sailor_moon의 이미지

안녕하세요,

알고리즘 책 등을 보면서 공부하다가 한가지 궁금한 부분이 생겨서 문의드립니다.

문자들의 "집합"을 입력받아 그 같음을 보이는 함수를 작성하라 , 라는 질문이 있더라구요.
단 순서는 상관하지 않고 , 중복도 상관하지 않을때,

예를들어

{"가", "나"} 와 {"나","가"} , {"가","가","나"} 는 모두 같다고 취급하는 형식입니다.

제가 생각했던 방법은,

가장 짧은 길이의 집합을 하나 가져와서

배열 등에 저장을 해둔뒤에, 다음 인풋이 들어와서 존재하는지를 판단해서 모두 true 가 되면
같다 라고 판단하려고 했는데, 웬지 너무 심플하고 별로 이런 걸 묻는게 아니고, 세련된 방법을 묻는것 같아서
질문 드립니다.

혹시 다른 접근 방법이 있을까요 ?

vacancy의 이미지


먼저 "집합"을 어떻게 구현할지부터 생각하는 게 중요할 것 같네요.

집합인데 {"가", "가", "나"} 같은 식으로 정말 저장할 것인지 등등요.

사실 중복을 제하고 정렬해서 가지고 있으면 비교는 매우 쉽겠죠.

snowall의 이미지

비트필드를 사용하는게 가장 깔끔해 보이는데요
n개의 문자에 대해 n개의 자리를 가지는 비트필드를 c[n]으로 정의하고
가=0
나=1
다=2
...

이렇게 해 놓고

집합을 입력받으면 처음부터 끝까지 스캔하면서 "가"가 나오면 c[0]=1||c[0], "나"가 나오면 c[1]=1||c[1], 이런식으로 스캔해서 저장해 두면 중복은 무시되고 하나라도 있으면 해당 비트가 1이 되겠죠.

어떤 집합을 입력 받아도 이 과정을 통해서 하나의 고유한 수를 만들어 낼 수 있으므로, 이제 두 집합의 비교는 두 정수의 비교를 하면 됩니다.

피할 수 있을때 즐겨라! http://melotopia.net/b

gilgil의 이미지

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;
}

[결과]

set1 == set2
set1 == set3

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.