#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int arr[1002];
vector<int> two;

int main()
{
	//1. Get input value
	ios::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i];
	}

	//2. Find the multiplication of all elements.
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			two.push_back(arr[i] + arr[j]);
		}
	}
	sort(arr, arr + N);
	sort(two.begin(), two.end());

	for (int i = N - 1; 0 < i; --i)
	{
		for (int j = 0; j < i; ++j)
		{
			if (binary_search(two.begin(), two.end(), arr[i] - arr[j]) == true)
			{
				cout << arr[i];
				return 0;
			}
		}
	}

	return 0;
}

||사고 과정

처음에는 주어진 수열에서 그 수열에 속한 최대 결과값을 찾는게 막연한 느낌을 받았다.

이런 느낌을 받을 때 정의역과 공역이 확실하면 거꾸로 하는게 대부분이여서 이번에도 거꾸로 해보기로 했다.

 

그래서 주어진 수열을 오름차순으로 정렬하여 마지막 원소부터 세 원소의 합이 가능한지 살펴보았는데

O(n^3)보다 작은 방법을 찾지 못했다..ㅠ

 

한시간쯤 시도 후 찾지 못해 다른 사람의 풀이를 보고 다시 혼자 풀어 보았다.

방법은 두 원소의 모든 합을 저장하여 이분탐색으로 찾아가며 풀이하는 방법이였다..

어떻게 보면 무식한 방법인데 시간을 계산해보면 O(N^2 * logN)의 복잡도로 괜찮은 방법이였다.


||사용 기법

  • Binary search

||풀면서 느낀 것

  • 시간 복잡도 계산을 해보자

시간 복잡도를 대강 보지 말고 내 방법에 대한 복잡도 계산을 해보는 걸 지금부터라도 해야겠다.

  • 이러한 유형 기억

이분 탐색에서 이렇게 어떤 수끼리 묶고 탐색을 하는 경우가 많다고 한다. 잘 기억해둘것!


||더 나은 풀이

바뀐 부분만 적으면

	//2. Find the multiplication of all elements.
	for (int i = 0; i < N; ++i)
	{
		for (int j = i; j < N; ++j)
		{
			two.push_back(arr[i] + arr[j]);
		}
	}
	sort(arr, arr + N);
	sort(two.begin(), two.end());
	for (int i = N - 1; 0 < i; --i)
	{
		for (int j = i - 1; 0 <= j; --j)
		{
			if (binary_search(two.begin(), two.end(), arr[i] - arr[j]) == true)
			{
				cout << arr[i];
				return 0;
			}
		}
	}

첫번째의 이중 반복문에서 중복 되는 경우를 없애 주었다.

두번째의 이중 반복문에서 i와 같은 값의 j를 빼는 경우를 제외했다.

 

이러한 처리 후 시간이 반 정도 절약 됐다.

#include <iostream>
#include <algorithm>

#define MAX 1'000'002
using namespace std;

pair<int, int> arr[MAX];

bool comp(const pair<int, int> & a, const pair<int, int> & b)
{
	return a.second < b.second;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int N; cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i].first;
		arr[i].second = i;
	}
	sort(arr, arr + N);

	int std = 0;
	for (int i = 0; i < N; ++i)
	{
		//바로 오른쪽이 자신과 같은지 
		if (arr[i].first == arr[i + 1].first) arr[i].first = std;
		else arr[i].first = std++;
	}
	sort(arr, arr + N, comp);
	
	for (int i = 0; i < N; ++i)
	{
		cout << arr[i].first << " ";
	}
		
	return 0;
}

||사고 과정

문제의 Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

는 말이 이해하기 힘들었지만 그냥 최소값부터 압축하라는 뜻..

 

Upper bound, Lower bound를 공부하면서 보게 된 문제여서 처음에는 Upper bound를 이용해서 풀려고했지만

1, 2, 3, 4, 5 처럼 중복되는 수가 없는 경우면 매 수마다 Upper bound를 하게 되니까 비효율적이라 생각해서

바로 옆에 있는 수를 비교해서 압축하는게 오히려 나을 수도 있겠다고 생각이 들어서 이렇게 풀게 됐다.


