글 읽기 - PPAP 약간의 힌트 얻을수 있을까 합니다.

irnd04 5년 전 0

시간초과가 계속 납니다.

시간을 줄일 방법이 생각이 안나네요.

마지막소스 첨부합니다.

A를 기준으로 Replace입니다.

테스트케이스에 A가 많이 포함되어있는 경우가 있을까봐 a * 2 + 1 != p 조건을 주었습니다.

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] str = sc.next().toCharArray();
		int p = 0;
		int a = 0;
		
		for (int i = 0; i < str.length; i++) {
			if (str[i] == 'P') p++;
			else a++;
		}
		
		if (a * 2 + 1 != p) {
			System.out.println("NP");
			return;
		}
		
		char[] test = new char[str.length];
		int size = str.length;
		int testsize;
		boolean flag;
		while (true) {
			testsize = 0;
			flag = false;
			
			for (int i = 0; i < size; i++) {
				if (i - 2 >= 0 && i + 1 < size &&
						str[i]     == 'A' &&
						str[i - 2] == 'P' &&
						str[i - 1] == 'P' &&
						str[i + 1] == 'P') {
					i++;
					testsize -= 2;
					flag = true;
				}
				else test[testsize] = str[i];
				testsize++;
			}
			str = test;
			size = testsize;
			
			if (!flag) break;
		}
		
		if (size == 1 && str[0] == 'P')
			System.out.println("PPAP");
		else System.out.println("NP");
	}
	
}

cozyyg 5년 전 2

단순히 replace만 해서는 시간 내에 문제를 해결할 수 없습니다. 각 loop마다 replace가 한 번만 된다면 시간복잡도는 O(n^2)이 됩니다.

어떤 문자열이 PPAP 문자열이 될 동치 조건을 생각하거나, replace를 잘 한다면 문제를 해결할 수 있습니다. 자세하게 설명을 드리지는 않겠습니다. 잘 생각해 보세요.

Green55 5년 전 1

스택을 이용 하는 것도 하나의 방법입니다.

irnd04 5년 전 0

@cozyyg @Green55

풀었습니다. 감사합니다.

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

문제

문제

출처

ICPC

PPAP 약간의 힌트 얻을수 있을까 합니다.

irnd04 5년 전 0

cozyyg 5년 전 2

Green55 5년 전 1

irnd04 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말