codility) Nesting

코딜리티 - Nesting

자료구조에서 Stack을 공부한 뒤, 코딜리티 Lesson 7의 Nesting 문제를 풀어보았다.

이번 문제는 25분 정도 걸려서 풀이를 완료했다.
처음 제출했을 때는 87점이 나왔고, 이후 문제 조건을 다시 확인하면서 빈 문자열 케이스를 수정해 100점을 받을 수 있었다.

---

문제 유형

항목내용

플랫폼	Codility
문제	Nesting
유형	Stack
핵심 개념	괄호 중첩 검사
사용 언어	Java
풀이 시간	약 25분
첫 제출 결과	87점
최종 결과	100점

---

문제 이해

문제는 문자열 S가 올바르게 중첩된 괄호 문자열인지 확인하는 것이다.

문자열 S는 다음 문자로만 이루어진다.

'(' 또는 ')'

올바른 중첩 문자열이면 1, 아니면 0을 반환해야 한다.

예를 들어:

입력결과이유

"(()(())())"	1	모든 괄호의 짝이 맞음
"())"	0	닫는 괄호가 하나 더 많음
"("	0	여는 괄호가 닫히지 않음
")"	0	닫는 괄호가 먼저 나옴
""	1	문제 정의상 빈 문자열도 properly nested

---

문제에서 중요했던 정의

처음에 놓쳤던 부분은 바로 이 조건이었다.

S is empty;

Codility 문제 설명에서는 properly nested string의 조건 중 하나로
S가 비어 있는 경우도 올바른 중첩 문자열이라고 정의하고 있다.

즉, 빈 문자열 ""은 괄호가 없지만, 잘못 닫힌 괄호도 없기 때문에 1을 반환해야 한다.

나는 처음에 길이가 2보다 작으면 무조건 올바르지 않다고 생각해서 이 케이스를 놓쳤다.

---

풀이 아이디어

이 문제는 Stack을 사용해서 풀 수 있다.

괄호 검사 문제에서는 가장 최근에 들어온 여는 괄호와 현재 닫는 괄호를 비교해야 하므로 Stack 구조가 잘 맞는다.

풀이 흐름은 다음과 같다.

1. 문자열을 앞에서부터 하나씩 확인한다.
2. '('를 만나면 stack에 넣는다.
3. ')'를 만나면 stack에서 '('를 하나 꺼낸다.
4. 만약 ')'를 만났는데 stack이 비어 있으면 짝이 맞지 않으므로 0을 반환한다.
5. 모든 문자를 확인한 뒤 stack이 비어 있으면 1, 남아 있으면 0을 반환한다.

---

처음 작성한 코드

처음에는 아래처럼 작성했다.

import java.util.*;

class Solution {
    public int solution(String S) {
        char[] charArray = S.toCharArray();        

        if (charArray.length < 2) return 0;

        Stack<Character> st = new Stack<>();

        for (char item : charArray) {
            if (item == '(') {
                st.push(item);
            } else if (item == ')') {
                if (st.isEmpty()) return 0;
                if (st.peek() == '(') st.pop();
            } 
        }

        if (st.isEmpty()) return 1;
        else return 0;
    }
}

이 코드의 기본적인 방향은 맞았다.

문자처리

(	stack에 push
)	stack이 비어 있으면 실패, 아니면 pop

하지만 아래 조건 때문에 빈 문자열 테스트를 통과하지 못했다.

if (charArray.length < 2) return 0;

---

왜 87점이 나왔을까?

문제는 S = ""인 경우였다.

빈 문자열이면:

charArray.length = 0

이므로 아래 조건에 걸린다.

if (charArray.length < 2) return 0;

그래서 0을 반환한다.

하지만 문제 정의상 빈 문자열은 properly nested이므로 정답은 1이어야 한다.

입력처음 코드 결과정답

""	0	1
"("	0	0
")"	0	0
"()"	1	1

즉, "(", ")"는 0이 맞지만, ""까지 같이 0으로 처리한 것이 문제였다.

---

수정한 코드

빈 문자열을 먼저 처리하도록 수정했다.

import java.util.*;

class Solution {
    public int solution(String S) {
        if (S.equals("")) return 1;

        char[] charArray = S.toCharArray();        

        if (charArray.length < 2) return 0;

        Stack<Character> st = new Stack<>();

        for (char item : charArray) {
            if (item == '(') {
                st.push(item);
            } else if (item == ')') {
                if (st.isEmpty()) return 0;
                if (st.peek() == '(') st.pop();
            } 
        }

        if (st.isEmpty()) return 1;
        else return 0;
    }
}

이렇게 수정한 뒤 100점을 받을 수 있었다.

---

더 깔끔하게 정리한 최종 풀이