||더 나은 풀이

#include <iostream>
#include <algorithm>

#define MAX 1'000'002
using namespace std;

pair<int, int> arr[MAX];
int result[MAX];

bool comp(const pair<int, int> & a, const pair<int, int> & b)
{
	return a.second < b.second;
}


int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int N; cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i].first;
		arr[i].second = i;
	}
	sort(arr, arr + N);

	int std = 0; 
	for (int i = 1; i < N; ++i)
	{
		if (arr[i].first != arr[i - 1].first) ++std;
		result[arr[i].second] = std;
	}
	
	for (int i = 0; i < N; ++i)
	{
		cout << result[i]<< " ";
	}
		
	return 0;
}

다른 사람들의 코드를 보던 중에 내 코드에서 sort한번을 생략 할 수 있음을 알았다.

 

배열을 하나 더 추가해서 arr[i]의 원래 순서의 인덱스에 넣는 방법이였다.

=> result[arr[i[.second] = std;

 

다른 문제에서 이렇게 원래 순서를 sort해서 가져오는 경우가 종종있었는데 앞으로 좀 더 빠르게 구현할 수 있겠다.

 

추가로 lower_bound를 이용해 푸는 방법으로 바킹독님 코드를 빌려왔다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int x[1000005];
vector<int> uni; // unique
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i];
		uni.push_back(x[i]);
	}
	sort(uni.begin(), uni.end());
	uni.erase(unique(uni.begin(), uni.end()), uni.end());
	for (int i = 0; i < n; i++)
		cout << lower_bound(uni.begin(), uni.end(), x[i]) - uni.begin() << ' ';
}

정렬 후 중복제거를 하게 되면 각 인덱스가 좌표압축한 결과와 같아진다.

ex) 

원본 배열 : [3] [2] [3] [3] [2] [4]

정렬 후 중복제거 : [2] [3] [4]

 

여기서 [2]는 인덱스가 0으로 2를 좌표압축한 결과와 같고 3, 4 도 마찬가지다.

이분탐색은 인덱스의 위치를 알 수 없으니 lower_bound로 그 위치를  알아내서 풀이하는 방법

'코딩 테스트 > 알고리즘 풀이' 카테고리의 다른 글

[백준 - 9663] N-Queen  (0) 2022.08.27
[백준 - 1074] Z  (0) 2022.08.26
[백준 - 1920] 수 찾기  (0) 2022.08.25
[백준 - 2156] 포도주 시식  (0) 2022.08.24
[백준 - 9465] 스티커  (0) 2022.08.23

개요

이분 탐색문제를 풀이하다 나온 개념


특징

이분 탐색을 응용한 알고리즘으로

정렬된 수열에서 찾고자 하는 값들의의 첫인덱스, 마지막 인덱스 + 1 을 구할 수 있다.


왜 사용하는가?

경험상 적절한 위치를 알기 위해서 사용하는 것 같다.

Lower bound는 찾고자 하는 값 이상의 부분수열에서 첫번째 인덱스

Upper bound는 찾고자 하는 값을 초과하는 부분수열에 첫번째 인덱스

 

이 위치들의 특징은 이곳에 찾고자 하는 값을 삽입해도 오름차순이 유지되는 특징이있다.

그리고 Upper bound -  Lower bound 의 값은 그 안에 속한 원소의 개수도 구할 수 있다.


구현


Lower bound

int Lower_bound(const int * arr, const int & size, const int & f)
{
	int s = 0, e = size, m;
	while (s < e)
	{
		m = (s + e) / 2;

		if (f <= arr[m]) e = m;
		else s = m + 1;
	}

	return s;
}

Lower bound는 f 가 시작 되는 지점을 찾는게 목표이다.

고로

시작지점은 arr[s] <= f, 끝 지점은 f <= arr[e] 라는 조건이 붙는다.

 

f <= arr[m] 일때 이 조건과 같은 e를 m에 두고 

나머지 경우인 arr[m] < f 는 해당되는 s를 m의 위치에 두되,

그냥 두면 s가 f에 도달하지 못하므로 m + 1인 인덱스를 s에 부여해준다.


