백준 1105 c++ "팔" -PlusUltraCode-

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

 

 

[필자 사고]

수의 제한이 20억이다 그냥 단순 비교를 하게 되면 이 문제는 시간초과가 난다.

잠시 생각을 해보니 그리디 알고리즘이 떠올려졌다.

그래 탐욕적 접근을 해보자

조심히 생각해보니 두 문자열이라 가정하고 8의 갯수를 새면 되지 않을까?? 
입력 값들 경우의 수를 다 해보니 다 맞았따. 

하지만 코드를 작성했는데 틀렸다. 

이유를 곰곰히 생각해보니 앞자리의 8의 갯수만 새면되는 것이다.

생각해보니 사잇값 정리가 떠올려졌다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

Input 함수

• 사용자로부터 두 문자열 str1과 str2를 입력받는다.
• 이 문자열들은 숫자 형태이며, 앞자리가 동일할 수도 다를 수도 있다.

---

Game_Start 함수

• 먼저 두 문자열의 길이가 다른 경우를 확인한다.
  이 경우에는 앞자리부터 비교할 수 없기 때문에 곧바로 0을 출력하고 종료한다.
• 두 문자열의 길이가 같다면, 인덱스 0부터 순차적으로 두 문자의 값을 비교한다.
• 만약 두 문자가 다르면 반복을 중단한다. 이 시점 이후는 의미가 없기 때문이다.
• 두 문자가 같고 동시에 해당 문자가 '8'이면, 8의 개수를 나타내는 resultCount를 1 증가시킨다.
• 반복이 끝난 후 resultCount를 출력한다.

[소스 코드]

#include  <iostream>
#include <vector>
#include <cstring>
using namespace std;

string str1, str2;

void Input() {
	cin >> str1 >> str2;
}

void Game_Start() {
	int resultCount = 0;

	if (str1.length() != str2.length()) {
		cout << 0;
		return;
	}

	for (int i = 0; i < str1.size(); i++) {
		if (str1[i] != str2[i]) break;
		if (str1[i] == '8') resultCount++;
	}

	cout << resultCount;
}


int main(void) {
	Input();
	Game_Start();
}