[코딜리티] codility lesson 7 Stacks and Queues - Brackets 100%

문제.

Programming language:                 C                        C++                        C#                        Go                        Java                        JavaScript                        Lua                        Objective-C                        Pascal                        PHP                        Perl                        Python                        Ruby                        Scala                        Swift 2                        Swift 3                        VB.NET                    

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

• S is empty;
• S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
• S has the form "VW" where V and W are properly nested strings.

For example, the string "{[()()]}" is properly nested but "([)()]" is not.

Write a function:

int solution(char *S);

that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.

For example, given S = "{[()()]}", the function should return 1 and given S = "([)()]", the function should return 0, as explained above.

Assume that:

• N is an integer within the range [0..200,000];
• string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Copyright 2009–2017 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

풀이.

123456789101112131415161718192021222324252627282930313233

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(String S) {
        // write your code in Java SE 8
        if(S.length()%2 != 0) return 0;
  ArrayList<Character> R = new ArrayList<Character>();
        
  for( char i : S.toCharArray()){
   if( i == '(' || i == '{' || i == '[') R.add(i);
   if( i == ')' || i == '}' || i == ']'){
       if(R.size() == 0) return 0;
    char chk=' ';

    switch(i){
    case ')' : chk = '('; break;
    case '}' : chk = '{'; break;
    case ']' : chk = '['; break;
    }
    
    if(R.get(R.size()-1) != chk) return 0;
    R.remove(R.size()-1);
   } 
  }
  if(!R.isEmpty()) return 0;
  return 1;
    }

}

설명.

괄호가 잘 닫혀 있는지 판별하여라

맞으면 1 틀리면 0

스택구조체 를 사용하지 않고서 풀고 싶었다....

작전 1 앞 과 뒤를 비교하면서 커플링이 잘됬는지 비교하고 특이 케이스를 예외 처리한다.

결과 1 관둠. 이거 예외 케이스 처리하는데 시간이 오래걸림.

작전 2 스트링 자체가 배열이므로 스트링을 스택처럼 사용해서 끝내보자

결과 2 스트링 객체가 딱 한가지 케이스 에서 연산 속도가 느림. 80% 가 됨

작전 3 뭐긴 뭐야 그냥 스택구조체 쓰는 거지

결과 3 100% 이건 뭐 답이 정해져 있는 듯.

사실 이 과정들은 코딜리티 레슨 을 풀면서 학습하게 된 이유가 크다.

뭘 해도 테스트케이스만 통과하면 됨. 우선 작전1 을 수행 해 봄.

두번째 작전 2는 '이미 있는 구조체를 쓰는 건 알고리즘 을 만드는것 같지가 않어서.'

마지막 작전 3은 답부터 정해놓고 문제 만든거 같아서. 시...시키는 데로 하겠습니다.

아마 코딜리티 문제가 쉽다고 말하는 사람들은 작전3의 이유 인거 같다.