doubler   2년 전

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

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

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

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

cozyyg   2년 전

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

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

doubler   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   2달 전

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

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