두 개의 k자리 숫자 m과 n이 주어졌다고 가정해 봅시다. 각 숫자의 자릿수는 무작위로 섞인 상태에서 서로 비교되며, 우리는 어떤 숫자가 더 클 확률이 높은지 알아내야 합니다.
예를 들어 입력이 n = 231, m = 337, k = 3이라면 출력은 'Second'가 됩니다. 즉, 두 번째 숫자가 더 클 확률이 더 높다는 의미입니다.
풀이 접근 방식
이 문제는 다음 단계에 따라 해결할 수 있습니다.
- n을 문자열 s1으로, m을 문자열 s2로 변환합니다.
- 카운터 변수 f(첫 번째 숫자가 큰 횟수)와 s(두 번째 숫자가 큰 횟수)를 0으로 초기화합니다.
- i를 0부터 k-1까지 반복하면서 각 자릿수를 비교합니다. s1[i]가 s2[i]보다 크면 f를 1 증가시키고, s1[i]가 s2[i]보다 작으면 s를 1 증가시킵니다.
- 반복이 끝난 후 f가 s보다 크면 "First"를, s가 f보다 크면 "Second"를, 그렇지 않으면 "Equal"을 출력합니다.
각 자릿수 위치에서 어느 숫자의 자릿수가 더 큰지 세는 방식으로, 전체적으로 어느 쪽이 우세한지 직관적으로 판단할 수 있습니다.
s1 := convert n to string
s2 := convert m to string
f := 0, s = 0
for initialize i := 0, when i < k, update (increase i by 1), do:
if s1[i] > s2[i], then:
(increase f by 1)
otherwise when s1[i] < s2[i], then:
(increase s by 1)
if f > s, then:
print("First")
otherwise when s > f, then:
print("Second")
Otherwise
print("Equal")구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int n, int m, int k) {
string s1 = to_string(n);
string s2 = to_string(m);
int f = 0, s = 0;
for(int i = 0; i < k; i++){
if(s1[i] > s2[i])
f++;
else if(s1[i] < s2[i])
s++;
}
if(f > s)
cout<<"First"<<endl;
else if(s > f)
cout<<"Second"<<endl;
else
cout<<"Equal"<<endl;
}
int main() {
int n = 231, m = 337, k = 3;
solve(n, m, k);
return 0;
}입력
231, 337, 3
출력
Second
위 예제에서 첫 번째 숫자 231은 자릿수마다 두 번째 숫자 337보다 작거나 같은 경우가 많기 때문에, 최종 결과로 "Second"가 출력됩니다. 이처럼 자릿수별 비교만으로도 두 숫자의 우열을 간단하게 판별할 수 있습니다.