글 읽기 - PPAP [ JAVA] O(N) 으로 푼다고 하는데, 시간초과 ㅠ

doubler 5년 전 0

문제는 PPAP 라는 문자열을 P로 압축하기 위해서

4글자씩 묶어서 "PPAP" 라는 문자열을 확인하고 이후에, 인덱스 재조정 및 문자열 갱신 형태로 하였습니다.

O(N) 의 시간복잡도로 해결한다고 하는데, 제 코드상 N 이긴 한데 내부적으로 substring() 이 부분때문에 문제가 나타나는거 같습니다.

어떻게 해결하는 것이 좋을지 여쭤봅니다.. ㅠ

import java.io.*;
import java.util.*;

public class Main {

	static InputStreamReader isr;
	static BufferedReader br;
	static OutputStreamWriter osw;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws IOException {
		isr = new InputStreamReader(System.in);
		br = new BufferedReader(isr);
		osw = new OutputStreamWriter(System.out);
		bw = new BufferedWriter(osw);

		String line = br.readLine();
		int len = line.length();
		
		for (int i = 0; i < len; i++) {
			if (i + 4 < line.length()) {
				char c1 = line.charAt(i);
				char c2 = line.charAt(i + 1);
				char c3 = line.charAt(i + 2);
				char c4 = line.charAt(i + 3);

				if (c1 == 'P' && c2 == 'P' && c3 == 'A' && c4 == 'P') {
					
					// 0 ~ i
					// i + 4 ~ len
					int s = i;
					line = line.substring(0, i) + "P" + line.substring(i+4, line.length());
					i = s - 1;
					len = line.length();
				}
			}
		}

		if(line.equals("PPAP")){
			bw.write("PPAP");
		}
		else{
			bw.write("NP");
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
}

cozyyg 5년 전 1

substring()의 시간 복잡도는 linear(substring의 길이 n에 대해 O(n))입니다. 따라서 저 방법으로는 O(n)에 문제를 해결할 수 없습니다.

PPAP 문자열이 가지게 되는 성질에 조금 더 주목하거나, 문자열 갱신을 잘 하면 문제를 해결할 수 있습니다.

doubler 5년 전 2

하.. 진짜 정말..

월요일부터 시작해서 4일만에 드디어 새벽에 풀었네요.... 4일동안 이 문제만 붙잡고 있었습니다.. ㅠ 물론 다른 것도 했지만..

답변에 해답이 있는데 항상 알고리즘은 어려운 거 같습니다.

저는 아래와 같이 정리했습니다. 푸시는 분들 참고했으면 좋겠네요.

(1) P 는 PPAP 문자열이다.

(2) PPAP 는 PPAP 문자열이다.

(3) PPAP(=P) + PAP 는 PPAP 문자열이다.

(4) P + PPAP(=P) + AP 는 PPAP 문자열이다.

(5) PPA + PPAP(=P) 는 PPAP 문자열이다.

이렇게 생각하고 저는 오랫동안 봤습니다.

저는 "P" 라는 문자열보단 "A" 라는 문자열에 주목했습니다. 일단 A 라는 문자열 앞에는 항상 P 가 2 개가 위치하고 뒤에는 P 가 항상 1개가 위치한다는 사실입니다.

그래야 PPAP 문자열을 만들 수 있거든요. 그럼 그외의 문자열은 무엇인가? 결국 P 밖에 없습니다. 자료구조는 스택을 이용했습니다.

O(n) 을 돌고 스택의 시간복잡도는 상수시간으로 O(1) 입니다. 제가 알기론.. ㅎ 그래서 해결이 되더군요.. 계속 시간초과, 컴파일에러 (급하게 내느라 문법도 안보고 냈습니다.) 만 떳는데.. 여튼 저의 아이디어는 이렇습니다.

A 를 만나기 이전까지는 스택에 계속 쌓다가 A를 만나는 시점에서는 스택에 있는 내용물이 P가 있는지 여부를 판단하는 겁니다. 그리고 P가 있는데 A 뒤에도 P가 있어야 합니다. 왜냐하면 문제는 PPAP 문자열을 찾아야 하기 때문이죠. PP + A + P = PPAP 문자열...

그렇습니다.. PPAP...

dannykim 3년 전 0

덕분에 문제 해결의 실마리를 찾을 수 있었습니다 감사합니다.

hokerz7 20일 전 0

결정적인 도움이 됐습니다!

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

문제

문제

출처

ICPC

PPAP [ JAVA] O(N) 으로 푼다고 하는데, 시간초과 ㅠ

doubler 5년 전 0

cozyyg 5년 전 1

doubler 5년 전 2

dannykim 3년 전 0

hokerz7 20일 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말