Upper bound

int Upper_bound(const int * arr, const int & size, const int & f)
{
	int s = 0, e = size, m;
	while (s < e)
	{
		m = (s + e) / 2;

		if (f < arr[m]) e = m;
		else s = m + 1;
	}

	return e;
}

Upper bound는 f 가 끝나는 지점 + 1 을 찾는게 목표이다.

고로

시작지점은 arr[s] <= f, 끝 지점은 f < arr[e] 라는 조건이 붙는다.

 

f < arr[m] 일때 이 조건과 같은 e를 m에 둔다면 f와 arr[e]는 같은 값이 될수 없으며

나머지 경우인 arr[m] <= f 는 위으 Lower bound와 같다.


 

 

'코딩 테스트 > 알고리즘' 카테고리의 다른 글

Binary search  (0) 2022.08.25
#include <iostream>
#include <algorithm>

using namespace std;
int arr[100'002];

int BinarySearch(const int * arr, const int & size, const int & f)
{
	int s = 0, e = size - 1, m;

	while (s <= e)
	{
		m = (s + e) / 2;

		if (arr[m] == f) return 1;
		if (arr[m] < f) s = m + 1;
		else e = m - 1;
	}
	return 0;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	
	int N; cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);

	int M,F; cin >> M;
	for (int i = 0; i < M; ++i)
	{
		cin >> F;
		cout << BinarySearch(arr, N, F) << "\n";
	}

	return 0;
}

||사고 과정

단순 이분탐색을 사용하는 문제,

직접 구현하여 풀이했다.


||사용 기법

  • Binary Search

||더 간단한 풀이

#include <iostream>

using namespace std;
int arr[100'002];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	
	int N; cin >> N;
	int temp;
	for (int i = 0; i < N; ++i)
	{
		cin >> temp;
		arr[temp] = 1;
	}

	int M,F; cin >> M;
	for (int i = 0; i < M; ++i)
	{
		cin >> F;
		cout << (arr[F] == 1 ? 1 : 0) << "\n";
	}

	return 0;
}

이런식으로 정렬 없이 할 수 있을것 같아서 생각해봤지만 들어오는 수의 범위가 int형이므로

int형의 범위만큼 배열을 정의할 수 없기에 비슷한 동작인 Set을 사용해볼것이고

그 중 항상 100% 안정성이 있지는 않지만 빠른 unordered_set을 사용해보았다.

#include <iostream>
#include <unordered_set>

using namespace std;
unordered_set<int> S;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	
	int N; cin >> N;
	int temp;
	for (int i = 0; i < N; ++i)
	{
		cin >> temp;
		S.insert(temp);
	}

	int M,F; cin >> M;
	for (int i = 0; i < M; ++i)
	{
		cin >> F;
		cout << ((S.find(F) == S.end()) ? 0 : 1) << "\n";
	}

	return 0;
}

여기서 놀라웠던건 시간인데

상수시간을 가지는 u_set보다 n log n의이분탐색이 더 빠르게 나왔다.

 

O(1)과 O(log N)에서 시간복잡도에 붙은 상수로 자주 뒤집어질수있다고 한다.

항상 상수를 떼고 계산하다보니까 그럴수도 있다는 생각을 하지 못했다.

 

글 읽기 - HashMap이 이분탐색보다 느린 이유가 뭔가요?

댓글을 작성하려면 로그인해야 합니다.

www.acmicpc.net

'코딩 테스트 > 알고리즘 풀이' 카테고리의 다른 글

[백준 - 1074] Z  (0) 2022.08.26
[백준 - 18870] 좌표 압축  (0) 2022.08.25
[백준 - 2156] 포도주 시식  (0) 2022.08.24
[백준 - 9465] 스티커  (0) 2022.08.23
[백준 - 11057] 오르막 수  (0) 2022.08.23
#include <iostream>
#include <algorithm>

using namespace std;

