글 읽기 - 반례 부탁드립니다.

lck0722 1년 전 0

다른 질문들 확인하면서 반례들 입력값으로 넣어 봤는데 전부 정답이 나왔습니다.

문제를 해결하고 싶어도 어느 부분에 문제가 있는 지 알 수가 없어서 곤란하네요...

조건 확인하는 중에 배열의 범위를 넘어가는 탐색을 하는 경우가 있어서 예외 처리를 해둔 것이 문제인가 싶기도 한데,

현재 index값 보다 큰 값을 확인하기 전에는 다 남아있는 배열의 최소 길이를 확인하고 넘어가기 때문에 문제가 없는 것 같다고 생각합니다.

반례 찾아주시면 감사드리겠습니다. ㅠ

해결했습니다. 1000 같이 100+ 패턴 뒤에 1이 안 따라오는 경우를 생각 못했었네요.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		
		for (int i = 0; i < T; i++) {
			StringBuilder sb = new StringBuilder();
			sb.append(scan.next());
			List<Integer> numList = new ArrayList<>();
			
			for (int j = 0; j < sb.length(); j++) {
				numList.add(Character.getNumericValue(sb.charAt(j)));
			}
			
			if (check(numList)) {
				System.out.println("YES");
			}
			else {
				System.out.println("NO");
			}
		};
		
		scan.close();
	}
	
	public static boolean check(List<Integer> list) {
		int index = 0;
		
		try {
			while (index < list.size()) {
				// 0으로 시작하는 경우
				if (list.get(index) == 0) {
					// 01 조건 만족하기 위한 최소 길이 체크
					if(list.size() - index < 2) {
						return false;
					}
					
					if (list.get(index+1) == 1) {
						index += 2;
					}
					else {
						return false;
					}
				}
				// 1로 시작하는 경우
				else {
					// 100+1+ 조건 만족하기 위한 최소 길이 체크
					if(list.size() - index < 4) {
						return false;
					}
					// 100 인지 확인
					if (list.get(index+1) == 0 && list.get(index+2) == 0) {
						index += 3;
						// 0+
						while (list.get(index) == 0) {
							index++;
						}
						// 1+
						while (list.get(index) == 1) {
							index++;
						}
						// 10011001 같은 형태 확인을 위한 절차
						if (list.get(index-1) == 1 && list.get(index-2) == 1) {
							List<Integer> l = new ArrayList<Integer>();
							// 배열 분할
							l.addAll(list.subList(index-1, list.size()));
							// 분할한 배열을 인자로 전달하여 체크
							if (check(l)) {
								return true;
							}
						}
					}
					else {
						return false;
					}
				}
			}
		}
		// 배열의 범위를 넘어서는 예외 처리
		catch (IndexOutOfBoundsException e) {
			return true;
		}

		return true;
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 부탁드립니다.

lck0722 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말