[HackerRank][String Manipulation] Sherlock and the Valid String

 

 

 

 

문제 링크

 

www.hackerrank.com/challenges/sherlock-and-valid-string

Sherlock and the Valid String | HackerRank

Sherlock considers a string to be valid if all characters of the string appear the same number of times. It is also valid if he can remove just  character at  index in the string, and the remaining characters will occur the same number of times. Given a string , determine if it is valid. If so, return YES, otherwise return NO.

 

 

Example

 

s = abc

This is a valid string because frequencies are {a: 1, b: 1, c: 1}.

 

s = abcc

This is a valid string because we can remove one c and have 1 of each character in the remaining string.

 

s = abccc

This string is not valid as we can only remove 1 occurrence of c. That leaves character frequencies of {a: 1, b: 1, c: 2}.

 

 

Function Description

Complete the isValid function in the editor below.

isValid has the following parameter(s):

• string s: a string

 

Returns

• string: either YES or NO

 

Input Format

A single string s.

 

 

Constraints

• 1 <= |s| <= 10^5
• Each character s[i] included in ascii[a-z]

 

 

 

 

문제 해석

 

딱 하나 이하만 지워서 남은 각각의 소문자 개수가 모두 같아야 하는 문제. 간단한 문제인데 edge case가 많았다.. 

아래 경우는 "YES"가 나와야 하는 경우이다. 이것만 잘 처리해 준다면 나머진 "NO"를 뱉어주면 끝!

• case 1. 한 문자로만 이루어져 있는 경우. ex) aaaaaa
• case 2. 모든 개수가 같은 경우. ex) aaabbbccc
• case 3. 다른 문자보다 딱 한 개 더 많이 있는 경우. ex) aabbccc
• case 4.괜히 하나 껴있는 경우  ex) aaaabbbbccccd

 

각 문자 별로 개수를 먼저 구해준 다음, 그 중 min과 max을 구하였다.

그렇게 구한 문자 개수 배열에서 min과 max을 빼주어 판단할 수 있는 경우가 각각 case 3, case 4이다.

아래 코드를 참고하여 자세히 알아보자!

 

 

 

 

제출 코드

public static String isValid(String s) {
    // Write your code here
        int[] eng = new int[26];
        for (char c: s.toCharArray()) {
            eng[c - 'a']++;
        }
        
        int cnt = 0;
        for(int i: eng) {
            if (i > 0) cnt++;
        }
        // case 1. 한 문자로만 이루어진 경우
        if (cnt == 1) return "YES";
        
        int min = 1000000;
        int max = 0;
        for (int i: eng) {
            if (i < min && i > 0) min = i; // i > 0 조심하기!
            if (i > max) max = i;
        }
        
        int[] maxEng = new int[26];
        int[] minEng = new int[26];
        
        for (int i = 0; i < 26; i++) {
            if (eng[i] == 0) continue; // 0일 경우는 넘겨주는게 편하다
            maxEng[i] = eng[i] - max;
            minEng[i] = eng[i] - min;
        }

        int maxCnt = 0;
        for (int i: maxEng) {
            if (i < 0) {
                maxCnt++;
            }
        }
        
        int minDiff = 0;
        int minCnt = 0;
        for (int i: minEng) {
            if (i > 0) {
                minCnt++;
                minDiff += i;
            }
        }
        
        String res = "";
        // if (case 2, 4. 개수가 똑같은 경우, 괜히 하나 껴있는 경우 || case 3. 하나만 한개 많은 경우)
        if (maxCnt <= 1 || (minCnt = 1 && minDiff == 1)) res = "YES";
        else res = "NO";
                
        return res;
}

 

 

 

 

 

 

 

그렇게 어려운 문제가 아니였는데 시간을 많이 썼다.... ㅠㅠㅠㅠ

첨에 접근을 너무 대충했던거 같아! 담에는 꼼꼼히 정리해서 풀어보자 8)

- mushroong

 

 

 

 

---