int dp[10'001][4] = {0,};
int arr[10'001] = {0,};

int main()
{
	//1. Get input value
	ios::sync_with_stdio(0), cin.tie(0);

	int n; cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
	}

	//2. Set initial value
	dp[1][1] = dp[1][0] = 0;
	dp[1][2] = dp[1][3] = arr[1];

	for (int i = 2; i <= n; ++i)
	{
		dp[i][0] = max(dp[i - 1][2], dp[i - 1][3]);
		dp[i][1] = dp[i - 1][0];
		dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + arr[i];
		dp[i][3] = dp[i - 1][2] + arr[i];
	}

	//3. Print
	cout << max(max(dp[n][0], dp[n][1]), max(dp[n][2], dp[n][3]));
	return 0;
}

||사고 과정

비슷한 문제를 좀 풀어서 풀이방법은 어렵지 않게 생각 할 수 있었다.

다만 나는 이차원 테이블을 사용하여 좀 어렵게 풀었다.

 

이번에도 그냥 감으로 이차원 테이블로 사용했던것 같다.

그래서 dp[ i ][ j ]에서 [ j ]의 경우를 찾으려고 하니까 처음에는 3개가 나왔다.

1번 쉬는 경우, 1번째로 마시는 경우, 2번째로 마시는 경우

 

사실 2번 쉬는 경우가 포함되어야 하지만 나는 최대로 마실거니까 1번만 쉬어도 되지 않을까 라는 생각을 했다.ㅠ

그래서 처음에 틀렸다가 예외를 찾고 추가하여 정답을 맞췄다.


||사용 기법

  • DP

||풀면서 느낀 것

  • 테이블을 이차원으로 사용하는 것을 잘 생각해서 설정해야겠다.

요새 이차원으로 DP를 풀다보니 이것도 당연히 이차원일꺼라는 안일한 생각이 있었다ㅠㅠ

감으로 풀지말고 확실한 논리로 테이블을 세팅하자ㅠ

  • 이런 문제는 뭔가 어차피 안해도 돼~ 라는 예외가 있는것 같다.

어떠한 경우는 생각해야하지 않을까? 하면 어차피 안해도 되는 예외같은게 많았다.

나는 이 문제에서 i번째 포도주를 안마시고 dp[i - 2]가 최대값일 수도 있지 않나? 라는 생각이 있었는데

필요 없는 예외였다.

다음에는 예외를 좀 더 논리적으로 제거해가야겠다.


||나아 진것

  • 예외 생각

다른 사람것을 보지 않고 잘 생각했음

 


||더 나은 풀이

#include <iostream>
#include <algorithm>

using namespace std;

int dp[10'001] = { 0, };
int arr[10'001] = { 0, };

int main()
{
	//1. Get input value
	ios::sync_with_stdio(0), cin.tie(0);

	int n; cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
	}

	//2. Set initial value
	dp[1] = arr[1];
	dp[2] = arr[2] + arr[1];

	for (int i = 3; i <= n; ++i)
	{
		dp[i] = max(dp[i - 3] + arr[i - 1], dp[i - 2]) + arr[i];
		dp[i] = max(dp[i - 1], dp[i]);
	}

	//3. Print
	cout << dp[n];
	return 0;
}

일차원 테이블로 풀이하는 방법이다.

dp[ i ]는 i번째 포도주에 왔을 때 최대로 마실 수 있는 양을 지닌다.

그 양의 경우의 수는 세가지인데

1) i번째를 두번째로 마시는 경우,

이는 i - 3의 최대 값과 arr[ i - 1 ]을 더해주면 arr[ i ]가 알아서 두번째로 마시는게 된다.

 

2)i번째를 첫번째로 마시는 경우,

이는 i - 1을 안마신경우이므로 dp[ i - 2 ]에서 현재 arr [ i ]을 더해주면 된다.

 

3)i번째를 안마시는 경우,

당연히 dp[i - 1] 이다.

dp[i - 2]라는 선택지도 있을것같지만 잘 생각해보면 dp[i - 2] <= dp[i - 1] 가 될 수 밖에 없다.

 

'코딩 테스트 > 알고리즘 풀이' 카테고리의 다른 글

