Contact

---

🔗 🔗 전체 1013번 문제

조건

---

문제

---

푸에르토리코 아레시보에 위치한 아레시보 전파망원경(Arecibo radio telescope)은 수십 년째 존재하지 않을 지도 모르는 외계 문명으로부터의 전파를 수신하기 위해 밤하늘을 바라보고 있다.

이 망원경이 수집한 전파 속에서 자연적으로 발생하기 힘든 패턴들을 찾아내어, 그것을 증거로 외계 문명의 존재 여부를 가리려는 노력은 줄곧 이어져왔지만 아직까지도 그러한 패턴은 발견되지 않았다. 한국 천문학계의 자존심 김동혁 박사는 국내 기술로 이러한 탐사를 진행하기 위하여 다음의 전파 표기를 표준으로 삼았다.

전파의 기본 단위는 $\{ 0 , 1 \}$ 두 가지로 구성되어있으며, $x+ ( )$ 는 임의의 개수(최소 1개) $x$의 반복으로 이루어진 전파의 집합을 나타낸다.

$(xyx)+ ( )$ 는 괄호 내의 $xyx$의 반복으로 이루어진 전파의 집합을 뜻한다. 아래는 이해를 돕기 위한 예제이다.

• 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, … }

반복을 의미하는 + 외에도 or 를 의미하는 $|$ 기호가 있다. $\{ x | y \}$ 는 $x$ 혹은 $y$를 의미하는 것으로, $\{ 0+ | 1+ \}$ 는 $\{ 0 , 1 , 00 , 11 , 000 , 111 , \dotsm \}$ 의 집합을 의미한다. 아래는 두 기호를 복합적으로 사용한 예이다.

• (100+1+ | 01)+

최근 김동혁 박사는 아레시보 전파망원경에서 star Vega(직녀성) 으로부터 수신한 전파 기록의 일부를 조사하여 그 전파들의 패턴을 분석하여 아래와 같이 기록하였다.

• (100+1+ | 01)+

김동혁 박사는 다양한 전파 기록 중에서 위의 패턴을 지니는 전파를 가려내는 프로그램을 필요로 한다. 이를 수행할 수 있는 프로그램을 작성하라.

입력

---

입력의 첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, $\{ 0, 1 \}$만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 $(1 ≤ N ≤ 200)$의 범위를 갖는다.

출력

---

각 테스트 케이스에 대해 주어진 전파가 문제에서 제시한 패턴이면 “YES”를 그렇지 않은 경우는 “NO”를 출력한다. 출력 문자열은 모두 대문자로 구성되어 있다.

케이스

---

예제 1

---

• 입력

TC
1
2
3
4
3
10010111
011000100110001
0110001011001

• 출력

TC
1
2
3
NO
NO
YES

풀이

---

정규식을 대강 알고있다면 이게 왜 GOLD V인지 다소 이해되지 않는 수준의 문제다. 정규식이 어려운 이유는 원하는 패턴에 맞춰 정규식을 설계하는 건데, 그 정규식을 대놓고 준다. 사실상 정규식의 개념을 아냐 모르느냐를 물어보는 문제.

나의 경우, 일하다가 간간히 쓸 일이 생겨서 몇 번 다뤄본적이 있어 그리 생소하지 않았다. 🔗 regexr에서 정규식을 설계하고 테스트를 할 수 있으니 참고하자. 정규식 관련해서는 유명한 사이트.

문제에 대놓고 $(100+1+ | 01)+$라는 정규식 자체를 제공하기 때문에, 그냥 문자열 받아서 정규식과 일치하는지 보면 된다.

JAVA에서는 Pattern.matches({정규식 문자열}, {문자열});과 같이 사용하며, 일치여부를 boolean으로 반환한다.

아래 소스를 보면 알겠지만 진짜 간단하다. 정규식을 아는 사람에겐 BRONZE 수준의 문제.

전체 소스

---

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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();
	}
}

분류

---

• 문자열
• 정규 표현식

여담

---

문제가 생각보다 쉬워서, "사실 이렇게 하면 안 되는게 아닐까?"하고 찾아보니 역시나 다른 방식으로 접근하는 방법이 공유되어 있었다. 정규표현식이 아닌 DFA(오토마타 전이 그래프)를 활용하는 방식이다. 정규표현식을 공식적으로 지원해주지 않는 언어라면 대체제로 시도해봄직하다. 백준에선 외부 라이브러리를 사용할 수 없을테니.