Home > Algorithm > BOJ > [BOJ] 1141๋ฒˆ ์ ‘๋‘์‚ฌ

[BOJ] 1141๋ฒˆ ์ ‘๋‘์‚ฌ
C++ ๋ฐฑ์ค€ BOJ ์•Œ๊ณ ๋ฆฌ์ฆ˜ Algorithm

๐Ÿ”— ๋ฌธ์ œ

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