Java - 시저 암호, 숫자 문자열과 영단어, 문자열 내 마음대로 정렬하기, K번째 수

Java

시저 암호

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/131705
• 어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고함
• "AB"는 1 만큼 밀면 "BC"가 되고 c만큼 밀면 "DE"가 되며 "z"는 1 만큼 밀면 "a"가 됨
• 문자열 s와 거리 n을 입력받아 s를 n만큼 민 암호문을 만드는 함수 solution을 완성

제한조건

• 공백은 아무리 밀어도 공백임
• s는 알파뱃 소문자, 대문자, 공백으로만 이루어져 있으며 s의 길이는 8000 이하임
• n은 1 이상, 25이하인 자연수임

입출력 예시

나의 풀이

class Solution {
    public String solution(String s, int n) {
        char[] charArr = s.toCharArray();

        StringBuilder answer = new StringBuilder();

        for (char c : charArr) {

            if (c == ' ') {
                answer.append(' ');
            } else if ('a' <= c && c <= 'z') {
                answer.append((char) ((c - 'a' + n) % 26 + 'a'));
            } else if ('A' <= c && c <= 'Z') {
                answer.append((char) ((c - 'A' + n) % 26 + 'A'));
            }
        }
        return answer.toString();
    }

}

• 문장의 각 알파벳을 일정한 정수 n만큼 밀면 된다는 것에 아스키 코드를 활용해야겠다고 생각하여 스트링 s를 toCharArray()로 캐릭터 배열을 먼저 만들었다.
• 그다음 조작한 문자를 문자열로 하나씩 저장해야 하므로 문자열과 + 연산을 하는 것보다 StringBuilder를 활용하는 것이 좋다고 생각해 StringBuilder를 생성했다
• 그다음 반복문으로 문자 배열의 각 요소와 n을 더해주는데, 이때 요구사항의 조건을 만족시키기 위한 if - else if 문을 작성했다
• 우선 ' ' (공백)으로 들어오면 문자열에 그냥 공백을 추가시켰다.
• 아스키 코드값은 대문자와 소문자 사이에 다른 값들이 있기 때문에 대, 소문자의 영역으로만 밀어야 하는 문제가 있었다.
• 그래서 우선 문자 배열의 요소가 대문자인지, 소문자인지 검증을 하고 넘어온 요소가 소문자라면 'a'를, 대문자라면 'A'를 빼면 넘어온 문자가 알파벳 순서의 몇 번째 인덱스에 있는지를 알 수 있다.
  
  • 알파벳은 26개가 있으므로  'a' 는 0번째 라고하면, 'z' 는 25번째에 있다. 이 위치를 인덱스라고 표현할 수 있따
  • 'd' - 'a' = 3 이 되므로 알파벳 모음의 3번째 인덱스에 위치했다고 볼 수 있다
• 그럼다음 + n 연산을 해줘서 요구사항대로 n번째 만큼 알파벳을 증가시킨다.
• 그 이후 % 26연산을 하는데, 만약 구해진 알파벳 인덱스의 값이 25를 넘어간다면 요구사항대로 다시 알파벳 처음으로 돌아가야하기 때문에 알파벳의 개수만큼 나머지 연산을 하면 나머지의 값 만큼이 다시 알파벳의 처음부터 계산한 알파벳의 인덱스가 된다
  • 26 % 26 = 0, 알파벳의 0번째 인덱스이므로 'a'가 됨
  • 28 % 26 = 2, 알파벳의 2번째 인덱스이므로 'c'가 됨
• 이후 구해진 값을 문자로 복호화 시키기 위해 대문자 였다면 'A'를 소문자 'a'를 더해주고 생성한 StringBuiler에 추가시켜주고 함수의 반환값이 String이기 때문에 toString()을 통해 반환해주면 문제를 풀 수 있다.

다른 풀이

