[Leetcode]3271. Hash Divided String

문제 요약

• 알고리즘 분류: Hash, Ascill Code, 문자열
• 난이도: Medium
• 문제내용:
  • a-z 를 0-25까지 표현한다.(ex. a = 0, b = 1, c = 3 ...... ,z = 25)
  • 문제에서 문자열 s, k정수를 준다.
  • 문자열 s에서 k만큼 자르고 자른 문자열에서 각 알파벳을 숫자로 변환하고 합친다.
  • 합친것을 숫자에서 알파벳으로 변한다. 넘어가면 26나머지 값을 알파벳을 변환한다.
  • 자른 문자열에서 처리한 것들을 합친것을 반한하여라
• 사이트 주소: https://leetcode.com/problems/hash-divided-string/description/

문제풀이

 이번 문제는 문자열을 각 문자형으로 변환후 Ascill Code로 처리하는 문제이다. 문자형 Ascill Code로 변환해서 처리하는 문제도 자주 나오기 때문에 처리하는 방법을 알면 다른문제에서도 응용을 많이 할수 있다. 이번 문제풀이 설명하기전에 문자형을 Ascill Code로 어떻게 처리하는지 보면 된다.  문자형 0 ~9는 Ascill Code값으로 30~39, 대문제 알파벳 A-Z는 65-90, 소문자 알파벳 a-z는 97-127로 나타낸다. 그러면 알파벳을 숫자로 순서대로 mapping해서 처리하는것은 알파벳 'a'나 'A'를 Ascill Code값만큼 빼면 되는것이다.

그럼 다시 문제로 가면 a-z 를 0-25까지 표현하는것은 위에 설명 처럼 문자열을 Ascill Code값을 변환해서 'a'만큼 코드 값 만큼 빼서 처리하면된다. 그다음 각 변환한것을 합쳐서 나머지 26으로 처리하면된다. 그 다음에는  Ascill Code 'a'만큼 더해서 알파벳으로 변환 하면끝이다. 그래서 각 k길이만큼 처리한 것끼리 합치기만 하면 끝이다. 

이번 문제는 문자열 slicing 처리하는 방법과  Ascill Code로 변환해서 처리하는 방법만 알면 구현 하는데 어렵지는 않다. 이렇게 구현하면 시간 복잡도는 O(N)만큼 나온다. 코드는 아래 참고 하면된다.

Code

Python

class Solution:
    def stringHash(self, s: str, k: int) -> str:

        result = ""
        # k 길이 만큼 증가
        for i in range(0, len(s), k):
            #
            result += chr(sum(map(lambda x: ord(x) - ord('a'), list(s[i: i + k]))) % 26 + ord('a'))
        return result

아래 코드는 위의 코드 압축형이라고 보면된다.

class Solution:
    def stringHash(self, s: str, k: int) -> str:
        # k 길이 만큼 증가
        # k 길이 만큼 문자 합치고 'z' 나눈 나머지를 문자 값으로 변환 한다.
        return ''.join([chr(sum(map(lambda x: ord(x) - ord('a'), list(s[i: i + k]))) % 26 + ord('a')) for i in range(0, len(s), k)])

Java

class Solution {
    public String stringHash(String s, int k) {
        String result = "";
        int index = 0;

        while(index < s.length()){
            int ch = 0;
            for (int i = 0; i < k; i++) {
                ch += s.charAt(index + i) - 'a';
            }

            ch %= 26;

            result +=(char)  (ch + 'a');
            index += k;
        }

        return result;
    }
}