Home > Algorithm > BOJ > [BOJ] 2890๋ฒˆ ์นด์•ฝ

[BOJ] 2890๋ฒˆ ์นด์•ฝ
C++ ๋ฐฑ์ค€ BOJ ์•Œ๊ณ ๋ฆฌ์ฆ˜ Algorithm

๐Ÿ”— ๋ฌธ์ œ

https://www.acmicpc.net/problem/2890


๐Ÿ“Œ ๋ฌธ์ œ ์š”์•ฝ

์ƒ๊ทผ์ด๋Š” ์นด์•ฝ ๋Œ€ํšŒ๋ฅผ ๊ฐœ์ตœํ–ˆ๋‹ค. ๋Œ€ํšŒ๋Š” ์ „์„ธ๊ณ„์— ์ƒ์ค‘๊ณ„๋˜๊ณ , ์œ„์„ฑ์ด ๊ฒฝ๊ธฐ์žฅ ์ „์ฒด๋ฅผ ์ดฌ์˜ํ•˜๊ณ  ์žˆ๋‹ค. ์ƒ๊ทผ์ด๋Š” ์œ„์„ฑ ์‚ฌ์ง„์„ ๋ฐ”ํƒ•์œผ๋กœ ์‹ค์‹œ๊ฐ„ ์ˆœ์œ„๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค.
์œ„์„ฑ ์‚ฌ์ง„์€ Rํ–‰ C์—ด์ด๋‹ค. ๋ชจ๋“  ์ค„์˜ ์ฒซ ๋ฒˆ์งธ ๊ธ€์ž๋Š” โ€˜Sโ€™์ด๊ณ  ์ถœ๋ฐœ์„ ์„ ์˜๋ฏธํ•œ๋‹ค. ๋˜, ๋งˆ์ง€๋ง‰ ๊ธ€์ž๋Š” โ€˜Fโ€™์ด๊ณ  ์ด๊ฒƒ์€ ๊ฒฐ์Šน์„ ์„ ์˜๋ฏธํ•œ๋‹ค. ๋Œ€ํšŒ์— ์ฐธ๊ฐ€ํ•œ ํŒ€์€ ์ด 9ํŒ€์ด๊ณ , ๊ฐ ํŒ€์€ 1๋ถ€ํ„ฐ 9๊นŒ์ง€ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ ธ ์žˆ๋‹ค. ์นด์•ฝ์€ ํ•ญ์ƒ ์—ด์— ๋Œ€ํ•ด ์—ฐ์†ํ•˜๋Š” ์„ธ ์นธ์„ ์ฐจ์ง€ํ•˜๋ฉฐ, ์นด์•ฝ ๋ฒˆํ˜ธ๋กœ ํ‘œ์‹œํ•œ๋‹ค. ๋งˆ์ง€๋ง‰์œผ๋กœ ๋ฌผ์€ โ€˜.โ€™๋กœ ๋‚˜ํƒ€๋‚˜ ์žˆ๋‹ค.
ํŒ€์˜ ์ˆœ์œ„๋Š” ๊ฒฐ์Šน์„ ์œผ๋กœ๋ถ€ํ„ฐ ๋–จ์–ด์ง„ ๊ฑฐ๋ฆฌ๋กœ ์ธก์ •ํ•œ๋‹ค. ๊ฐ€๊นŒ์šธ์ˆ˜๋ก ์ˆœ์œ„๊ฐ€ ๋†’๋‹ค. ๋งŒ์•ฝ, ๋‘ ํŒ€์ด ๊ฒฐ์Šน์„ ๊ณผ ๋–จ์–ด์ง„ ๊ฑฐ๋ฆฌ๊ฐ€ ๊ฐ™๋‹ค๋ฉด, ๊ฐ™์€ ๋“ฑ์ˆ˜์ด๋‹ค.

์ž…๋ ฅ: ์ฒซ์งธ ์ค„์— R๊ณผ C๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ R๊ฐœ ์ค„์—๋Š” โ€˜.โ€™, โ€˜Sโ€™, โ€˜Fโ€™, โ€˜1โ€™~โ€™9โ€™๋กœ ์ด๋ฃจ์–ด์ง„ ์œ„์„ฑ ์ง€๋„๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ํ•œ ์ค„์—๋Š” ์ตœ๋Œ€ ํ•œ ๊ฐœ์˜ ์นด์•ฝ๋งŒ ์žˆ๊ณ , ์œ„์„ฑ ์‚ฌ์ง„์— ์žˆ๋Š” ์นด์•ฝ์€ ํ•ญ์ƒ 9๊ฐœ์ด๋‹ค. (10 โ‰ค R, C โ‰ค 50)
์ถœ๋ ฅ: ์ถœ๋ ฅ์€ ์ด 9์ค„์„ ํ•ด์•ผ ํ•œ๋‹ค. i๋ฒˆ์งธ ์ค„์—๋Š” i๋ฒˆ ํŒ€์˜ ๋“ฑ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. (i=1~9)


๐Ÿ’ก ์ ‘๊ทผ ๋ฐฉ๋ฒ•

์ž…๋ ฅ ๋ฐ›์€ ์ˆซ์ž๋ฅผ ์ธ๋ฑ์Šค๋กœ ๋งˆ์ง€๋ง‰ ์œ„์น˜๋ฅผ ๋ฐฐ์—ด์— ๋‹ด๊ณ ,
ํ•ด๋‹น ๋ฐฐ์—ด์„ ๊ธฐ์ค€์œผ๋กœ ๊ฒฐ์Šน์ ์—์„œ๋ถ€ํ„ฐ ๋žญํ‚น์„ ๋‹ค๋ฅธ ๋ฐฐ์—ด์— ๋‹ด์•„ ์ถœ๋ ฅํ–ˆ๋‹ค.


โš ๏ธ ์ฒ˜์Œ์— ํ–ˆ๋˜ ์‹ค์ˆ˜


๐Ÿ’ป ์ฝ”๋“œ

#include <iostream>
using namespace std;

int R, C;
char map[51][51];
int pos[10];
int r[10];

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

  cin >> R >> C;

  for (int i = 0; i < R; ++i) {
    for (int j = 0; j < C; ++j) {
      cin >> map[i][j];
      if (map[i][j] > '0' && map[i][j] <= '9')
        pos[map[i][j] - '0'] = j;
    }
  }

  int rank = 1;
  for (int i = C - 2; i > 0; --i) {
    bool isRanking = false;
    for (int j = 1; j <= 9; ++j) {
      if (pos[j] != i)
        continue;

      r[j] = rank;
      isRanking = true;
    }

    if (isRanking)
      rank++;
  }

  for (int i = 1; i <= 9; ++i) {
    cout << r[i] << '\n';
  }
  return 0;
}