๐ ๋ฌธ์
https://www.acmicpc.net/problem/1141
๐ ๋ฌธ์ ์์ฝ
์ ๋ ฅ: ์ฒซ์งธ ์ค์ ๋จ์ด์ ๊ฐ์ N์ด ์ฃผ์ด์ง๋ค. N์ 50๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๋จ์ด๊ฐ ์ฃผ์ด์ง๋ค. ๋จ์ด๋ ์ํ๋ฒณ ์๋ฌธ์๋ก๋ง ์ด๋ฃจ์ด์ ธ ์๊ณ , ๊ธธ์ด๋ ์ต๋ 50์ด๋ค. ์งํฉ์๋ ๊ฐ์ ๋จ์ด๊ฐ ๋ ๋ฒ ์ด์ ์์ ์ ์๋ค.
์ถ๋ ฅ: ์ ๋์ฌX ์งํฉ์ธ ๋ถ๋ถ์งํฉ์ ์ต๋ ํฌ๊ธฐ๋ฅผ ์ถ๋ ฅํ๋ค.
๐ก ์ ๊ทผ ๋ฐฉ๋ฒ
N๊ฐ์ ๋ฌธ์์ด์ ์
๋ ฅ ๋ฐ๊ณ , ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ์ ํ ๋ค,
๋ค์ ์ธ๋ฑ์ค์ ๋ฌธ์์ด์ ํ์ฌ ๋ฌธ์์ด์ด ์ ๋์ฌ๋ก ์ฌ์ฉ๋๋์ง ํ์ธํ๋ ๋ฐฉ์์ผ๋ก ๊ตฌํํ๋ค.
โ ๏ธ ์ฒ์์ ํ๋ ์ค์
if(words[i + 1].length() >= len && words[i + 1].substr(0,len) == words[i])
continue;
ํด๋น ๋ถ๋ถ์ ์ฝ๋๊ฐ ์๋๋
if(words[i + 1].length() < len)
continue;
if(words[i + 1].substr(0,len) == words[i])
continue;
์ด๋ฐ ์ฝ๋๋ก ์์ฑํ์๋ค.
์๋๋ ๋ค์ ๋ฌธ์์ด๋ณด๋ค ๊ธธ์ด๊ฐ ๊ธธ๋ฉด ์์น์๋ ๋ฐฉํฅ์ผ๋ก ์กฐ๊ฑด ๊ฒ์ฌ๋ฅผ ํ ๊น๋ด ๋ค์์ผ๋ก ๋๊ธฐ๋๋ก ํ๋ ์กฐ๊ฑด์ด์๋๋ฐ
๋ค์ ๋ฌธ์์ด์ด ํ์ฌ ๋ฌธ์์ด๋ณด๋ค ์งง์ผ๋ฉด ํฌํจ๋ ์ผ์ด ์๋ค๊ณ ๋ค์ ์๊ฐํด์ ์กฐ๊ฑด๋ฌธ์ ์์ ํ๋ค.
๐ป ์ฝ๋
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int N;
string words[51];
int main()
{
int ans = 0;
cin >> N;
for(int i = 0; i < N; ++i)
{
cin >> words[i];
}
sort(words, words + N);
for(int i = 0; i < N - 1; ++i)
{
int len = words[i].length();
if(words[i + 1].length() >= len && words[i + 1].substr(0,len) == words[i])
continue;
ans++;
}
ans++;
cout << ans;
return 0;
}