[Java] 프로그래머스 2단계: 올바른 괄호

Об этом предложении

[문제 바로 가기] - 올바른 괄호 유형 : 스택 💡 아이디어 내가 생각한 올바른 괄호의 조건은 ( 와 ) 의 개수가 맞아야 함 개수뿐만 아니라 순서도 맞아야 함 예) )()( 도 개수는 맞지만 순서가 틀리다 처음 풀이에서는 개수는 세지 않았고, ( 가 나올 경우 스택에 넣고 ) 가 나올 경우 스택에서 뺐다. 이때 ) 가 나올 때 스택이 비어있으면 올바르지 않은 괄호이기 때문에 false 를 return 해주었다. 그런데 이 풀이가 효율성 테스트를 통과하지 못했다. 그럼 처음에 ( 와 ) 의 개수를 세서 불필요한 연산을 줄이면 되지 않을까 했다. 1차 풀이 : split() 사용 import java.util.*; class Solution { boolean solution(String s) { Deque<String> stack = new ArrayDeque<>(); String[] str = s.split(""); // --- 추가한 로직 --- int openCnt = 0; int closeCnt = 0; for (String t : str) { if (t.equals("(")) openCnt++; else closeCnt++; } if (openCnt != closeCnt) return false; // --- 추가한 로직 --- for (String t : str) { if (t.equals("(")) stack.push("("); else { if (!stack.isEmpty() && stack.peek().equals("(")) stack.pop(); else return false; } } return stack.isEmpty(); } } 이 코드가 효율성 테스트까지 통과했다. 문자열의 길이가 100,000 이하였기 때문에 이전 코드가 왜 시간 초과가 났을까 생각해봤다. 먼저 이 코드에서는 split() 메서드를 사용한다. 이 메서드는 문자열 s 의 길이만큼 길이 1짜리 String 객체를 새로 만들며, 인자 "" 는 정규식으로 처리되기 때문에 매 글자마다 정규식 매칭과 객체 할당이 일어난다. 따라서 시간 복잡도는 O(n)이지만 상수 비용이 커서 시간 초과가 난 것으로 판단했다. 2차 풀이 : split() 대신 charAt() 사용 class Solution { boolean solution(String s) { Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == ('(')) stack.push(1); else { if (!stack.isEmpty()) stack.pop(); else return false; } } return stack.isEmpty(); } } split() 대신 charAt() 을 사용했더니 개수를 비교하지 않아도 시간 초과가 나지 않았다. 어차피 스택에는 ( 일 경우에만 넣기 때문에 굳이 String을 넣을 필요 없다고 생각해 1을 넣었는데, 같은 맥락으로 스택을 사용하지 않고 cnt 를 둬도 될 것 같다.

Детали предложения

Провайдер

velog

Источник

velog-rss

Балл

54.39

Уверенность

49%