[백준 - 18870] 좌표 압축  (0) 2022.08.25
[백준 - 1920] 수 찾기  (0) 2022.08.25
[백준 - 9465] 스티커  (0) 2022.08.23
[백준 - 11057] 오르막 수  (0) 2022.08.23
[백준 - 1543] 문서 검색  (0) 2022.08.23
#include <iostream>
#include <algorithm>

#define MAX 100001
using namespace std;

int dp[MAX][3];
int arr[2][MAX];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int T; cin >> T;

	while (T--)
	{
		//1. Get input value
		int N; cin >> N;
		for (int i = 0; i < 2; ++i)
		{
			for (int j = 1; j <= N; ++j)
			{
				cin >> arr[i][j];
			}
		}
		
		//2. Set initial value
		dp[1][0] = arr[0][1];
		dp[1][1] = arr[1][1];
		dp[1][2] = 0;

		//3. Do fill DP table
		for (int i = 2; i <= N; ++i)
		{
			dp[i][0] = max(dp[i - 1][2], dp[i - 1][1]) + arr[0][i];
			dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + arr[1][i];
			dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]);
		}

		//4. Print
		cout << max(dp[N][0], max(dp[N][1], dp[N][2])) << "\n";
	}
	return 0;
}

||사고 과정

생각하는데 한 40분정도 소모했던 문제였다.

처음에 뭔가 직감적으로 일차원 테이브로는  풀지못하여 이차원 테이블인것 같았지만

인덱스마다 의미하는 것을 찾는게 어려웠다.

 

DP[ i ] [ j ] 에서 i는 분명 데이터의 개수를 뜻하는 것이니 j의 의미를 찾고 있던 와중에

데이터에서 나올 수 있는 경우의 수를 좀 더 집중적으로 생각했다.

상하좌우로 인접한 스티커는 땔수 없으니

하나의 열(i)에서 위의 스티커를 떼는 경우, 아래의 스티커를 떼는 경우, 떼지 않는 경우를 생각했다.

 

이 떼지 않는 경우를 생각하기가 어려웠는데 처음 본다고 생각하면

많은 스티커를 떼는게 목표지만 떼지 않는 경우를 구한다 라는게 와닿지 않았던것 때문이였던것 같다.

 

아무튼 이렇게 세가지를 j에 대응시켜서 손코딩으로 값을 찾아가니 점화식도 나오고 풀게 되었던 문제다.


||사용 기법

  • DP

||풀면서 느낀 것

  • 이차원 배열 테이블의 느낌

DP[i][j]라면 i는 데이터의 개수이고, j는 데이터에서 나올 수 있는 경우의수 를 뜻하는게 많았던것 같다.

  • 넓게 생각하자

처음에는 무조건 많이 떼는게 최대가 나온다고 생각했지만 아니였다.

테스트 케이스가 아니였다면 생각하지 못했을거다.

어떻게 보면 예외처리를 잘하자라는 말ㅋㅋㅠ

  • 테이블의 의미를 찾는게 이번에는 도움이 되었다.

경험상 의미를 찾으면 점화식도 금방 나오는것 같기에

다음에는 좀 더 집중해서 찾아봐야겠다.

 

'코딩 테스트 > 알고리즘 풀이' 카테고리의 다른 글

[백준 - 1920] 수 찾기  (0) 2022.08.25
[백준 - 2156] 포도주 시식  (0) 2022.08.24
[백준 - 11057] 오르막 수  (0) 2022.08.23
[백준 - 1543] 문서 검색  (0) 2022.08.23
[백준 - 1309] 동물원  (0) 2022.08.22
#include <iostream>
#define MOD 10007
#define ALL 10
using namespace std;
//일차원의 10번째 인덱스는 총합을 의미한다.
long long dp[1001][11] = { 0, };

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	for (int i = 0; i < 10; ++i)
	{
		dp[1][i] = 1;
		dp[1][ALL] += dp[1][i];
	}
	
	for (int i = 2; i <= N; ++i)
	{
		dp[i][ALL] = dp[i][0] = (dp[i - 1][ALL]) % MOD;
		for (int j = 1; j < 10; ++j)
		{
			dp[i][j] = (dp[i][j - 1] - dp[i - 1][j - 1] + MOD) % MOD;
			dp[i][ALL] = (dp[i][ALL] + dp[i][j]) % MOD;
		}
	}
	
	cout << dp[N][ALL]<< endl;

	return 0;
}

