[Algorithm] 06.코딩 테스트를 위한 알고리즘 공부

in Study on Algorithm

문자열 압축

설명

알파벳 대문자로 이루어진 문자열을 입력받아 같은 문자가 연속으로 반복되는 경우 반복되는

문자 바로 오른쪽에 반복 횟수를 표기하는 방법으로 문자열을 압축하는 프로그램을 작성하시오.

단 반복횟수가 1인 경우 생략합니다.

입력

첫 줄에 문자열이 주어진다. 문자열의 길이는 100을 넘지 않는다.

출력

첫 줄에 압축된 문자열을 출력한다.

예시 입력 1

KKHSSSSSSSE

예시 출력 1

K2HS7E

예시 입력 2

KSTTTSEEKFKKKDJJGG

예시 출력 2

KST3SE2KFK3DJ2G2

문제 해결을 위해 생각한 방법

  1. 문자 종류를 체크해서 <문자:개수> 쌍의 LinkedHashMap만들기

  2. 입력 문자열.charAt(i)로 for문 돌면서 Map에서 해당 글자가 기존에 있었다면 <글자:기존값+1>쌍을 Map에 다시 put해주기, 없었다면 <글자:1>쌍을 put해주기

  3. <글자:개수>쌍의 글자와 개수를 각각 String형 변수 answer에 더해 이어붙이기 
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;

public class Main {

    public String solution(String input) {

        StringBuilder answer = new StringBuilder();
        Map<Character, Integer> cMap = new LinkedHashMap<>();

        for(int i = 0; i < input.length(); i++) {
            if(cMap.get(input.charAt(i)) != null) {
                cMap.put(input.charAt(i), cMap.get(input.charAt(i)) + 1);
            } else {
                cMap.put(input.charAt(i), 1);
            }
        }

        for(Entry<Character, Integer> entrySet : cMap.entrySet()) {
            if(entrySet.getValue() == 1) {
                answer.append(entrySet.getKey());
            } else {
                answer.append(entrySet.getKey()).append(entrySet.getValue());
            }
        }
        return answer.toString();
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        String answer = main.solution(input);
        System.out.println(answer);
    }
}

이런 식으로 시도했는데 오답 처리가 되었다. 문제를 제대로 읽지 않고 예시에 있는 KKHSSSSSSSE가 K2HS7E이 되는 입출력 결과만 보고 해결 방법을 떠올렸는데 문제를 다시 보니 ‘같은 문자가 연속으로 반복되는 경우’에만 해당 문자의 반복 횟수를 표기하는 문제였다.

KSTTTSEEKFKKKDJJGG이 입력되면 KST3SE2KFK3DJ2G2값이 출력되어야 하는데 나는 전체 문자열 안에서 해당 문자의 개수를 세었기 때문에 K5S2T3E2FDJ2G2와 같은 값을 출력했고 오답 처리가 된것이다.

정답을 얻기 위해 다시 생각한 방법

문자에 해당하는 개수를 지정할 때 해당 문자를 기준으로 전체 문자열에서 해당 문자가 몇개 있는지 세는 것이 아니라 앞 문자를 기준으로 조건문을 만들어서 앞 문자와 같은 문자면 개수를 세는 방식으로 수정해야 한다.

뒷문자와 다르면 개수 세는 행위를 멈추고, 이전문자, 현재문자, 다음문자를 비교해 가면서 반복문을 수행하는 방식으로 시도해 보았다.

import java.util.Scanner;

public class Main {

    public String solution(String input) {

        char c = input.charAt(0);
        StringBuilder answer = new StringBuilder("" + c);
        int n = 1;

        char before = input.charAt(0);
        char it = input.charAt(1);
        char after = input.charAt(2);

        for(int i = 0; i < input.length() - 1; i++) {
            if (i == input.length() - 2) {
                after = input.charAt(input.length() - 1);
            } else if (i < input.length() - 2){
                it = input.charAt(i + 1);
                after = input.charAt(i + 2);
            }

            if (before != it && it == after) {
               if(i == input.length() - 2) {
                   answer.append(it).append(n);

               }
                n++;
                continue;
            } else {
                if (n != 1) {
                    answer.append(it).append(n);
                } else {
                    answer.append(it);
                }
            }

            n = 1;
            before = input.charAt(i + 1);

        }
        return answer.toString().toString();
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        String answer = main.solution(input);
        System.out.println(answer);
    }
}

