[Java] 백준 1013번 [Contact] 자바

: ) YOUNG·2022년 4월 10일
3

알고리즘

목록 보기
89/417
post-thumbnail

백준 1013번
https://www.acmicpc.net/problem/1013


문제

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

  • (100 | 11)+ = { 100 , 11 , 10011 , 11100 , 1110011100 , 100111111100100, … }

  • (100+1+ | 01)+

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


입력

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


출력

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


예제 입력 1

3
10010111
011000100110001
0110001011001

예제 출력 1

NO
NO
YES

생각하기

이 문제는 정규표현식의 개념을 다루는 문제이다.

난 정규표현식에 대해서 잘 몰라서 쓸때마다 검색하면서 풀었는데,
이문제가 얼마나 쉽나 함은..

그냥 문제에서 제시한 "(100+1+ | 01)+" 패턴을 그대로 넣기만 하면 정답이 출력된다.

골드 문제여서 엄청 어려울 줄 알았는데, 정규표현식 자체가 좀 까다롭다는 점 때문에 티어가 높은게 아닐까 싶다.

동작

정규표현식으로 만든 패턴과 문자열을 비교하기 위해서는 regex.Pattern을 사용해야 합니다.

Pattern P = Pattern.compile("(100+1+|01)+"); 릍 통해
미리 우리가 사용할 pattern을 상수로 compile 한 뒤

matcher의 matches함수를 활용해 비교해서 boolean값으로 판별합니다.



TMI

1. 안타깝지만 아레시보 천문대는 2020년에 붕괴되어서 은퇴를 하게 되었다.

2. 영화 콘택트에서 주인공이 외계신호를 연구하다 쫓겨난 곳이 아레시보 전파만원경이었다. 그래서 이 문제의 제목이 contact이다. (첫 줄은 명대사)




코드


import java.util.regex.Pattern;
import java.io.*;

public class Main {
	private static final Pattern P = Pattern.compile("(100+1+|01)+");

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		while(T-- > 0) {

            if (P.matcher(br.readLine()).matches()) {
                sb.append("YES").append('\n');
            } else {
                sb.append("NO").append('\n');
            }
		}
		
		System.out.println(sb);

	} // End of main
} // End of class 

0개의 댓글