class Caesar {
    String caesar(String s, int n) {
        String result = "";
    n = n % 26;
    for (int i = 0; i < s.length(); i++) {
      char ch = s.charAt(i);
      if (Character.isLowerCase(ch)) {
        ch = (char) ((ch - 'a' + n) % 26 + 'a');
      } else if (Character.isUpperCase(ch)) {
        ch = (char) ((ch - 'A' + n) % 26 + 'A');
      }
      result += ch;
    }
        return result;
    }
}

• 접근 방식은 똑같지만 Character.isLowerCase(), Character.isUpperCase()를 활용하여 대, 소문자를 검증하는 방법을 알게 되어서 가져왔다.

class Caesar {
    public String caesar(String s, int _n) {
        return s.chars().map(c -> {
            int n = _n % 26;
            if (c >= 'a' && c <= 'z') {
                return 'a' + (c - 'a' + n) % 26;
            } else if (c >= 'A' && c <= 'Z') {
                return 'A' + (c - 'A' + n) % 26;
            } else {
                return c;
            }
        }).mapToObj(c -> String.valueOf((char)c))
        .reduce((a, b) -> a + b).orElse("");
    }
}

• 마찬가지로 접근은 같은데, Stream을 활용한 방법이다
• 처음에는 나도 스트림으로 접근해보고자 Arrays.stream()을 사용했는데 문자 배열은 이것으로 스트림을 얻을 수 없어서 우선 빨리 풀어야겠다는 생각에 반복문으로 접근했었는데 chars()를 다시한번 상기시키는 계기가 되었다.
• 알고리즘 공부를 하면서 문자열을 chars()를 통해 아스키코드 값의 스트림을 얻을 수 있다는 것을 알게되었었는데.. 좀 더 생각이 오래걸리더라도 스트림을 익숙하게 하려면 생각하는 시간을 조금은 길게 가져야 할 것 같다

---

숫자 문자열과 영단어

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/81301
• 숫자의 일부 자릿수가 영단어로 바뀌어졌거나 혹은 바뀌지 안혹 그대로인 문자열 s가 매개변수로 주어질 때 s가 의미하는 원래 숫자를 return하는 함수를 완성
  • 1478 → "one4seveneight"
  • 234567 → "23four5six7"
  • 10203 → "1zerotwozero3"

제한조건

• s의 길이는 1 ~ 50 이며 s가 "zero" 또는 "0"으로 시작하는 경우는 주어지지 않음
• return 값이 1 ~ 2,000,000,000 이하의 정수가 되는 올바른 입력만 s로 주어짐

입출력 예시

나의 풀이

import java.util.HashMap;
import java.util.Map;

class Solution {
    
    public int solution(String s) {
        
        Map<String, String> englishNumber = new HashMap<>();

        englishNumber.put("zero", "0");
        englishNumber.put("one", "1");
        englishNumber.put("two", "2");
        englishNumber.put("three", "3");
        englishNumber.put("four", "4");
        englishNumber.put("five", "5");
        englishNumber.put("six", "6");
        englishNumber.put("seven", "7");
        englishNumber.put("eight", "8");
        englishNumber.put("nine", "9");
        
        char[] charArr = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        StringBuilder strNumber = new StringBuilder();

        int index = 0;

        for (char c : charArr) {

            if (c - '0' < 10) {
                strNumber.append(c);
                continue;
            }

            sb.append(c);
            index++;
            String getEnglishNumber = englishNumber.get(sb.toString());

            if (getEnglishNumber == null) {
                continue;
            }

            strNumber.append(getEnglishNumber);
            sb.delete(0, index);
        }

        return Integer.parseInt(strNumber.toString());
    }
}

