백준_11478_서로 다른 부분 문자열의 개수

[youbeen2798]

문제 : https://www.acmicpc.net/problem/11478
난이도 : 실버 3

문제를 풀다보면, vector보다 set이나 map을 쓰는게 효율성이 좋을 때를 종종 볼수 있다.

하지만, set과 map을 사용하는 것에 익숙치 않기 때문에,
오늘은 set에 관련된 기초 문제를 중심으로 풀어보려 한다.

문제
문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램

예를 들어, ababc의 부분 문자열은
{a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc}로,
결과값은 12

구현

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

string st;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> st;

	unordered_set <string> uset;
	for (int i = 0; i < st.size(); i++) {
		for (int j = 1; j <= st.size() - i; j++) {
			string k = st.substr(i, j); //substr의 첫번째 인자는 시작 위치, 두번째 인자는 개수
			uset.insert(k); //unordered_set에 원소 추가하기
		}
	}
	cout << uset.size();
}

set의 장점

1. 중복 원소를 직접 제거하지 않아도, 자동으로 중복을 없애준다.
2. 특정 원소를 추가하거나 지우는 작업이 O(logN)으로 빠른 편이다.

이 문제는 중복을 제거해야 하기 때문에, 자연스럽게 set으로 풀게 되었다.

unordered_set과 set의 차이
unordered_set은 insert(추가), erase(삭제), find(찾기)의 시간복잡도가 O(1)이다.

근데,, 이상하게 백준에서 set보다 unordered_set으로 코드를 돌렸을 때, 시간이 더 크게 나왔다..?!(이거 이유 아는 사람 알려쥬..)

[ghdcksgml1]

unordered_set 이 더 큰 이유는 시간복잡도상으로는 O(1)이여서 더 빨라야하는게 맞음. 근데 O(logN) 시간복잡도도 엄청 빠른거잖아? ex) (1) = 1, (log₂2⁶³) = 63
unordered_set 함수로직의 탐색이나 해쉬 값을 만드는 연산이 set보단 느려서 그런거일듯

[youbeen2798]

해쉬 함수에 대해 더 알아봐야겠군...
답변 땅콩베리망치><