문제 개요
문자열 S와 숫자 X가 주어졌다고 가정해 봅시다. 주사위를 굴리는 플레이어는 총 M명이며, 각 플레이어는 X가 아닌 다른 숫자가 나올 때까지 주사위를 계속해서 굴립니다. 문자열 S에서 S[i]는 i번째 주사위 굴림 결과를 나타내며, 우리의 목표는 이 문자열로부터 플레이어의 수 M을 구하는 것입니다.
단, 한 가지 제약 조건이 있습니다. 문자열 S의 마지막 문자는 절대 X가 될 수 없습니다. 이는 마지막에 굴린 사람이 반드시 X가 아닌 숫자를 얻고 게임을 마쳤음을 보장합니다.
예제
예를 들어, 문자열이 "3662123"이고 X = 6이라면 출력값은 5입니다. 이를 단계별로 살펴보면 다음과 같습니다.
- 첫 번째 플레이어가 주사위를 굴려 3이 나왔습니다.
- 두 번째 플레이어가 주사위를 굴려 6, 6, 2가 차례로 나왔습니다.
- 세 번째 플레이어가 주사위를 굴려 1이 나왔습니다.
- 네 번째 플레이어가 주사위를 굴려 2가 나왔습니다.
- 다섯 번째 플레이어가 주사위를 굴려 3이 나왔습니다.
두 번째 플레이어처럼 X(여기서는 6)가 연속으로 나오면 같은 플레이어가 계속 굴리는 것이고, X가 아닌 숫자가 나오는 순간 그 플레이어의 차례가 끝나고 다음 플레이어로 넘어갑니다.
접근 방법
풀이 방법은 매우 간단합니다. 문자열을 처음부터 끝까지 순회하면서 X가 아닌 문자의 개수를 세면 됩니다. 각 플레이어의 마지막 굴림은 반드시 X가 아닌 숫자이므로, X가 아닌 숫자의 총 개수가 곧 플레이어의 수와 일치합니다.
C++ 구현 예제
#include<iostream>
using namespace std;
int countPlayers(string str, int x) {
int count = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] - '0' != x)
count++;
}
return count;
}
int main() {
string s = "3662123";
int x = 6;
cout << "Number of players: " << countPlayers(s, x);
}
출력 결과
Number of players: 5
코드 설명
countPlayers 함수는 문자열과 목표 숫자 x를 매개변수로 받습니다. 반복문을 통해 문자열의 각 문자를 하나씩 확인하면서, 해당 문자를 정수로 변환한 값(str[i] - '0')이 x와 다르면 카운트를 1씩 증가시킵니다. 모든 문자를 검사한 뒤 최종 카운트 값을 반환하면, 그 값이 곧 플레이어의 수입니다.
이 알고리즘의 시간 복잡도는 O(n)(n은 문자열의 길이)이며, 추가 메모리를 거의 사용하지 않는 O(1)의 공간 복잡도를 가지므로 매우 효율적입니다.