• 먼저 주어진 문자열인 s에 숫자의 영단어나, 문자열인 숫자를 골라내고 원문을 골라낸 값은 제거해야한다고 생각했다.
• 그러면 어차피 s에 각 요소를 하나씩 꺼내서 내가 변환하고자 하는 영단어나 문자인 숫자인지를 비교하여 맞으면 이 문자열을 누적시켜서 반환하면 될 것 같다고 생각했다.
• 그래서 s의 요소를 꺼내기 위해서 문자 배열로 변환하여 문자를 하나씩 꺼낸 후 StringBuilder를 만들어서 이 꺼내진 문자를 하나씩 누적시키면서 원하는 문자가 되면 또다른 Stringbuilder인 strNumber에 해당 문자열을 누적시키고 비교를 위해 먼저 누적시켰던 StringBuilder는 delete()로 다시 초기화 시켰다.
• 여기서 비교 대상이 필요하므로 Map<String, String> 을 동해 키값은 영단어, 밸류는 문자열인 숫자를 반환하도록 하였는데, 숫자가 아닌 문자열인 숫자로 반환하는 이유는 어차피 문자열로 합친다음 마지막에 한번에 숫자타입으로 형변환 할 예정이기 때문이다
• 이 로직을 거치면 영어단어는 모두 문자열인 숫자로 변환할 수 있는데 문제는 주어진 문자열 s에 문자열인 숫자가 들어있는 경우도 검증해야 한다.
• 이를 검증하기 위해서 if문을 통해 문자배열에서 하나씩 값을 꺼낸 문자에 '0'을 뺀 값이 10보다 작으면 이 문자는 숫자라는 것이므로 즉시 strNumber에 해당 문자를 그대로 추가시킨 후 continue;로 바로 다음 반복문으로 가도록 작성하여 모든 조건을 해결했다.

다른 풀이

class Solution {
    public int solution(String s) {
        String[] strArr = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
        for(int i = 0; i < strArr.length; i++) {
            s = s.replaceAll(strArr[i], Integer.toString(i));
        }
        return Integer.parseInt(s);
    }
}

• 문자 배열로 영어 단어를 구성한다음 주어진 문자열을 replaceAll(변경 대상인 문자열, 변경해야 할 문자열)로 매우 깔끔하고 가독성있게 해결한 것이 인상깊어서 가져왔다.
• 물론 반복문으로 계속 문자열을 생성하는 것이 StringBuilder보단 성능이 낮을 수 있으나 연산 횟수가 많지 않고 매우 간단하게 해결할 수 있다는 점에서 간단한 문자열 변환은 replaceAll()을 사용해봐야겠다고 생각했다.
  • replaceAll()은 첫 번째 인자에 정규식을 받으므로 정규식을 통해 다양한 문자열을 원하고자 하는 문자열로 수정할 수도 있다.
  • 다만 정규식을 사용하여 문자열을 변환하는 방식은 일반적으로 문자열을 직접 다루는 것보다 성능이 떨어질 수 있다
• 지금 문제의 경우 어차피 배열을 순회해서 값을 꺼내서 변경해야 하기 때문에 정규식을 사용하지 않는 replace()를 사용해도 문제를 해결함과 동시에 성능도 올릴 수 있다.

각 방법 별 실행 결과 성능 속도의 비교

• replace와 replaceAll을 사용한 속도 비교를 참고하자.

나의 풀이 -> Map와 문자 배열 활용

테스트 1 〉 통과 (0.06ms, 72.9MB)

테스트 2 〉 통과 (0.11ms, 84.2MB)

테스트 3 〉 통과 (0.13ms, 68.9MB)

테스트 4 〉 통과 (0.07ms, 83.8MB)

테스트 5 〉 통과 (0.12ms, 83.4MB)

테스트 6 〉 통과 (0.12ms, 77.1MB)

테스트 7 〉 통과 (0.08ms, 70.5MB)

테스트 8 〉 통과 (0.11ms, 67.4MB)

테스트 9 〉 통과 (0.07ms, 79.8MB)

테스트 10 〉 통과 (0.06ms, 99.1MB)

 

다른 풀이 - replace() 사용

