DeJa
Techvu
DeJa
전체 방문자
48,644
오늘
4
어제
65
  • Techvu (60)
    • DesignPatterns (3)
      • 생성 (0)
      • 구조 (1)
      • 행동 (2)
    • Refactoring (0)
    • DataStructures (0)
    • Algorithms (24)
      • 기본 지식 (12)
      • 문제 풀이 (12)
    • OOP (0)
    • TDD (2)
    • DDD (0)
    • Programming Languages (9)
      • Java (9)
      • Kotlin (0)
    • Spring (1)
    • JPA (7)
    • Web (1)
      • 기본 지식 (1)
      • 실무 경험 (0)
    • CS (12)
      • Network (1)
      • OS (8)
      • DataBase (3)
      • Server (0)
    • Git (1)
    • Conferences (0)

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

  • Study
  • GitHub
  • Medium Blog

인기 글

  • 자바 버전별 역사 및 특징
    2022.01.12
    자바 버전별 역사 및 특징
  • 깃허브 사용 방법
    2021.12.15
    깃허브 사용 방법
  • 스키마(Schema)
    2022.01.08
    스키마(Schema)
  • 동시성 이슈(Concurrency Issue)
    2022.03.20
    동시성 이슈(Concurrency Issue)
  • 재귀 함수(Recursion Function)
    2021.12.08
    재귀 함수(Recursion Function)

태그

  • JPA
  • CS
  • Spring
  • 디자인패턴
  • java
  • DATABASE
  • web
  • TDD
  • 알고리즘
  • network
  • OS

최근 댓글

  • 글 잘읽고 가요.
    아이폰
  • 컴파일러자체에서 꼬리재귀를 지원하지 않으니 static으로⋯
    aaa
  • 압도적 감사
    ㅇㅇㅇ

최근 글

  • Write a test code right now
    2022.03.24
    Write a test code right now
  • 동시성 이슈(Concurrency Issue)
    2022.03.20
    동시성 이슈(Concurrency Issue)
  • POJO, JavaBean, Entity, VO, DTO
    2022.02.08
    POJO, JavaBean, Entity, VO, DTO
  • TDD with Agile
    2022.02.05
    TDD with Agile
  • Java Stream 기초
    2022.01.23
    Java Stream 기초

티스토리

hELLO · Designed By 정상우.
DeJa

Techvu

2020 카카오 신입 공채 : 문자열 압축
Algorithms/문제 풀이

2020 카카오 신입 공채 : 문자열 압축

2022. 1. 18. 18:17
728x90

문자열 압축

프로그래머스 문자열 압축

해설

aabbaccc -> 2a2ba3c
s 의 길이는 1 <= s <= 1000
s 는 알파벳 소문자로만 이루어져 있음
문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return

min (1개단위로 잘랐을 때의 결과 vs 2개 ..)
min (2개단위로 잘랐을 때의 결과 vs 3개 ..)
...

압축 최대 효율은 -> 2 * 반복되는 문자열

압축 최대 효율은 2번 압축 되는 경우 가장 짧은 문자열로 압축이 된다.

1개 단위로 반복되는 문자를 압축하는 경우

* 예시 입력 1
* KKHSSSSSSSE
*
* 예시 출력 1
* K2HS7E
// i 번째랑 i + 1 번째의 문자를 비교한다.
public String solution2(String s){
    String answer="";
    s=s+" ";
    int cnt=1;
    for(int i=0; i<s.length()-1; i++){
        if(s.charAt(i)==s.charAt(i+1)) cnt++;
        else{
            answer+=s.charAt(i);
            if(cnt>1) answer+=String.valueOf(cnt);
            cnt=1;
        }
    }
    return answer;
}

구현

1개 단위로 반복되는 문자를 압축하는 경우의 로직을 가지고, 이중 반복문을 생각하여 구현하면 된다.

public class Solution {

    static int answer;

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

    public static int solution(String alphabet) {
        // 구하고자하는 답을 원본 문자열의 길이로 초기화
        answer = alphabet.length();

        // 1 ~ alphabet.length/2 만큼의 단위로 문자열 자르기
        for (int i = 1; i <= alphabet.length() / 2; i++) {
            int count = 1;

            // i 개 단위로 자른 문자열
            String current = alphabet.substring(0, i);
            StringBuilder stringBuilder = new StringBuilder();

            // i 개 단위로 잘린 현재 문자열(current) 와 비교하기 위한 next 문자열 구하는 반복문
            for (int k = i; k < alphabet.length(); k = k + i) {
                int nextLastIndex = Math.min(k + i, alphabet.length());
                String next = alphabet.substring(k, nextLastIndex);

                if (current.equals(next)) {
                    count++;
                } else {
                    appendToStringBuilder(stringBuilder, count, current);
                    count = 1;
                    current = next;
                }
            }

            // Ex. alphabet 길이가 16이고 3개 단위로 자른다고 했을때, 내부 반복문의 k 값은 15 까지만 가능함.
            // 따라서 내부 반복문 끝나면 한 번더 남은 문자열을 붙여줘야 함
            appendToStringBuilder(stringBuilder, count, current);

            answer = Math.min(answer, stringBuilder.length());
        }

        return answer;
    }

    static void appendToStringBuilder(StringBuilder stringBuilder, int count, String str) {
        if(count > 1) {
            stringBuilder.append(count);
        }
        stringBuilder.append(str);
    }
}
728x90
저작자표시 비영리 동일조건
  • 카카오스토리
  • 트위터
  • 페이스북

'Algorithms > 문제 풀이' 카테고리의 다른 글

이것이 코딩 테스트다 : 편집 거리  (0) 2022.01.18
[BOJ 18353] 병사 배치하기  (0) 2022.01.11
이것이 코딩테스트다 : 금광  (0) 2022.01.07
[BOJ 14502] 연구소  (0) 2022.01.06
[BOJ 15686] 치킨 배달  (0) 2022.01.03
    'Algorithms/문제 풀이' 카테고리의 다른 글
    • 이것이 코딩 테스트다 : 편집 거리
    • [BOJ 18353] 병사 배치하기
    • 이것이 코딩테스트다 : 금광
    • [BOJ 14502] 연구소
    알고리즘
    DeJa
    DeJa
    Tech Blog
    댓글쓰기
    이것이 코딩 테스트다 : 편집 거리
    이전 글
    이것이 코딩 테스트다 : 편집 거리

    티스토리툴바