-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
found와 최종 답
20.11.11 03:56 작성 조회수 175
1
found가 괄호를 최소로 지워서 valid한 상태를 찾으려는 장치인 것을 이해했습니다.
그런데 이 강의의 예제에서,
처음 String이 길이가 8인 (a)())()일 때,
while문이 한 번 돌게 되면, queue에 길이가 7인 [a)())(), (a())(), (a)))(), (a)()(), (a)()(), (a)())), (a)())(]가 남게 되고,
두 번째 while문에서 queue의 두 번째 값('(a())()')이 poll 되어 found가 true가 되기 전까진,
queue의 첫 번째 값('a)())()')이 코드를 수행해 queue에 길이가 6인 것들이 추가되게 되는데요.
이 예제에선 길이가 6인 추가된 것들이 isValid()에 맞지 않아 res에 추가되지 않았지만,
혹시나 isValid()에 맞는 경우가 생긴다면, 최종 답에 길이가 7인 것과 6인 것이 섞일 수도 있는 건가요?
아님 제가 잘못 이해했을까요 ㅠ?
답변을 작성해보세요.
1
푸샵맨 코딩스터디
지식공유자2020.11.16
안녕하세요.
답변이 늦어서 죄송합니다.
while문이 한 번 돌게 되면, queue에 길이가 7인 [a)())(), (a())(), (a)))(), (a)()(), (a)()(), (a)())), (a)())(]가 남게 되고,
=> 맞습니다.
두번째 while문에서 queue의 두 번째 값('(a())()')이 poll 되어 found가 true가 되기 전까진,
queue의 첫 번째 값('a)())()')이 코드를 수행해 queue에 길이가 6인 것들이 추가되게 되는데요.이 예제에선 길이가 6인 추가된 것들이 isValid()에 맞지 않아 res에 추가되지 않았지만,
혹시나 isValid()에 맞는 경우가 생긴다면, 최종 답에 길이가 7인 것과 6인 것이 섞일 수도 있는 건가요?
=> queue에 전부 추가가 되고 있습니다. 문자 a를 피해서(if(str.charAt(j)!='(' && str.charAt(j)!=')') continue;)
다시문자를만들고( str.substring(0,j)+str.substring(j+1);) 이를 큐에 넣고 있습니다.
최종답은 오픈( + 클로즈 ) 가 무조건 매치가 되야합니다.
최종 답에 길이가 7인 것과 6인 것이 섞일 수도 있는 건가요?
=>여기서 길이라고 하면
문자 a를 제외하면 쌍으로 존재해야해서 6개 브레이스가 쌍으로(오픈+클로즈) 존재해야 되죠 ^^;
디버깅 천천히 걸어서 보시면 이해 되실거여여 ^^;
감사합니다~
0
답변 2