테스트 1 〉 통과 (0.09ms, 76.7MB)

테스트 2 〉 통과 (0.06ms, 83.1MB)

테스트 3 〉 통과 (0.06ms, 72.6MB)

테스트 4 〉 통과 (0.09ms, 78.2MB)

테스트 5 〉 통과 (0.11ms, 82.2MB)

테스트 6 〉 통과 (0.09ms, 72.6MB)

테스트 7 〉 통과 (0.06ms, 77.7MB)

테스트 8 〉 통과 (0.07ms, 76MB)

테스트 9 〉 통과 (0.10ms, 74.1MB)

테스트 10 〉 통과 (0.08ms, 88MB)

 

다른 풀이 - replaceAll() 사용

테스트 1 〉 통과 (0.43ms, 83.8MB)

테스트 2 〉 통과 (0.30ms, 88MB)

테스트 3 〉 통과 (0.32ms, 72.9MB)

테스트 4 〉 통과 (0.32ms, 92MB)

테스트 5 〉 통과 (0.31ms, 86.1MB)

테스트 6 〉 통과 (0.35ms, 81.4MB)

테스트 7 〉 통과 (0.41ms, 86.4MB)

테스트 8 〉 통과 (0.35ms, 86.6MB)

테스트 9 〉 통과 (0.37ms, 73.4MB)

테스트 10 〉 통과 (0.44ms, 84.3MB)

---

문자열 내 마음대로 정렬하기

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/12915
• 문자열로 구성된 리스트 strings와 정수 n이 주어졌을 때 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하는 함수를 작성
• strings가["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱스의 1 문자는 "u", "e", "A"로 strings를 정렬함

제한조건

• strings는 길이 1 이상 50 이하인 배열이고 원소는 소문자 알파벳으로 이루어져 있음
• strings의 원소는 길이 1 이상, 100 이하인 문자열이며 모든 strings의 원소의 길이는 n보다 큼
• 인덱스 1의 문자가 같은 문자열이 여럿 일 경우 사전순으로 앞선 문자열이 앞쪽에 위치함

입출력 예시

나의 풀이

import java.util.Arrays;

class Solution {
    public String[] solution(String[] strings, int n) {
        
        String[] answer = new String[strings.length];
        
        for (int i = 0; i< strings.length; i++) {
            answer[i] = strings[i].charAt(n) + strings[i];
        }
    
        Arrays.sort(answer);
        
        for (int i = 0; i < strings.length; i++) {
            answer[i] = answer[i].substring(1);
        }
  
        return answer;
    }
}

• String 배열을 반환하기 위해 주어진 배열의길이로 새로운 배열을 생성한다.
• 두 번째 매개변수인 n이 문제를 해결하기 위해 정렬해야 하는 strings의 각 요소인 문자열의 index이므로 반복문을 통해 strings[i].charAt(n)으로 문자열을 추출한다.
• 일단 가장 중요한것은 이 추출한 문자만 정렬해서는 원본의 문자열 배열을 정렬할 수 없기 때문에 무언가 방법이 필요했다.
• 여기서 적용한 방법은 이렇게 추출한 문자를 가장 앞에 두고 추출했던 문자열을 이어 붙여서 새로운 배열에 저장한 다음 이 배열자체를 Arrays.sort()를 활용하여 오름차순으로 정렬했다.
  
  • 문제로 주어진 문자열 배열이 ["sun", "bed", "car"]이고 n이 1이라면 "usun", "ebed", "acar"로 이루어진 문자열 배열을 Arrays.sort()로 오름차순 정렬하면 "acar", "ebed", "usun"이 된다
• 이렇게 정렬한 문자 배열을 다시한번 반복문으로 꺼내서 substring(1)로 정렬을 위해 붙였던 문자를 제거해서 다시 배열에 저장하여 이 배열을 반환하면 문제를 해결할 수 있다.

다른 풀이

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public String[] solution(String[] strings, int n) {
        Arrays.sort(strings);
        Arrays.sort(strings, Comparator.comparing((s) -> s.substring(n, n + 1)));
        return strings;
    }
}

