๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
โœจ Algorithm

[๋ฐฑ์ค€/C++] 1316๋ฒˆ : ๊ทธ๋ฃน ๋‹จ์–ด ์ฒด์ปค

by nitronium102 2021. 9. 6.

๋ฌธ์ œ

๊ทธ๋ฃน ๋‹จ์–ด๋ž€ ๋‹จ์–ด์— ์กด์žฌํ•˜๋Š” ๋ชจ๋“  ๋ฌธ์ž์— ๋Œ€ํ•ด์„œ, ๊ฐ ๋ฌธ์ž๊ฐ€ ์—ฐ์†ํ•ด์„œ ๋‚˜ํƒ€๋‚˜๋Š” ๊ฒฝ์šฐ๋งŒ์„ ๋งํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค๋ฉด, ccazzzzbb๋Š” c, a, z, b๊ฐ€ ๋ชจ๋‘ ์—ฐ์†ํ•ด์„œ ๋‚˜ํƒ€๋‚˜๊ณ , kin๋„ k, i, n์ด ์—ฐ์†ํ•ด์„œ ๋‚˜ํƒ€๋‚˜๊ธฐ ๋•Œ๋ฌธ์— ๊ทธ๋ฃน ๋‹จ์–ด์ด์ง€๋งŒ, aabbbccb๋Š” b๊ฐ€ ๋–จ์–ด์ ธ์„œ ๋‚˜ํƒ€๋‚˜๊ธฐ ๋•Œ๋ฌธ์— ๊ทธ๋ฃน ๋‹จ์–ด๊ฐ€ ์•„๋‹ˆ๋‹ค.

๋‹จ์–ด N๊ฐœ๋ฅผ ์ž…๋ ฅ์œผ๋กœ ๋ฐ›์•„ ๊ทธ๋ฃน ๋‹จ์–ด์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ๋‹จ์–ด์˜ ๊ฐœ์ˆ˜ N์ด ๋“ค์–ด์˜จ๋‹ค. N์€ 100๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ๋‹จ์–ด๊ฐ€ ๋“ค์–ด์˜จ๋‹ค. ๋‹จ์–ด๋Š” ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ๋งŒ ๋˜์–ด์žˆ๊ณ  ์ค‘๋ณต๋˜์ง€ ์•Š์œผ๋ฉฐ, ๊ธธ์ด๋Š” ์ตœ๋Œ€ 100์ด๋‹ค.

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ๊ทธ๋ฃน ๋‹จ์–ด์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

ํ’€์ด

01. ๊ธฐ๋ณธ์ ์œผ๋กœ boolean ์ž๋ฃŒํ˜•์˜ ๋ฐฐ์—ด์„ ๋งŒ๋“ค๊ณ  0์œผ๋กœ ์ดˆ๊ธฐํ™”ํ•œ๋‹ค.

02. ๋ฌธ์ž๊ฐ€ ์ฒ˜์Œ์œผ๋กœ ๋‚˜์˜ค๋ฉด 1์„ ๋„ฃ์–ด์ค€๋‹ค.

03. ๋งŒ์•ฝ ์ด์ „์— ๋‚˜์˜จ ๋ฌธ์ž์™€ ํ˜„์žฌ ๋ฌธ์ž๊ฐ€ ๋‹ค๋ฅด๊ณ  ์•ŒํŒŒ๋ฒณ ๋ฐฐ์—ด์˜ ํ•ด๋‹น ๋ฌธ์ž๊ฐ€ 1์ด๋ผ๋ฉด(์ด๋ฏธ ๋‚˜์˜จ ์ ์ด ์žˆ๋‹ค๋ฉด) ๋ฐ”๋กœ returnํ•ด์ค€๋‹ค. 

word[0] - 97(ascii)์„ ํ•ด๋„ ์ข‹์ง€๋งŒ ํ˜น์‹œ ๋ชจ๋ฅผ ์—๋Ÿฌ๋ฅผ ๋ฐฉ์ง€ํ•˜๊ธฐ ์œ„ํ•ด 'a'๋กœ ์ž‘์„ฑํ•˜๋Š” ๊ฒƒ์ด ์ข‹๋‹ค. 
#include <iostream>
using namespace std;

bool alphabet[26]; // bool ์ž๋ฃŒํ˜•์œผ๋กœ ๋ณ€๊ฒฝ
int cnt = 0;

void checker(string word){
  fill_n(alphabet, 26, 0);
  alphabet[word[0] - 'a'] = 1; // ascii ์ฝ”๋“œ ๋Œ€์‹  'a'๋กœ ์ž‘์„ฑํ•˜๊ธฐ!

  for (int i=1; i<word.length(); i++){
    int idx = word[i] - 'a';
    // ๊ทธ๋ฃน ๋‹จ์–ด๊ฐ€ ์•„๋‹Œ ๊ฒฝ์šฐ
    if (word[i-1] != word[i] && alphabet[idx] != 0)
      return;
    alphabet[idx] = 1;
  }
  cnt++;
}

int main(){
  int n;
  string word;
  cin >> n;
  for (int i=0; i<n; i++){
    cin >> word;
    checker(word);
  }
  cout << cnt;
}

 

๋Œ“๊ธ€