빈 문자열은 사실 따로 처리하지 않아도 된다.

왜냐하면 빈 문자열이면 for문이 한 번도 실행되지 않고, stack은 그대로 비어 있기 때문이다.
마지막에 stack.isEmpty()를 기준으로 반환하면 자연스럽게 1이 반환된다.

import java.util.*;

class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();

        for (char ch : S.toCharArray()) {
            if (ch == '(') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) {
                    return 0;
                }

                stack.pop();
            }
        }

        return stack.isEmpty() ? 1 : 0;
    }
}

Nesting 문제는 입력 문자열이 ( 또는 )로만 이루어진다고 명시되어 있다.

string S is made only of the characters '(' and/or ')'

따라서 if (ch == '(')가 아니라면 )라고 봐도 된다.

---

Deque를 사용한 풀이

Java에서는 Stack 대신 Deque를 스택처럼 사용할 수도 있다.

import java.util.*;

class Solution {
    public int solution(String S) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char ch : S.toCharArray()) {
            if (ch == '(') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) {
                    return 0;
                }

                stack.pop();
            }
        }

        return stack.isEmpty() ? 1 : 0;
    }
}

Deque의 push()와 pop()은 앞쪽에서 동작한다.

메서드의미

push()	앞에 넣기
pop()	앞에서 꺼내기
peek()	앞 값 확인

코딩테스트에서는 Stack보다 Deque를 사용하는 풀이도 자주 볼 수 있다.

---

시간복잡도

문자열 S의 길이를 N이라고 하면, 문자열을 한 번만 순회한다.

작업시간복잡도

문자열 순회	O(N)
stack push/pop	각 O(1)
전체 시간복잡도	O(N)

각 문자는 한 번씩만 확인하고, 괄호를 넣거나 꺼내는 작업도 상수 시간에 처리된다.

따라서 전체 시간복잡도는 다음과 같다.

O(N)

---

공간복잡도

최악의 경우 모든 문자가 여는 괄호일 수 있다.

((((((((

이 경우 stack에 모든 문자가 들어갈 수 있으므로 최대 N개의 문자를 저장하게 된다.

상황공간

모든 문자가 (인 경우	stack에 N개 저장
공간복잡도	O(N)

따라서 공간복잡도는 다음과 같다.

O(N)

다만 이 문제는 (와 ) 한 종류만 다루기 때문에, Stack을 쓰지 않고 카운터 하나로도 풀 수 있다.
그 경우 공간복잡도는 O(1)까지 줄일 수 있다.

---

카운터를 사용한 풀이

(가 나오면 count를 증가시키고, )가 나오면 count를 감소시키는 방식이다.

class Solution {
    public int solution(String S) {
        int count = 0;

        for (char ch : S.toCharArray()) {
            if (ch == '(') {
                count++;
            } else {
                count--;

                if (count < 0) {
                    return 0;
                }
            }
        }

        return count == 0 ? 1 : 0;
    }
}

이 풀이에서는 stack을 사용하지 않기 때문에 공간복잡도는 O(1)이다.

풀이 방식시간복잡도공간복잡도

Stack 사용	O(N)	O(N)
Count 사용	O(N)	O(1)

다만 Stack 문제를 연습하는 목적이라면 Stack 풀이로 먼저 이해하는 것도 좋다고 생각한다.

---

이번 문제에서 배운 점

이번 문제에서 배운 점은 다음과 같다.

배운 내용정리

빈 문자열 처리	문제 정의상 ""도 properly nested이다
성급한 예외 처리 주의	length < 2를 무조건 0으로 처리하면 빈 문자열을 놓친다
Stack 활용	여는 괄호를 저장하고 닫는 괄호가 나오면 pop한다
문제 조건 확인	입력 문자는 (, )만 들어온다
시간복잡도	한 번 순회하므로 O(N)
공간복잡도	Stack 사용 시 최악 O(N), count 사용 시 O(1)

---

마무리

이번 Nesting 문제는 Stack 기본기를 연습하기 좋은 문제였다.

풀이 자체는 어렵지 않았지만, 문제 정의를 정확히 읽지 않아서 빈 문자열 케이스를 놓쳤고 첫 제출에서 87점을 받았다.

특히 아래 조건을 제대로 확인하지 못한 것이 원인이었다.

S is empty;

이 조건 때문에 빈 문자열 ""도 올바른 중첩 문자열로 판단해야 한다.

이번 문제를 통해 단순히 구현을 빠르게 하는 것보다,
문제에서 정의한 올바른 상태가 무엇인지 먼저 확인하는 것이 중요하다는 점을 다시 느꼈다.

다음부터는 예외 조건을 직접 추가하기 전에, 해당 조건이 문제 정의와 충돌하지 않는지 먼저 확인해야겠다.