• 새로운 배열을 생성할 필요 없이 strings를 그대로 활용하고 sort()함수에 비교자(Comparator)를 주어 문제를 가독성있고 깔끔하게 해결하는 것이 신기해서 가져왔다.
• 이 결과를 보고 내 풀이도 사실 새로운 문자열 배열을 생성할 필요가 없다는 것도 알게 되었다
• 여기서 Arrays.sort(strings)를 먼저 하는것이 처음에는 이해가 안갔는데, ai툴을 통해 물어보니 '인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치해야 함'이라는 제약 조건때문에 먼저 strings 배열에 있는 요소들을 사전순으로 배치한 다음, Comparator를 통해 비교를 해야 동일한 비교자로 비교해도 사전순으로 정렬이 되기 때문이라는 것을 알게 되었따.
• 두 번째 정렬하는 로직을 새로운 문자열을 계속 생성하는 substring()이 아니라 Arrays.sort(strings, Comparator.comparing((s) -> s.charAt(n))); 처럼 charAt(n)을 사용하면 미세하게나마 성능을 올릴 수 있다
• sort()함수를 사용할 때 원하는 비교자를 제공하는 방법은 유용할 것 같아서 몇번 연습이 필요할 것 같다

import java.util.*;

class Solution {
    public String[] solution(String[] strings, int n) {
        return Arrays.stream(strings).map(string -> new IndexString(string, n)).sorted()
            .map(indexString -> indexString.string).toArray(String[]::new);
    }

    class IndexString implements Comparable<IndexString> {

        String string;
        char index;

        IndexString(String string, int index) {
            this.string = string;
            this.index = string.charAt(index);
        }

        public int compareTo(IndexString indexString) {
            System.out.println(index+"," + indexString.index);
            if (index == indexString.index) {
                return string.compareTo(indexString.string);
            } else {
                return index - indexString.index;
            }
        }
    }
}

• 코테 문제에서 별도의 inner 클래스를 만들어서 Comparable을 구현하여 자기자신을 비교할 수 있는 객체를 만들고, 이를 Stream API를 활용해서 매우 깔끔하고 객체지향적으로 문제를 접근한 것이 신기해서 가져왔다.
• Inner class IndexString은 원래 본인의 요소인 문자열 string과 string의 n번째 요소를 문자로 저장한 index를 가지고 있으며 생성자를 통해 들어온 int index로 매개변수로 들어온 string.charAt(index)를 통해 구해진 문자를 this.index로 저장한다.
• 자기 자신을 비교할 수 있도록 Comparable 인터페이스를 구현하여 새로 구현한 compareTo(IndexString indexString)메서드는 스트림으로 변환된 문자 배열의 각 요소와 n을 매개변수로 생성된 IndexString을 매개변수로 한다
• 먼저 this.index와 비교 대상의 char index가 같다면, this.string과 indexString.string을 compareTo를 통해 오름차순 정렬한다
• 다르다면 문자열을 사전순으로 정렬할 필요가 없으므로 char index를 기준으로 this.index - indexString.index 를 통해 char index를 유니코드 값을 비교하여 오름차순 정렬한다.
• 이렇게 구현된 StringIndex를 활용하여 strings 배열을 stream으로 만들고 map()을 통해 스트림의 각 요소를 new IndexString(string, n)을 통해 모두 IndexString으로 변환하고 sorted()로 정렬한다.
• 이때 IndexString에 구현된 compareTo()가 자동으로 호출되어 작성한 로직에 따라 자신이 가진 문자열과 비교 대상의 문자열이 같으면 오름차순을, 그게 아니라면 자신이 가진 index 문자와 비교대상의 문자를 비교하여 오름차순을 진행한다.
• 그 다음 다시 map을 통해서 indexString이 가진 string 문자열을 추출하여 String으로 매핑하고 toArray()로 최종적으로 String 배열로 결과를 반환하여 문제를 해결했다.

