[JAVA] 백준 1013번 : Contact

 

---

 

• 코드

정답 코드 : 정규식을 통하여 정규식에 맞으면 StringBuilder에 append시켜준 뒤 반복문을 빠져나와서 출력해주었다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.valueOf(st.nextToken());
		StringBuilder sb = new StringBuilder();
		String s = "((100+1+)|(01))+";
		
		for(int i = 0; i < N; i++) {
			String temp = br.readLine();
			if(temp.matches(s))
				sb.append("YES");
			else
				sb.append("NO");
			sb.append("\n");
		}

		System.out.print(sb);
	}
}

 

다른 사람 코드 : maivve.tistory.com/208를 보고 참고하였다. 정규식을 사용하는 것보다 오토마타 전이 그래프(DFA) 를 직접 그려보는 것 + 오토마타 상태 그래프를 바탕으로 알고리즘을 짜서 코딩하는 것이 더 빠르다고 한다. 링크를 통해서 한번 익혀보면 좋을 것 같다.

 

다른 링크 : eine.tistory.com/entry/%EB%B0%B1%EC%A4%80%EC%A0%80%EC%A7%80-1013%EB%B2%88-Contact-2671%EB%B2%88-%EC%9E%A0%EC%88%98%ED%95%A8-%EC%8B%9D%EB%B3%84-%ED%92%80%EC%9D%B4

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Algorithm {
	static StringBuilder sb;

	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.valueOf(st.nextToken());
		sb = new StringBuilder();

		while (n-- > 0) {
			String jeonPa = br.readLine();

			int state = 0;
			for (int i = 0; i < jeonPa.length(); i++) {
				char num = jeonPa.charAt(i);
				state = getState(state, num);

				if (state == -1) {
					break;
				}
			}

			if (state == 0 || state == 3 || state == 6 || state == 7) {
				sb.append("YES");
			} else {
				sb.append("NO");
			}

			sb.append("\n");
		}

		System.out.print(sb.toString());
	}

	// 오토마타 상태 그래프에 맞게 출력
	static int getState(int state, char ch) {
		if (ch == '0') {
			switch (state) {
			case 0:
				return 1;
			case 2:
				return 4;
			case 3:
				return 1;
			case 4:
				return 5;
			case 5:
				return 5;
			case 6:
				return 1;
			case 7:
				return 8;
			case 8:
				return 5;
			}
		}

		if (ch == '1') {
			switch (state) {
			case 0:
				return 2;
			case 1:
				return 3;
			case 3:
				return 2;
			case 5:
				return 6;
			case 6:
				return 7;
			case 7:
				return 7;
			case 8:
				return 0;
			}
		}

		return -1;
	}
}