프로그래머스-level2-쇠막대기

https://programmers.co.kr/learn/courses/30/lessons/42585

코딩테스트 연습 - 쇠막대기 | 프로그래머스

 (  ) 갯수 일치 여부를 활용하는 문제의 연장선이다...(백준에 있음)

접근 방법은

    1. 먼저 () 인 애들 찾아서 ,로 replace 하고
    2. 왼쪽에서부터 (는 +1 , )는 -1을 한다.(글자수 만큼)
       중간에 있는 , 를 카운팅한다.
       0이 되는 시점에 sum에 카운팅+1을 한다.
       그리고 카운팅을 0으로 초기화 한다.
    3. 2번과정 끝까지 반복 

기본적으로 정확성에는 문제가 없는 것 같으나 효율성에서 시간을 초과한다...

이중 반복문에 if else 가 난무하니 시간이....

주어진 스트링의 최대 길이는 10만...  최적화를 시도해보겠다!

class Solution {
    public int solution(String arrangement) {
        StringBuilder s = new StringBuilder("");
		s.append(arrangement);
		// () 를 , 로 바꿈
		while(true) {
			int index = s.indexOf("()");
			if(index == -1) {break;}
			s.replace(index, index+2, ",");
		}
		int count =0;
		
		int answer =0;
		while(true) {
			int check =0;
			int index;
			int lastIndex;
			for(int i =0; i < s.length(); i++) {	//길이만큼 반복
				index = s.indexOf("(");
				if(s.charAt(i) =='(') {check += 1;}	// ( 일 경우 +1
				else if(s.charAt(i) ==')') {check -= 1;}  // ) 일 경우 -1
				else {
					if(i > index) {
						count++; 
					}
				}						// , 일 경우 count
				if(i >= index && check ==0 && count > 0) {
					lastIndex = i;
					answer += (count+1);
					s.deleteCharAt(index);
					s.deleteCharAt(lastIndex-1);
					count = 0;
					break;
				}  // ( ) 맞아 떨어질 경우 sum
			}
			if(s.indexOf("(") == -1) {break;}
		}
		return answer;
    }
}

참고한 코드

아래 코드는 1개의 for문에서 모든 처리를 한다.

단순하게 접근해서 

  1. " ( " 로 시작하면 queue에 넣고 " ) "로 시작하면 queue 마지막에 있는 " ( "를 추출하면서 +1을 한다.

  2. " ( ) " 인 구간이 있으면 선이 그어지는 왼쪽 갯수를 더한다.( + queue.size()가 된다)

 

즉 나는 외부 for문으로 선의 갯수만큼 반복하면서 내부 for에서는 나누어진 선의 갯수를 더했지만

참고한 코드는 쇠막대기로 쪼갠 것을 기준으로 모든 선의 갯수만큼 더했다.

class Solution {
    public int solution(String arrangement) {
        int answer = 0;
        char startBrace = '(', endBrace = ')';
        LinkedList<Character> queue = new LinkedList<>();

        //TODO : 쇠막대기 - 스택/큐 -> arrangement 큐로 변환 하여 풀이 하기
        for (int index = 0; index < arrangement.length(); index++) {
            if (arrangement.charAt(index) == startBrace && arrangement.charAt(index + 1) == endBrace) {
                answer += queue.size();
                index++;
                continue;
            }

            char brace = arrangement.charAt(index);

            if (brace == startBrace) {
                queue.add(brace);
            } else {
                queue.pollLast();
                answer++;
            }
        }

        return answer;
    }
}