---

K번째 수

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/42748
• 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때 , k번째에 있는 수를 구하는 문제
• 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 arraydml 2번째부터 5번째까지 자르면 [5,2,6,3]이고 이를 정렬하면 [2, 3, 5, 6]이 되며 이 배열의 3번째 숫자는 5가 됨
• 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용하여 나온 결과를 배열에 담아 return 하는 함수를 작성

제한조건

• array의 길이는 1 이상 100 이하이며 각 원소는 1 이상 100 이하임
• commands의 길이는 1 이상 50 이하이며 각 원소는 길이가 3임

입출력 예시

나의 풀이

import java.util.Arrays;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        for (int i = 0; i < commands.length; i++) {
            int start = commands[i][0];
            int end = commands[i][1];
            int target = commands[i][2];

            int tempIndex = 0;
            int[] tempArr = new int[end - start + 1];
            for (int j = start - 1; j <= end - 1; j++) {
                tempArr[tempIndex++] = array[j];
            }

            Arrays.sort(tempArr);
            answer[i] = tempArr[target - 1];
        }
        return answer;
    }
}

• 주어진 array를 commads의 각 요소를 통해 요구사항의 값을 꺼내기 위해 먼저 반복문으로 commads의 요소안에 있는 값들을 꺼내 start, end, target 변수에 저장한다.
• commands의 각 요소의 길이는 3으로 고정되어있고 각 역할이 정해져있기 때문에 0, 1, 2라는 하드코딩으로 값을 꺼냈다.
• 먼저 꺼낸 변수들을 통해 array에서 start 번째 부터 end 번째의 요소를 잘라내야하기 때문에 반복문을 통해 array의 요소를 하나씩 꺼내서 임시 저장소인 tempArr 배열에 저장했다.
• 이때 tempArr의 길이를 end - start + 1로 했는데, 만약 특정 배열의 2번째 부터 5번째까지의 값을 꺼내야 한다면 4개의 요소가 들어가기 때문에 5 - 2 = 3 + 1로 배열의 길이를 동적으로 원하는 딱 원하는 만큼만 생성하도록 했다.
• 그 다음 반복의 조건을 start - 1 부터 end - 1 값까지 반복했는데, 실제 배열의 인덱스는 0부터 시작하기 때문에 그 위치를 맞추기 위해서 start와 end에 -1 연산을 추가했다.
• 그다음 반복이 진행될 때마다 tempIndex++로 인덱스를 증가하면서 임시 배열인 temArr의 인덱스의 값을 하나씩 증가시키면서 배열을 잘라낸다
• 그다음 TimSort 로직으로 최적화된 Arrays.sort(tempArr)로 tempArr을 오름 차순으로 정렬한 후 tempArr[target - 1]로 반환할 배열에 찾은 값을 저장한다.
• 이때 마찬가지로 인데스이기 때문에 target -1을 연산했다.

다른 풀이

import java.util.Arrays;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];

        for(int i=0; i<commands.length; i++){
            int[] temp = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
            Arrays.sort(temp);
            answer[i] = temp[commands[i][2]-1];
        }

        return answer;
    }
}

• 훨씬 더 깔끔하게 copyOfRange()메서드를 통해서 가공하고자 할 배열에 인자를 집어 넣어서 원하는 배열을 얻는 방법이 있었다.
• 이러면 index 예외가 발생할 여지도 없어지고 코드도 매우 가독성이 좋아져서 매우 좋은 방법인 것 같다.
• copyOfRange()는 첫 번째 인자에 복사할 배열, 두 번째에 시작 위치, 세 번째에 끝 위치(포함되지 않음)으로 이용할 수 있다.