section5.1

괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다.
(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.

입력설명
첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다.

출력설명
첫 번째 줄에 YES, NO를 출력한다.

입력예제 1
(()(()))(()

출력예제 1
NO

 

 

 

 

ANSWER

public class Question1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        System.out.println(solution(s));
    }

    public static String solution(String s) {
        String answer = "YES";

        // 리스트로 만들기
        // ( 다음 ) 오는 순서대로 리스트에서 삭제
        // 한바퀴 돈 후 처음과 마지막 (,) 짝인이 확인
        // 계속 진행 > 시간이 오래 걸릴지 모르겠다

        List<Character> tmpList = new ArrayList<>();
        for (char x : s.toCharArray()) {
            tmpList.add(x);
        }

        while (!tmpList.isEmpty()) {
            for (int i = 0; i < tmpList.size()-1; i ++) {
                if (!tmpList.get(0).equals('(') || !tmpList.get(tmpList.size() - 1).equals(')')) {
                    return "NO";
                }

                if (tmpList.get(i).equals('(') && tmpList.get(i+1).equals(')')) {
                    tmpList.set(i, '0');
                    tmpList.set(i+1, '0');
                }
            }

            Iterator<Character> iterator = tmpList.iterator();
            while (iterator.hasNext()) {
                Character character = iterator.next();
                if ('0' == character) {
                    iterator.remove();
                }
            }
        }

        return answer;
    }
}

• 정답도 맞고 시간초과도 없었지만 스택을 어떻게 사용해야 할지 몰라서 이렇게 풀었다

 

 

 

SOLUTION

public class Answer1 {
    public static void main(String[] args) {
        Answer1 T = new Answer1();
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        System.out.println(T.solution(str));
    }

    public String solution(String str) {
        String answer = "YES";
        Stack<Character> stack = new Stack<>();

        for (char x : str.toCharArray()) {
            if (x == '(') {
                stack.push(x);
            } else {
                if (stack.isEmpty()) {
                    return "NO";
                }
                stack.pop();
            }
        }

        if (!stack.isEmpty()) {
            return "NO";
        }

        return answer;
    }
}

• 스택
  • 후입선출 : 먼저 들어온 데이터가 나중에 나가는 구조
  • 단반향 일출력 구조
  • 깊이 우선 탐색(DFS)에 이용

 

 

 

cf. Exception in thread "main" java.util.ConcurrentModificationException

// 0 제거
int tmpZero = 0;
for (char x : tmpList) {
    if (x == '0') {
        tmpList.remove(tmpZero);
    }
    tmpZero ++;
}

Iterator<Character> iterator = tmpList.iterator();
while (iterator.hasNext()) {
	Character character = iterator.next();
	if ('0' == character) {
		iterator.remove();
	}
}

• 보통 ConcurrentModificationException는 멀티스레드 환경에서 발생하는 문제
• 지금의 경우는 멀티스레드와 관련이 없는데 for-each문 순회 중 요소 추가/삭제 시 문제가 되고 있다
  • for-each문은 iterator를 활용해 순회 작업을 수행하는데 iterator는 순회 도중 컬렉션의 변경 여부를 감지할 수 있으며 직접 remove를 호출하여 현재 요소를 삭제하면 변경을 감지한 iterator가 순회를 중단하고 ConcurrentModificationException를 발생하게 된다
  • for-each문은 iterator를 사용하여 순회하는데 여기서 iterator는 read-only이기 대문에 컬렉션을 변경하는 작업은 허용되지 않는다
  • 따라서 컬렉션을 순회하면서 요소를 변경해야하는 경우 for-each문 대신 일반 반복문 혹은 iterator를 직접 활용하여 변경할 수 있다
  • 참고 : https://jyyoun1022.tistory.com/12