그렇지만 이 코드도 오답이 나왔다. answer에 우선K를 넣어놓고 시작하기 때문인지 아니면 다른 문제 때문인지 처음에 등장하는 문자가 연속될 경우에는 개수를 세지 못한다.

성공 코드

디버깅 하면서 주먹구구식으로 안될때마다 코드를 이리저리 바꿔가며 해결했기 때문에 이전에 왜 안되었고 지금 왜 동작한 건지 알 수 없다. 이런 식으로 푸는건 좋은 방법이 아닌것 같고 로직을 정해두고 구체화 해가면서 풀어야 할것 같다.

import java.util.Scanner;

public class Main {

    public String solution(String input) {
        StringBuilder answer = new StringBuilder();
        int n = 1;
        char before = 0;
        char it = input.charAt(0);
        char after = input.charAt(1);

        for(int i = 0; i < input.length(); i++) {
            if (i > 0 && i < input.length() - 2){
                it = after;
                after = input.charAt(i + 1);
            } else if (i == input.length() - 2) {
                it = after;
            } else if (i == input.length() - 1) {
                after = 0;
            }

            if (before != it && it == after) {
               if(i == input.length() - 1) {
                   answer.append(it).append(n);
               } else {
				n++;
				continue;
               }
            } else {
                if (n != 1) {
                    answer.append(it).append(n);
                } else {
                    answer.append(it);
                }
            }
            n = 1;
            before = it;
        }
        return answer.toString();
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        String answer = main.solution(input);
        System.out.println(answer);
    }
}

그런데 이것이 정답인줄 알았는데 정답이 아니었다. 코드를 정리하기 위한 차원에서 고치고 있었는데,

KKHSSSSSSSE

와 같은 값을 넣었을 때 결과값으로 K2HS7E가 나와야 하는데, K2HS8값이 나온다는 것을 알게 되었다. 채점 사이트에서 정답 처리가 된 이유는 입력 예시 중 해당 값이 없었기 때문이었다.

그래서 우선 원래 의도대로 코드를 정리한 다음 이 부분을 수정하려고 했는데, 또 웬일인지 정리된 코드로는 제대로 동작했다. 하다가 뭔가 틈이 있던 로직이 메꿔졌나 보다. 그렇다는것은 1)코드를 그대로 바꾸는데 실패했다는 것이고 2)아직도 뭐가 문제인지 파악이 안되고 있다는 것이다.

다시 수정한 최종 성공 코드

import java.util.Scanner;
  
public class Main {
  
   public String solution(String input) {
        StringBuilder answer = new StringBuilder();
        int n = 1;

        char before = 0;
        char it = input.charAt(0);
        char after = input.charAt(1);

        for(int i = 0; i < input.length(); i++) {
            if (i != 0){
                it = after;
                 if (i != input.length() - 1) {
                    after = input.charAt(i + 1);
                } else {
                    after = 0;
                }
            }
            if (before != it && it == after) {
                n++;
                continue;
            } else {
                if (n != 1) {
                    answer.append(it).append(n);
                } else {
                    answer.append(it);
                }
            }
            n = 1;
            before = it;
        }
        return answer.toString();
    }
  
  public static void main(String[] args){
    Main main = new Main();
    Scanner sc = new Scanner(System.in);
    String input = sc.next();
    String answer = main.solution(input);
    System.out.println(answer);
  }
}

강사님 풀이법

내용이 정리도 잘 안되고 내가 너무 복잡하게 푼것 같아서 강사님의 풀이법도 들어 보았다. 강사님이 설명해주시는 방식은

