[코테연습] 올바른 괄호 () 만들기

문제

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항
문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
입출력 예
s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

 

 

나의  첫 풀이

- '(' 와 ')' 의 갯수를 카운팅하자!! 0이 되면 알맞은 사용일거야!

  -> 결과적으로 실패

[첫번째 시도 코드]

String s = "(((()))";
int cnt = 0;
s.lines.forEach(it -> {
    if (it.equals("(")) {
        cnt++;
    } else if (it.equals(")")) {
        cnt--;
    }
});

 

[실패 원인]

1. lines - 문자열의 줄 바꿈 갯수를 읽어들이는 메서드로(equals가 될리가 만무), 내가 의도했던 문자 한개당 읽어 들이는 것은
   1. chars를 사용해야한다. (stream)
   2. toCharsArray() (for문)
2. int 증감 불가 - lambda 안에서의 지역변수(cnt)는 무조건 final이거나 effectively final으로 실질적 final이어야 한다. 증감을 다르게 구현할 수 있는데
   1. lambda 대신 for문에서 toCharArray()로 순회 하면 int cnt의 증감 가능
   2. int가 아닌 AutomicInteger로 getAndIncrement(), getAndDecrement()로 증감 가능

---

나의  두번째 풀이

- 증감을 열심히 맞췄지만,, 뚜둥 함정이다!

  -> 결과적으로 실패

입력값 〉	")()("
기댓값 〉	false
실행 결과 〉	실행한 결괏값 true이 기댓값 false과 다릅니다.

[두번째 시도 코드]

int cnt = 0;
for (char it: s.toCharArray()) {
    if (it == '(') {
        cnt++;
    } else if(it ==')') {
        cnt--;
    }
}
return cnt == 0 ? true : false;

---

나의  세번째 풀이

- 증감도 맞아야 하고, ')'가 '(' 보다 많아지는 순간이 오면 안된다. 즉 int가 음수가 되면 안됨.

   - int 방식으로 풀어도 되고, 뭔가 스택을 이용해 보고싶기도 하다.

   - int, AutomicInteger, Stack, stream.reduce() 4가지 방식으로 확인 해보자 

 

[int]

int cnt = 0;
for (char c : s.toCharArray()) {
    if (c == '(') {
        cnt++;
    } else if (c == ')') {
        cnt--;
        if (cnt < 0) {
            return false;
        }
    }
}
return cnt == 0;

 

 

[AutomicInteger]

AtomicInteger cnt = new AtomicInteger(0);
s.chars().forEach(ch -> {
    if (ch == '(') {
        cnt.getAndIncrement();
    } else if (ch == ')') {
        cnt.getAndDecrement();
    }
});

 

 

[Stack]

Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
    if (c == '(') {
        stack.push(c); // 여는 괄호를 스택에 넣음
    } else if (c == ')') {
        if (stack.isEmpty()) {
            // 스택이 비어있으면 닫는 괄호가 많다는 뜻
            return false;
        }
        stack.pop(); // 짝을 맞춘 여는 괄호를 제거
    }
}
return stack.isEmpty();

 

[stream.reduce()]

int cnt = s.chars()
        .map(ch -> ch == '(' ? 1 : (ch == ')' ? -1 : 0))
        .reduce(0, Integer::sum);

 

---

선택의 이유와 근거

 1. int와 AutomicInteger는 어떤 차이가 있을까?

 - AutomiaInteger를 보면 get하여 접근하고 있는 것을 볼 수 있다. 이는 스레드 세이프한 연산이 가능하다.
 여러 스레드가 동시에 읽기 쓰기를 해도 동시성 문제가 발생하지 않는다. 대신 이 부분 때문에 int 연산보다는 퍼포먼스가 떨어질수 있으므로 단일 스레드여도 무관하다면 int가 유리하다.

 - int 는 반대로 멀티스레드 환경에서는 경쟁 상태(race condition)가 발생할 수 있다.

2. stack과 카운팅 방식엔 어떤 차이가 있을까?

 - '(' 와 ')' 만 사용할때는 카운팅 방식이 유리해 보인다.

•  공간복잡도, 시간 복잡도
  • 카운팅 방식은 연산을 통해 숫자를 기억하지만, Stack은 100개의 '('가 들어온다면 100개를 담고 있을 것이다.
    메모리 측면에서 카운팅 방식이 단일 정수 변수로 0(1) 메모리 사용인 것에 비해 효율이 좋지 못하고,
    이것은 곧 데이터 구조 관리와 속도로 이어진다.

	스택방식	카운팅 방식
적용 대상	유효 괄호, 순서 O, 비정상 구조 [{ 등 검출 가능	유효 괄호, 순서 X, 비정상 구조 검출 불가능
성능	0(n)시간  / 0(n) 공간	0(n) 시간, 0(1) 공간
메모리 사용	여는 괄호 숫자에 따라 메모리 사용 (O(n)) 증가	(O(1)) 로 적음