🔗 Full Problem 1013

"If humanity were the only thing that existed in this infinitely vast universe, wouldn't that be truly sad?"

The Arecibo radio telescope, located in Arecibo, Puerto Rico, has spent decades gazing at the night sky in an attempt to receive radio waves from an alien civilization that may not even exist.

Efforts to find patterns in the radio waves collected by this telescope that could not naturally occur, and to use them as evidence for the existence of extraterrestrial civilizations, have continued unabated, but no such pattern has been discovered yet. Dr. Kim Dong-hyeok, the pride of Korean astronomy, adopted the following radio wave notation as a standard in order to carry out this kind of search using domestic technology.

The basic units of a radio wave consist of the two symbols $\{ 0 , 1 \}$, and $x+ ( )$ represents the set of radio waves formed by repeating $x$ an arbitrary number of times (at least 1).

$(xyx)+ ( )$ represents the set of radio waves formed by repeating $xyx$ within the parentheses. Below are examples to help with understanding.

• 1+ = { 1, 11, 111, 1111, 11111, … }
• 10+ = { 10, 100, 1000, 10000, 100000, … }
• (01)+ = { 01, 0101, 010101, 01010101, 0101010101, … }
• (1001)+ = { 1001, 10011001, 100110011001, … }
• 10+11 = { 1011, 10011, 100011, 1000011, 10000011, … }
• (10+1)+ = { 101, 1001, 10001, 1011001, 1001101, 100011011000001, … }

In addition to +, which means repetition, there is also the symbol $|$, which means "or". $\{ x | y \}$ means either $x$ or $y$, so $\{ 0+ | 1+ \}$ means the set $\{ 0 , 1 , 00 , 11 , 000 , 111 , \dotsm \}$. Below is an example that combines both symbols.

• (100+1+ | 01)+

Recently, Dr. Kim Dong-hyeok examined a portion of the radio wave records received from star Vega at the Arecibo radio telescope, analyzed the pattern of those radio waves, and recorded it as follows.

• (100+1+ | 01)+

Dr. Kim Dong-hyeok needs a program that can pick out, from among various radio wave records, the ones that match the pattern above. Write a program that can do this.

The first line of input gives the number of test cases $T$. Then, for each test case, a string consisting only of $\{ 0, 1 \}$ representing a radio wave is given with no spaces. The string length is in the range $(1 ≤ N ≤ 200)$.

For each test case, print "YES" if the given radio wave matches the pattern presented in the problem, and "NO" otherwise. The output strings consist entirely of uppercase letters.

• Input

TC
3
10010111
011000100110001
0110001011001

• Output

TC
NO
NO
YES

If you have even a rough knowledge of regular expressions, it's hard to understand why this is rated GOLD V. What makes regular expressions difficult is designing a regex to match a desired pattern, but this problem hands you the regex outright. It's essentially a question of whether or not you understand the concept of regular expressions.

In my case, I had dealt with them a few times at work when the need occasionally arose, so they weren't too unfamiliar. You can design and test regular expressions at regexr, so check it out — it's a well-known site for regex work.

Since the problem hands you the regex $(100+1+ | 01)+$ directly, all you need to do is take the input string and check whether it matches the regex.

In JAVA, you use it like Pattern.matches({regex string}, {string});, which returns whether it matches as a boolean.

As you can see from the source below, it's really simple. For anyone who knows regular expressions, this is a BRONZE-level problem.

JAVA
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.regex.Pattern;

/**
 * 백준 전체 1013 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/13/a1013">1013 풀이</a>
 * @since 2021.06.13 Sun 04:34:19
 */
public class Main
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		// 케이스 수
		int T = Integer.parseInt(reader.readLine());
		
		for (int i = 0; i < T; i++)
		{
			String text = reader.readLine();
			
			// 정규식 일치 여부
			String result = Pattern.matches("(100+1+|01)+", text) ? "YES" : "NO";
			
			System.out.println(result);
		}
		
		reader.close();
	}
}

• Strings
• Regular Expressions

Since the problem turned out easier than expected, I thought "surely it's not really supposed to be solved this way?" and looked into it — and sure enough, a different approach had been shared elsewhere. That approach uses a DFA (deterministic finite automaton transition graph) instead of a regular expression. This is worth trying as an alternative in languages that don't officially support regular expressions. On Baekjoon, you presumably can't use external libraries anyway.