[프로그래머스] 숫자 문자열과 영단어

||문제 이해

숫자와 영문이 섞인 문자열을 숫자로 변경하여 리턴해라.

---

||해결 계획

pair<int , int> p라는 변수에 first는 인덱스, second는 해당 숫자를 저장할 것이다.

1번 for문에는 단어만을 검색하여 p에 저장,

2번 for문 에는 숫자만을 검색하여 p에 저장

 

그 후 인덱스(fisrt)를 기준으로 오름차순 sort 하여 순서대로 합쳐 리턴한다.

---

||계획 검증

1번 for문에는 string::find를 사용할 것이기 때문에 가장 큰 문자 길이 eight의 5를 곱했다.

find : 시간 복잡도는 찾으려는 문자 길이 * 원본 문자열 길이

단어 개수 * find = 10 * n * 5 = O(50 * n)

 

2번 for문에는 문자열 길이만큼 반복하여 저장한다 = O(n)

 

즉, O(50 * n + n) 이므로 최대 50 * 50 + 50 = 2550 번 연산으로 끝낼 수 있다.

---

||오답 원인

1. while과 find의 환장의 조합 - 1

이는 무한 루프다.

find가 계속 인덱스 0 부터 찾는 것을 막기 위해 j + 1을 했었는데 사용하지 않은 어리석은 케이스

find는 항상 인덱스 0 부터 찾을 것이다. one을 찾아도 다음에도 같이 ond을 찾을 것이다.....

이 때문에 많은 시간 소모를 했다...

 

2. while과 find의 환장의 조합 - 2

찾지 못하면 npos를 반환하는 find로 못 찾을 때까지 반복하여

반복문 내부에서 찾은 영어단어를 숫자로 변환하여 저장하려고 했다.

근데 만약 s가 "one4zerotwo"라 한다면 이 코드는 one을 저장할 수 없다.

왜냐면 처음 찾은 one이 인덱스 0을 반환한다, 이는 즉 false와 같으므로 반복문 내부에 들어가지 못하여 저장할 수 없다.

 

2. 내 착각

어찌어찌 저 for문은 넘어가고 

처음에는 문자열을 순차적으로 탐색하여 문자와 숫자 한 번에 변환하여 저장하려고 했다.

string s = "one4twozero";

for(int i = 0; i < s.size(); ++i)
{
	if(s[i] 가 문자면)
    {
    	for( 0 ~ 10 )
        {
        	if(s.find(모든 문자) != npos)
            {
            	찾으면 저장 후 break
            }
        }
    }
    if(s[i] 가 숫자면)
    {
    	숫자 - '0' 후 저장
    }
}

근데 여기서 웃긴 게 처음 탐색인 i가 0일 때 찾는 문자는 'o'이다.

그러면 이 i부터 one인지, two인지, three인지 탐색하여 맞는 것으로 저장한다.

여기서 나는 one을 변환했으니까 다음 탐색은 4겠지??라고 무의식 속에 사로잡혀있었다.

 

근데 다음 탐색은 놀랍게도 'n'이다.

그러면 n부터 탐색된 two가 나와 1 다음 2가 나오게 된 것 ㅋㅋㅋ

좀 더 자세히 생각해야겠다..

---

||구현

#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;

const string num[10] = { "zero","one","two","three","four","five","six","seven","eight","nine" };

typedef pair<int, int> pii;
vector<pii> v;

int solution(string s) {
	int answer = 0;

	//문자만 변환하는 곳
	int i, j;
	size_t t;
	for (i = 0; i < 10; ++i)
	{
		t = 0;
		do
		{
			t = s.find(num[i], t);
			if (t != string::npos)
			{
				v.push_back({ t++, i });
			}
			else break;
		} while (true);
	}
	//숫자만 변환하는 곳
	for (i = 0; i < s.size(); ++i)
	{
		//숫자가 영어보다 아스키코드가 작음
		if (s[i] <= '9')
		{
			v.push_back({ i,s[i] - '0' });
		}
	}
	sort(v.begin(), v.end());

	for (const auto & d : v)
	{
		answer = answer * 10 + d.second;
	}

	return answer;
}

---

||되돌아보기

처음에 한 번에 저장하려는 풀이가 정확하게 그려지지 않음에도 쉬워 보인다고코드를 작성하여

이것저것 시간을 많이 소모했고 find도 내가 자세히 알지 못하여 시간을 소모했다..

많은 반성을 하게 됐다..

 

이번에 풀게 될 수 있었던 핵심은 통일이다.

문자 먼저 모두 pair<인덱스(int),해당 숫자(int)>형으로 저장하고

그다음 숫자도 따로 모두 pair<인덱스(int),해당 숫자(int)>형으로 저장하여 통일했다.

 그 후에는 sort 하고 출력하면 끝!

 

다른 타입이 섞여있다면 한 번에 하려 하지 말고 하나의 타입씩 연산하는 것도 괜찮았다

---

||개선 코드

#include <bits/stdc++.h>
using namespace std;

int solution(string s) {
    s = regex_replace(s, regex("zero"), "0");
    s = regex_replace(s, regex("one"), "1");
    s = regex_replace(s, regex("two"), "2");
    s = regex_replace(s, regex("three"), "3");
    s = regex_replace(s, regex("four"), "4");
    s = regex_replace(s, regex("five"), "5");
    s = regex_replace(s, regex("six"), "6");
    s = regex_replace(s, regex("seven"), "7");
    s = regex_replace(s, regex("eight"), "8");
    s = regex_replace(s, regex("nine"), "9");    
    return stoi(s);
}

저 regex는 처음 보는데 대강 보니까 유용하게 쓸 수 있을 것 같다.

다음에 좀 공부해야겠다.