[HackerRank][String Manipulation] Special String Again

 

 

 

문제 링크

 

www.hackerrank.com/challenges/special-palindrome-again/problem

Special String Again | HackerRank

A string is said to be a special string if either of two conditions is met:

• All of the characters are the same, e.g. aaa.
• All characters except the middle one are the same, e.g. aadaa.

 

A special substring is any substring of a string which meets one of those criteria. Given a string, determine how many special substrings can be formed from it.

 

Example

s = mnonopoo

s contains the following  special substrings: {m, n, o, n, o, p, o, o, non, ono, opo, oo}.

 

Function Description

Complete the substrCount function in the editor below.

substrCount has the following parameter(s):

• int n: the length of string s
• string s: a string

 

Returns
- int: the number of special substrings

 

Input Format

The first line contains an integer n, , the length of s.
The second line contains the string s.

 

Constraints

1 <= n <= 10^6

Each character of the string is a lowercase English letter, ascii[a-z] .

 

 

 

 

 

문제 해석

 

주어진 문자열의 sub string 중, 가운데 문자를 제외한 나머지 문자가 모두 같은 sub string의 개수를 구하는 문제.

간단하게 시작 문자열을 잡고 그 다음 문자를 바꿔가며 하나씩 개수를 세어주면 되는 듯 하다. 이중 for문이 되겠지?

중간 문자열을 만났는지 flag 하나 두어서 체크하기!

이중 for문 안쓰고 할 수 있는 방법이 있는지 생각해 보기 (?)

 

 

 

 

 

제출 코드

// Complete the substrCount function below.
    static long substrCount(int n, String s) {

        long result = n;
        char[] sCharArray = s.toCharArray();
        
        for (int i = 0; i < n - 1; i++) {
            int sameCnt = 1;
            boolean turnFlag = false;
            char start = sCharArray[i];
            
            for (int j = i + 1; j < n; j++) {
                if (start == sCharArray[j]) {
                    if (turnFlag) {
                        sameCnt--;
                        if (sameCnt == 0) {
                            result++;
                            break;
                        }
                    }
                    else {
                        sameCnt++;
                        result++;
                    }
                } 
                else {
                    if (turnFlag) break;
                    else turnFlag = true;
                }
            }
        }
        
        return result;
    }

 

 

+

아래는 해커랭크에서 따봉을 가장 많이 받은 Python코드를 Java로 작성한 답안입니다 :)

// Complete the substrCount function below.
    static long substrCount(int n, String s) {
        List<Character> charArray = new ArrayList<>();
        List<Integer> countArray = new ArrayList<>();
        char[] sCharArray = s.toCharArray();

        char spot = sCharArray[0];
        int count = 1;
        
        for(int i = 1; i < n; i++) {
            if (spot == sCharArray[i]) count++;
            else {
                charArray.add(spot);
                countArray.add(count);
                spot = sCharArray[i];
                count = 1;
            }               
        }
        charArray.add(spot);
        countArray.add(count);
        
        long result = 0;
        
        for (int i = 0; i < charArray.size(); i++) {
            Integer value = countArray.get(i);
            result += ((value * (value + 1)) / 2);
        }   
        
        for (int i = 1; i < charArray.size() - 1; i++) {
            if ((charArray.get(i - 1) == charArray.get(i + 1)) && countArray.get(i) == 1) {
                result += min(countArray.get(i - 1), countArray.get(i + 1));
            }
        }
        
        return result;
    }

 

 

 

 

어떻게 더 빠르게 할 수 있을까..

이중 for문은 웬만해서 쓰고 싶지 않은데 써부러따 ㅜㅜ

- mushroong

 

 

 

 

---