[Codility(코딜리티)] Lesson7. Nesting (100%)

Lesson 7 Stacks and Queues - Nesting (Java Solution)

app.codility.com/programmers/lessons/7-stacks_and_queues/nesting/

Nesting coding task - Learn to Code - Codility

---

문제

N개의 문자로 이루어진 String S가 주어진다

S = "(()(())())" 이런 형태로 주어지는데,

모든 문자가 완전하게 ()로 감싸 지면 1 아니면 0이다 

예를 들어,

S = "(()(())())" 이면, ()로 모두 감싸 져서 답은 1이다

S = "())" 이면, )가 하나 남는다 따라서 0 이다

 

해결

큐로 풀었다

큐에 먼저 문자를 array로 쪼개서 넣는다

그리고 '('와 ')'의 개수를 세는 변수 front, back을 선언한다

그리고 큐를 돌려서,

'('이면 큐에서 꺼내고, first를 1씩 올려준다

')'이면 큐에서 꺼내고. back을 1씩 올려준다 (단, front가 0이면 이미 감싸 지지 않으므로 break 한다)

최종적으로 front+back이 0이면 감싸 졌으므로 1 아니면 0을 출력한다

public class Nesting {

    public int solution(String s) {
        Queue<Character> queue = new ArrayDeque<>();
        for (char c : s.toCharArray()) queue.add(c);

        int front = 0;
        int back = 0;

        while (!queue.isEmpty()) {
            if (queue.peek() == ')') {
                queue.poll();
                back++;
                if (front == 0) break;
                front--;
                back--;
            } else if (queue.peek() == '(') {
                queue.poll();
                front++;
            }
        }

        return front+back == 0 ? 1 : 0;
    }