https://school.programmers.co.kr/learn/courses/30/lessons/12909
Stack 써서 올바른 괄호 찾는 문제인데
기본적으로 파라미터가 String 하나만 넘어와서 적합성 검증하는거잖아
그런데 파라미터 응용해서
boolean solution(String[] string1, String[] string2) {
...
}
이것처럼 2개의 배열로 넘어오고 각각 배열에는 '(' 또는 ')' 로만 이루어진 문자열로만 이루어져있을 때
각각 배열의 요소들을 합했을 때 올바른 괄호가 나오는 경우 카운팅 하는 문제일 경우에
파라미터 배열의 길이 범위가 1 <= string1, string2.length <= 100,000 일 경우에 복잡도 O(n^2) 보다 낮게 푸는 방법좀 알려주셈
import java.util.*;public class Solution { public static boolean solution(String[] string1, String[] string2) { // 균형 정보를 저장할 리스트 List<int[]> balances1 = new ArrayList<>(); List<int[]> balances2 = new ArrayList<>(); // 각 배열에 대해 (최종 균형, 최소 균형) 계산 calculateBalances(string1, balances1); calculateBalances(string2, balances2); // 균형 정보를 저장
두개 들어온다고 n^2이 되는 이유가 뭐임??
아그러네 nm이네
답은 뜨는데 효율성 검사에서 시간 초과뜨길래... 배열 요소값을 한번 가공해서 돌려야되나
내가 드립을 잘못 이해하고 있는건가 싶어서 간단하게 해봄
https://ideone.com/t1wEKM
해당 댓글은 삭제되었습니다.
단순 갯수만 카운트해서는 )()()( 이런 괄호도 올바르다고 판단해서 안됨
그러네 ㅋㅋ; 이건 좀 해봐야겠는데
링크 달아둔 기본 문제는 스택쓰면 간단하게 풀리긴하는데 파라미터 응용된게 문제..