앞문자와 뒷문자를 비교해서 같으면 cnt값을 올려주고 같지 않은 순간 해당 문자와 숫자를 출력하면서(단 cnt가1일때는 문자만 출력되도록 조건절을 넣었다) cnt를 다시 1로 만들어 주고,

반복문 안에서 i가 입력받은 문자열의 길이가 될때까지 이 동작을 반복하는데, i와 i+1을 비교해 나가면서 마지막i, i+1가 될 때 문자열.length를 넘어서서 ArrayIndexOutOfBoundsException이 발생하는 것을 방지하기 위해

반복문을 돌기 전 입력받은 문자열 맨 뒤에 공백 문자열을 넣어준다.

public String teacherSolution(String input) {
        StringBuilder answer = new StringBuilder();
        input = input + "";
        int cnt = 1;
        for (int i = 0; i < input.length() - 1; i++) {
            if (input.charAt(i) == input.charAt(i + 1)) {
                cnt++;
            } else {
                answer.append(input.charAt(i));
                if (cnt > 1) {
                    answer.append(cnt);
                }
                cnt = 1;
            }
        }

나는 before, it, after라는 세 개의 변수를 만들고 현재 문자와 앞 문자까지 비교해가면서 조건을 걸었는데 강의를 듣고 생각해보니 이전 문자와도 비교하는 로직이 왜 필요했는지 과거의 나자신을 이해할수 없다는 생각이 들었다. 그래서 before를 없애봤더니 이 코드 역시 채점사이트에서 정답 처리가 되었다.

public String solution(String input) {
        StringBuilder answer = new StringBuilder();
        int n = 1;

        char it = input.charAt(0);
        char after = input.charAt(1);

        for(int i = 0; i < input.length(); i++) {
            if (i != 0){
                it = after;
                if (i != input.length() - 1) {
                    after = input.charAt(i + 1);
                } else {
                    after = 0;
                }
            }
            if (it == after) {
                n++;
                continue;
            } else {
                if (n != 1) {
                    answer.append(it).append(n);
                } else {
                    answer.append(it);
                }
            }
            n = 1;
        }
        return answer.toString();
    }

정리

내가 최종적으로 정리한 코드와 강사님 방식대로 만들어본 코드를 비교해보자면, 우선 나는 i번째 문자와 i +1번째 문자를 변수로 만들어놓고 비교를 하고자 했고, 개수를 제대로 세려면 앞문자와 뒷문자가 같을때는 continue문 아닐때는 append를 하는 식으로 짜야 한다고 생각했는데

그냥 반복문 안에서 개수를 늘려주다가 뒷문자와 같지 않게 되면 자연스럽게 answer에 이어붙여 주면 되는 거였고

이어붙여 줄 때도 나같은 경우 개수가 1이 아닐때와 1일 때를 나누어서 append를 했다면 강사님은 어차피 append로 이어붙이는 부분이니 기본적으로 문자를 이어붙이게 하고 여기서 개수가 1이냐 아니냐에 따라 개수를 더해줄지 말지 결정하는 방식으로 진행하셨다.

반복문이 문자열의 끝까지 진행되었을 때 i + 1을 조회하고자 할 때 발생하는 ArrayIndexOutOfBoundsException을 방지하기 위해서도 i가 되었을 때 비교할 문자를 임의의 문자 0으로 넣어주었는데, 입력받은 문자열 뒤에 공백문자를 넣고 시작하는 방법도 있다는 것을 알게 되었다.

여러 모로 삽질을 많이 했기에 문제를 해결하는 절차에 대해서도 다시 생각해 보게 된 문제였다. 문제를 보고 바로 코딩을 하지 말고 기록할 수 있는 공간에 기록을, pc를 통해 텍스트로 정리하는 방식으로도 감이 안잡힌다면 종이에 직접 적어서라도 전체적인 진행 방향을 정리해 놓고 시작하는 습관이 필요하겠다.


© 2021.1. by jean202

Powered by jean202