||사고 과정

처음에 2까지 경우의 수를 작성해보고

0부터 시작하는 경우의수, 1부터 시작하는 경우의 수 이렇게 나누어 생각을 했던것같다.

 

그렇게 나누어 보다보니까

두자리에서 0으로 시작하는 경우의 수는 한자리의  0 ~ 9로 시작하는 수,

두자리에서 1으로 시작하는 경우의 수는 한자리의  1 ~ 9로 시작하는 수,

...

두자리에서 9으로 시작하는 경우의 수는 한자리의  9로 시작하는 수,

가 나왔다.

 

그래서 자리수를 i, 시작하는 수를 j로 dp[i][j]형태의 이차원 배열로 테이블을 설정했다.

그 후 점화식을 세워보았고

dp[i][0]은 어쩔 수 없이 dp[i - 1][0] + ...  + dp[i - 1][9] 까지 더해주어야했고

dp[i][1]부터는 dp[i][j] = dp[i][j - 1] - dp[i - 1][j - 1] 이라는 식을 쉽게 세울수 있었다.

 


||사용 기법

  • DP

||풀면서 느낀 것

  • 테이블설정 후 점화식 작성

역시 DP는 이렇게 푸니까 많이 수월하다.


||새로 알게 된것

  • MOD 관련

코드부터 예외까지 15분정도로 모두 끝냈지만 MOD 연산 때문에 시간이 많이 소요 됐다. 

MOD연산은 오버프로우(음수)를 막기위해 사용되는 것으로 음수가 나와서는 안되는데

중간에 A = ( A - B ) % MOD 이런 연산이 있는데 A - B에서 이미 음수가 나와 MOD를 해도 의미가 없는 경우가 있었다.

 

그래서 찾은 방법이 MOD를 더해주는것,

A = ( A - B + MOD ) % MOD


||나아 진것

  • 깔끔한 풀이 사고 였다.

'코딩 테스트 > 알고리즘 풀이' 카테고리의 다른 글

[백준 - 2156] 포도주 시식  (0) 2022.08.24
[백준 - 9465] 스티커  (0) 2022.08.23
[백준 - 1543] 문서 검색  (0) 2022.08.23
[백준 - 1309] 동물원  (0) 2022.08.22
[백준 - 1699] 제곱수의 합  (0) 2022.08.22

내가 작성했던 코드

#include <iostream>
#include <string>

using namespace std;

string str;
string f_str;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	getline(std::cin, str);
	getline(std::cin, f_str);

	int d_length = str.length();
	int f_length = f_str.length();

	int cnt = 0;
	int result;
	while ((result = str.find(f_str)) != string::npos)
	{
		++cnt;
		str = str.substr(result + f_length, d_length);
	}
	cout << cnt;
	return 0;
}

다른 분이 작성한 더 나이스한 방법(하단)

int a;
int main() 
{
	string s, y;
	getline(cin, s); getline(cin, y); 
	auto pos = s.find(y); 
	
	while (pos != string::npos)
	{
		a++;
		pos = s.find(y, pos + y.size());
	}
	cout << a; 
}

||사고 과정

단어 검색이 중복없이 최대로 나오게 하려면 맨앞부터 차근차근 검색해가면 되니까 어려운건 없었고

검색하는 함수를 찾아보는데에 시간이 더 걸렸다.


||풀면서 느낀 것

  • 문자열 문제도 항상 하나이상은 풀어야겠다.

문자열 문제는 가끔 풀게 되는데 할때마다 까먹는거 같아서 하루에 한번은 풀어야겠다.

'코딩 테스트 > 알고리즘 풀이' 카테고리의 다른 글

[백준 - 9465] 스티커  (0) 2022.08.23
[백준 - 11057] 오르막 수  (0) 2022.08.23
[백준 - 1309] 동물원  (0) 2022.08.22
[백준 - 1699] 제곱수의 합  (0) 2022.08.22
[백준 - 7576] 토마토  (0) 2022.08.18

+ Recent posts