오늘의 학습 키워드
- 올바른 괄호
공부한 내용 본인의 언어로 정리하기
import java.util.*;
class Solution {
boolean solution(String s) {
char[] arr = s.toCharArray();
List<Character> right = new ArrayList<>();
List<Character> left = new ArrayList<>();
if ((s.length() % 2) != 0) {
return false;
}
for (char c : arr) {
if (c == '(') {
right.add(c);
} else if (c == ')') {
left.add(c);
}
if (left.size() > right.size()) {
return false;
}
}
return right.size() == left.size();
}
}오늘의 회고
오늘 문제는 열리는 괄호가 짝지어져서 ( 로 열렸으면 ) 문자로 닫혀야 true가 아니라면 false가 반환되야하는 문제이다.
처음에는 무조건 첫글자는 (, 마지막 글자는 ) 으로 되어 있어야 한다는 생각에
if (s.startsWith("(") && s.endsWith(")")) {로 시작을 했었다.
그리고 앞서 나온 문제들과 같이 배열로 만들고 짝이 지어지려면 짝수인지 확인해야 했기때문에 String s의 길이의 반으로 나누었을때 나머지가 0 이면 진행이 되게 시작을 했다.
그리고 p와 y의 갯수를 구했던 문제처럼 각 문자의 배열을 만들어 사이즈를 비교했고
크기가 같다면 true 값을 반환하게 만들었다. 하지만 여러가지 오류가 많았고 처음부터 코드를 짜기 시작했다.
처음에 열림과 닫힘에 대해 경우를 주고 시작한다고 하더라도 ( 과 )의 갯수가 같은 경우에 실패가 나올 수 있다는 걸 깨달았다. 예를들어 ())(() 이런 경우는false가 나와야 하지만 true가 나와서 실패한다는 걸 알았고 차라리 다른 방법을 이용해서 풀기로 했다.
그래서 나온 비교하는 코드가 이것이었다
if (left.size() != right.size()) {
return false;
}하지만 결과가 계속 실패로 떴는데 안된 이유는 for문이 돌아갈때마다 옳은지 아닌지 계속 반환을 했기때문에 시작부터 false가 나왔기 때문이다. 그래서 경우의 수를 확실히 할 수 있는 것으로 고쳤고 아래 코드가 고친 코드이다.
if (left.size() > right.size()) {
return false;
} 이렇게 되면 열리는 괄호보다 닫히는 괄호가 많아지는 경우에는 절대 true가 성립될 수 없게 되는것이다. 예를 들자면 ())(()() 같이 열린 괄호보다 닫히는 괄호가 많아지게 되면 짝이 절대 성립이 될수 없기 때문이다. 닫히는 괄호가 뒤쪽으로 간다고 해도 반복문에 의해 판단이 되기때문에 절대 성립 될수가 없다. ((())()) 같은 경우도 안된다는 것을 볼 수 있다.
오늘 페어 프로그래밍을 하면서 여러 사람들의 코드를 봤는데 나처럼 배열로 푼 사람들도 있었던 반면 문제의 유형인 "스택/큐"에 맞춰서 Stack을 이용해서 푼사람도 굉장히 많았다.
정석적으로 Stack으로 완성한 사람도 있었고 if문 대신 switch-case문을 이용해서 ( 일때와 )일때 각각 stack으로 추가하고 제거하고 해서 isEmpty()인 경우에 반환되는 값을 출력하게 했다.
AI 코드리뷰
코드 리뷰:
문제 해결 접근 방식은 올바릅니다. 괄호의 균형을 확인하는 기본적인 로직을 구현했습니다.
문자열의 길이가 홀수인 경우를 먼저 체크하는 것은 좋은 최적화입니다.
ArrayList를 사용하여 괄호를 저장하는 것은 불필요한 메모리 사용을 초래합니다.
왼쪽 괄호의 개수가 오른쪽 괄호의 개수보다 많은 경우를 체크하는 것은 좋습니다.
시간 복잡도:
현재 코드의 시간 복잡도는 O(n)입니다. 여기서 n은 입력 문자열의 길이입니다.
효율성 개선:
다음과 같이 코드를 개선할 수 있습니다:
ArrayList 대신 단순 카운터를 사용합니다.
문자열을 toCharArray()로 변환하지 않고 직접 순회합니다.
불필요한 조건 검사를 줄입니다.
개선된 코드 제안
class Solution {
boolean solution(String s) {
if (s.length() % 2 != 0) {
return false;
}
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
count++;
} else if (s.charAt(i) == ')') {
if (count == 0) {
return false;
}
count--;
}
}
return count == 0;
}
}개선된 버전의 장점:
ArrayList 대신 count 변수를 사용하여 메모리 사용량을 줄였습니다.
toCharArray()를 사용하지 않고 charAt()으로 직접 문자에 접근하여 추가 메모리 할당을 피했습니다.
왼쪽 괄호를 만나면 count를 증가시키고, 오른쪽 괄호를 만나면 감소시킵니다.
오른쪽 괄호를 만났을 때 count가 0 이면 바로 false를 반환합니다. 이는 )(와 같은 경우를 처리합니다.
최종적으로 count가 0 인지 확인하여 모든 괄호가 올바르게 닫혔는지 확인합니다.
이 개선된 버전은 여전히 O(n) 시간 복잡도를 가지지만, 메모리 사용량이 크게 줄어들었고 불필요한 연산을 제거하여 더 효율적입니다.
오늘 보았던 Stack을 이용한 방법과 Queue를 이용한 방법도 AI를 이용해 추가하겠다
Stack을 이용한 방법
import java.util.Stack;
class Solution {
boolean solution(String s) {
// 문자열 길이가 홀수인 경우, 괄호의 균형이 맞을 수 없으므로 false 반환
if (s.length() % 2 != 0) {
return false;
}
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(') {
// 왼쪽 괄호를 만나면 스택에 push
stack.push(c);
} else if (c == ')') {
if (stack.isEmpty()) { // 스택이 비어있는데 오른쪽 괄호를 만나면 false 반환
// 이는 닫는 괄호가 여는 괄호보다 먼저 나온 경우
return false;
}
// 오른쪽 괄호를 만나면 스택에서 pop (왼쪽 괄호 제거)
stack.pop();
}
}
// 모든 문자를 처리한 후 스택이 비어있으면 true, 그렇지 않으면 false 반환
return stack.isEmpty(); // 스택이 비어있다는 것은 모든 괄호의 짝이 맞았다는 의미
}
}Queue를 이용한 방법
import java.util.LinkedList;
import java.util.Queue;
class Solution {
boolean solution(String s) {
// 문자열 길이가 홀수인 경우, 괄호의 균형이 맞을 수 없으므로 false 반환
if (s.length() % 2 != 0) {
return false;
}
Queue<Character> queue = new LinkedList<>();
int openCount = 0; // 왼쪽 괄호의 개수를 세는 변수
// 모든 문자를 큐에 넣음
for (char c : s.toCharArray()) {
queue.offer(c);
}
while (!queue.isEmpty()) {
char c = queue.poll(); // 큐에서 문자를 하나씩 꺼냄
if (c == '(') { // 왼쪽 괄호를 만나면 openCount 증가
openCount++;
} else if (c == ')') {
if (openCount == 0) { // openCount가 0인데 오른쪽 괄호를 만나면 false 반환
// 이는 닫는 괄호가 여는 괄호보다 많은 경우
return false;
}
// 오른쪽 괄호를 만나면 openCount 감소
openCount--;
}
}
// 모든 문자를 처리한 후 openCount가 0이면 true, 그렇지 않으면 false 반환
return openCount == 0; // openCount가 0이라는 것은 모든 괄호의 짝이 맞았다는 의미
}
}내일 공부할 것 :
오늘도 더 효율적이고 현대적인 방법을 몰라서 정확성과 효율성부분 모두에서 해매고 있었던 것 같다. 근 시일 내에 Stack과 Queue의 사용법과 장,단점에 대해서 정리하고 기록해야 겠다.
문제
https://school.programmers.co.kr/learn/courses/30/lessons/12909
