• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

질문있습니다.

21.01.27 19:20 작성 조회수 131

3

강의에서 start= left+1, end = right-left-1 을 해주고

결과값 리턴시 s.substring(start, start+end)을 해주고있습니다.

궁금한것이 start+end를 하는것이 결국 left+1 + right-left-1 인걸로 생각되서 저는 end에 right만 해주고 결과값에 s.substring(start, end)를 하여 테스트를 해봤는데 동일하게나옵니다.

여러가지 테스트를 했는데 똑같이 나와서 맞구나 생각되는데

프로그래머스의 가장긴팰린드롬이라는 문제를 적용해서 해보았는데... 알려주신 방법으로는 통과가 되는데 제가 수정한 방법은 특정 문제에 실패가 나옵니다.. 아무리 제가 테스트 케이스를 작성해서 넣어봐도 똑같은거 같은데.. 제가 수정한 방식의 접근 방법이 어디가 잘못된건지 여쭤봅니다.

감사합니다.

```java

public class inflearn_string_04 {
	
	
	public static void main(String[] args) {
		String[] ss = new String[] {"a","qwertytrss","tt","fff","asdfds","abcde","abcabcdcbae"};
		
		for(String s: ss) {
		
			solve(s);
		}
	}
	
	
	private static int start, end, end2;
	
	public static void findSubString(String s, int left, int right) {
		
		while(left >= 0 && right <= s.length()-1 && s.charAt(left) == s.charAt(right)) {
			//System.out.println(left+","+right+","+s.substring(left,right+1));
			left --;
			right ++;
		}
		
		
		if(end2 < right-left-1) {
			end2 = right;
		}
		
		if(end < right-left-1) {
			start = left+1;
			end = right-left-1;
		}
		
	}
	
	public static String solve(String s) {
		start = 0;
		end = 0;
		end2 = 0;
		boolean chk = false;
		int len = s.length();
		if(len < 2) return s;
		
		for(int i=0; i< len-1; i++) {
			findSubString(s,i,i);
			findSubString(s,i,i+1);
			
		}
		
		
		if((s.substring(start,start+end).equals(s.substring(start,end2)))) {
			chk = true;
		}
		
		System.out.println( chk+"||"+s.substring(start,start+end)+"=="+s.substring(start,end2));
		
		
		return s.substring(start,start+end);
//		return s.substring(start,end);
	}
}
```

답변 4

·

답변을 작성해보세요.

1

장정현님의 프로필

장정현

2021.06.09

리트코드 
https://leetcode.com/problems/longest-palindromic-substring

동일한 문제에서 입력값이 "cbbd" 일때 "c" 가 나오면서 실패하는데.. 현재값을 기준으로 좌우를 비교해서 해당 케이스를 통과를 못하는것 같습니다(뇌피셜).. 어떻게 해야 통과가 될까요..?

1

유민선님의 프로필

유민선

질문자

2021.01.28

예제를 보니 이해가 되었습니다:)

end라는 것이 결국 가장긴 팰린드롬의 길이라고 보면되고 start가 시작의 포인터라고 보면되는군요.

if (end2 < right - left - 1) { -> if (end2-start < right - left - 1) {

이해하고 나니 위에처럼 바꾸면  동일한 처리를 하게되었어요!!

감사합니다 :) 

1

안녕하세요.

이 문제는 substring()에 본질을 이해해야는 문제죠. 

결론은  연속되는 palindrom이 존재하다가 end포인트가 달라지는 경우입니다. 

예제를 먼저 올려드리고, 글로쓰면 오래 걸려서 그림은 나중에 올릴게요. 

먼저 예제를 돌려보세요.

package zTest03;

public class Pal {

public static void main(String[] args) {

String[] ss = new String[] {

"jgnendsknkso" };

for (String s : ss) {

solve(s);

}

}

public static String solve(String s) {

start = 0;

end = 0;

end2 = 0;

boolean chk = false;

int len = s.length();

System.out.println("len "+len);

if (len < 2)

return s;

for (int i = 0; i < len - 1; i++) {

findSubString(s, i, i);

findSubString(s, i, i + 1);

}

System.out.println("start " + start + " end "+end+ " start+end " + (start + end));

System.out.println("start " + start + " end2 " + end2);

System.out.println("11 " + s.substring(start, start + end));

System.out.println("22 " + s.substring(start, end2));

if ((s.substring(start, start + end).equals(s.substring(start, end2)))) {

chk = true;

}

System.out.println(chk + "||" + s.substring(start, start + end) + "==" + s.substring(start, end2));

return s.substring(start, start + end);

// return s.substring(start,end);

}

private static int start, end, end2;

public static void findSubString(String s, int left, int right) {

while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {

//System.out.println(left+","+right+","+s.substring(left,right+1));

left--;

right++;

}

System.out.println("left " + left + " right " + right);

if (end2 < right - left - 1) {

end2 = right;

System.out.println("end2   "+end2+" ========================= right " + right);

}

if (end < right - left - 1) {

start = left + 1;

end = right - left - 1;

System.out.println("end   "+end+"   ============================= right " + right);

}

}

}

0

장정현님 ~ 안녕하세요.

이 문제는 업데이트를해서 문제분석, 코딩으로  강좌가 나눠져 있습니다.

최신 소스는 제 github에도 올라가 있습니다.

질문주신내용 :

동일한 문제에서 입력값이 "cbbd" 일때 "c" 가 나오면서 실패하는데.. 현재값을 기준으로 좌우를 비교해서 해당 케이스를 통과를 못하는것 같습니다(뇌피셜).. 어떻게 해야 통과가 될까요..?

답변:

=> 제가 올린 소스로는 cbbd에 대해서 bb값을 잘 받고 있습니다.

다시 강의와 소스를 해보시고 안되면 바로 질문 주세요~

감사합니다~

해피코딩하세요~