BaekJoon 8595 히든넘버

Link : https://www.acmicpc.net/problem/8595

소스 결과 : 6748 KB / 0 ms

출처 : BackJoon , JPOI 2010 3번

 

설명

문자열 중에 히든넘버의 합을 구하는 문제

얼핏 보면 간단해 보이지만 함정이 존재한다.

 

C++의 경우 string 클래스의 method를 이용해서 푸는 알고리즘이 존재하는데

간단히 설명하면 알파벳이 아닌 인덱스를 찾은후 삭제, 삭제된열에서 알파벳의 인덱스를 검색

그 사이를 stoi 를 이용해 숫자로 변환, 반복 방법이 존재하는데

해당 방법을 사용해 봤자 기다리고 있는건 시간초과

 

string 클래스를 사용하기보다는 char 배열을 이용해 푸는 방법이 훨씬 마음 편하다.

 

또하나의 함정은

문자열의 최대길이는 5,000,000, 그리고 히든넘버는 최대 6자리이고 히든넘버 사이에는 문자 한개이상이 반드시 존재한다.

즉 최대로 꾸겨 넣으면 문자열 5백만 사이에 [숫자 * 6][문자] 의 조합이 500만 / 7 개 만큼 존재한다.

히든 넘버의 최대값은 999,999, 히든 넘버를 최대로 넣으면 714,285개가 존재한다.

이 떄의 합은 약 71.4억 ( 714,284,285,715 ) int 값의 범위를 벗어나 Overflow가 발생한다.

 

따라서 long 이나 long int 를 사용해야 한다.

 

이 두 함정을 생각해서 문제를 풀어보자.

 

알고리즘

 

1. 0 ~ n-1 인덱스까지 반복

 1-1. 현재 인덱스가 알파벳인지 판별

   1-1-1. 총 합에 현재까지 발견된 숫자 추가

   1-1-2. 현재까지 발견된 숫자 * 10 + 현재 인덱스의 숫자값 => 현재까지 발견된 숫자

 

2. 숫자를 판별하기 위한 플래그가 true 일시 총 합에 추가

 

소스코드

 

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

using namespace std;

int main()
{
	int n;
	char sentense[5000000];

	scanf("%d", &n);

	scanf("%s", sentense);

	int upper = 0;
	bool isDigit = false;
	long int sum = 0;
	for (int i = 0; i < n; i++)
	{
		if ('0' <= sentense[i] && sentense[i] <= '9')
		{
			isDigit = true;
			upper = upper * 10 + int(sentense[i] - '0');
		}
		else
		{
			if (isDigit)
			{
				isDigit = false;
				sum += upper;
				upper = 0;
			}
				
		}
	}

	if (isDigit)
		sum += upper;

	cout << sum;

	return 0;
}