482. License Key Formatting (해석 + 풀이)

조건:

• 1 <= s.length <= 105
• s consists of English letters, digits, and dashes '-'.
• 1 <= k <= 104

의역: 영문자와 숫자 그리고 - 로만 구성된 문자열 s와 정수 k가 제공될 때

정수 k 보다 짧을 수 있지만 적어도 하나의 문자(영문자 or 숫자)를 포함해야 하는 첫 번째 그룹을 제외하고

그룹: -로 나누어진 문자열 

각 그룹이 정확히 k자를 포함하고 모든 소문자를 대문자로 변환하여 변경된 문자열 s를 반환하라

+ 문자의 위치는 변경할 필요 없다.

의역: 문자 4개로 이루어진 그룹을 만들어야 하므로 -를 제외하면 8문자 이기 때문에 중간에 -을 넣은 문자열을 반환한다.

 

풀이: 

1. StringBuilder 이용 (오른쪽 부터 왼쪽으로 순차적으로 채우기)

class Solution {
    public String licenseKeyFormatting(String s, int k) {
        s.toUpperCase();
        // - 를 제거한 문자열 생성
        char sArray[] = s.toCharArray(); // split 보다 더 빠른 속도로 가능
        StringBuilder deletedDashS = new StringBuilder(""); // 문자열 합치기에 최적
        for (char unit:sArray)
            if(unit!='-')
                deletedDashS.append(unit);
        int count = 0;
        // 뒤에서 부터 카운팅 하여 해당 k번째 자리가 된다면 해당 자리에 - 추가
        for(int i=deletedDashS.length()-1;i>=0;i--){
            if(count!=0&&count%k==0)
                deletedDashS.insert(i+1,'-');
            count++;
        }
        return deletedDashS.toString();
    }
}

1-1 좀더 효율적인 코드 (LeetCode 공식 풀이 코드) 

StringBuilder의 insert를 안써서 그런지 속도 면에서 더 우월했다.

class Solution {
    public String licenseKeyFormatting(String s, int k) {
        char[] chars = s.toCharArray();
        
        int count = 0;
        
        for (int i = 0; i<chars.length; i++) {
            char c = chars[i];
            if (c != '-')
                count++;
        }
        
        StringBuilder b = new StringBuilder(count + (count % k));
        
        int pos = 0;
        
        // first group
        {
            int n = count % k;
            
            count -= n;
            
            while (n > 0) {
                
                while (chars[pos] == '-')
                    pos++;
                
                b.append(Character.toUpperCase(chars[pos]));
                
                pos++;
                n--;
            }
        
            if (pos > 0 && count > 0) {
                b.append('-');
            }
        }
        
        // other groups
        while (count > 0) {
            
            int n = k;
            
            count -= k;
            
            while (n > 0) {
                
                while (chars[pos] == '-')
                    pos++;
                
                b.append(Character.toUpperCase(chars[pos]));
                
                pos++;
                n--;
            }
        
            if (pos > 0 && count > 0) {
                b.append('-');
            }
        }
        
        return b.toString();
    }
}

링크: https://leetcode.com/problems/license-key-formatting/description/

메모: StringBuilder의 insert는 가급적 쓰지 말자.