[백준알고리즘] 1013번: Contact -C++

[백준알고리즘] 1013번: Contact -C++

1013번: Contact (acmicpc.net)

1013번: Contact

비트열처럼 생긴 문자열에 대한 정규식을 처리하는 문제다.

실제 조건인 (100+1+ | 01)+는 정규 표현식으로도 맞는 조건이니까..

 

처음에 노가다로 풀었는데, 풀고 C++에서 정규 표현식이 가능한지 찾아보니까 있었다. 두 코드를 모두 첨부했다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

직접 확인

먼저 해당 정규식을 일일이 확인했다.

정규식을 뜯어보면 다음과 같다.

• 0 시작
  • 다음이 무조건 1
• 1 시작
  • 다음 1이 나오기 전에 2개 이상의 0 존재
  • 다음 1은 1개 이상 나와야 함

근데, 여기서 빨간색으로 칠한 조건 때문에 일일이 하기 까다로워진다.

 

 

예를 들자면, 다음과 같은 경우 때문이다. 아래의 식은 3번째 예를 뺀 나머지는 모두 YES인 조건이다.

• 10011001 = 1001 1001
• 1001101   = 10011 01
• 1001110   = 10011 10
• 100101     = 1001 01

예시를 보고 이해가 잘 안될 수 있을 것 같아 추가하자면.. 조건인 (100+1+ | 01)+ 에서 "100+1+"의 끝이 어디인지, "100+1+"이 끝나고 다음이 "01"인지 "100+1+"인지 확인하는 과정이 필요하기 때문이다.

 

 

그래서 조건을 다음과 같이 정했다. 여기서 문자열이 끝나는 범위는 고려하지 않았고, 코드에는 적용했다.

• 0 시작
  • 다음이 1인지 확인
• 1 시작
  • 다음 1까지 2칸 이상 띄워져 있어야 함
  • 다음 1로부터 다음 0을 찾음
    
    • 다음 0이 1개만 나올 경우
    • 다음 0이 2개 이상 나올 경우 (다음 0 이전에 1이 2개 이상 존재)

아래 빨간색 두 조건 중 전자는 "100+1+" 다음에 "01"이 나오는 경우라고 생각했고, 후자는 "100+1+" 다음에 또다시 "100+1+"이 나오는 경우라고 생각하고 문제를 풀었다.

 

 

문자열이 끝나는 범위라던가 다른 조건들은 코드를 통해 확인하면 될 것 같다.

#include <iostream>
#include <string>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	int test_case;
	std::cin >> test_case;
	for (int t = 0; t < test_case; t++)
		solve();
}

void solve(void)
{
	std::string bits;
	std::cin >> bits;

	int idx = 0;
	bool continue_flag = true;
	while (idx < bits.size() && continue_flag)
	{
		switch (bits[idx])
		{
		case '0':
			idx++;
			if (bits.size() <= idx || '0' == bits[idx])
				continue_flag = false;
			idx++;
			break;

		case '1':
			idx++;

			int next_1 = bits.find('1', idx);
			if (next_1 == std::string::npos || next_1 - idx < 2)
			{
				continue_flag = false;
				break;
			}

			int next_0 = bits.find('0', next_1);
			if (next_0 == bits.size() - 1)
			{
				continue_flag = false;
				break;
			}

			if (next_0 == std::string::npos)
			{
				idx = bits.size();
				break;
			}
			idx = next_0;
			if ('0' == bits[next_0 + 1] && 1 < next_0 - next_1)
				idx--;
			break;
		}
	}

	std::cout << (idx == bits.size() && continue_flag ? "YES" : "NO") << '\n';
}

 

---

 

regex

다음은 실제 정규표현식을 바로 적용한 예제다.

 

 

문제를 풀고난 뒤 C++ regex에 대해 찾아보았고, C++11부터는 <regex> 헤더가 추가되어 직접적으로 정규표현식을 사용할 수 있게 되었다고 한다. 필요한 것 이외에 좀 찾아보니 awk도 있고 replace하는 기능 등 다양한게 있는 것 같으니 필요할 때 찾아서 써야겠다.

 

 

아무튼, 해당 헤더를 가져다가 정규식을 바로 적용하면 문제를 쉽게 풀 수 있다. regex 객체로 정규식 패턴을 넣어 생성해주고, regex_match라는 함수를 사용해 입력된 문자열이 정규식 패턴과 일치하는지 바로 확인할 수 있다.

 

 

참고로 위에 일일이 구한 코드가 30KB 정도 메모리를 더 사용했지만, regex를 사용한 경우가 4ms 더 많이 나왔다.

 

 

아래는 C++ regex를 사용한 예제다.

#include <iostream>
#include <string>
#include <regex>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	int test_case;
	std::cin >> test_case;
	for (int t = 0; t < test_case; t++)
		solve();
}

void solve(void)
{
	std::string bits;
	std::cin >> bits;

	std::regex pattern("(100+1+|01)+");
	std::cout << (std::regex_match(bits, pattern) ? "YES\n" : "NO\n");
}