#쉽게 푸는 알고리즘 #1 [연속되는 문자열 압축]

안녕하세요 J.sieun 입니다.

쉽게 생각하고 쉽게 풀어쓰는 알고리즘 제 1탄이 되겠습니다 :)

이 콘텐츠는 "개강" 전까지 이틀에 하나씩 올리도록 하겠습니다. 

//와..생각하는것도 힘들듯..

개강하고는 C# 이나 C++ 도 올리겠습니다. 

//우선 가장 많이 배운다고 생각되는 언어가 "Java"라고 생각하기 때문에  자바 부터 올립니다. 이점 양해바랍니다.) 

서론이 길었는데요. 

바로 본론으로 들어가도록 하겠습니다. 

연속되는 문자열을 가지고 압축하는 알고리즘이란? 예를 들면 

"안녕녕녕녕하세요요요" 

이런식의 문자열이 있으면

"안1녕4하1세1요3" 

이런식으로 반복되는 문자열을 하나로 합쳐서 보여주게 하는 것을 문자열 압축이라고 합니다. 

이러한 알고리즘을 하나하나 설명해보도록 하겠습니다.(연속하는 문자열 20단어까지)

출력화면과 소스를 먼저 보도록 하겠습니다. 

import java.util.Scanner;

public class blogClass {

static String _InputArr [] = null;

static char _CapsuleArr[] = new char[20];

static String _OutputArr[] = null;

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner scanner = new Scanner (System.in);

System.out.println("http://jsieun73.tistory.com/");

System.out.println("몇번 하실건가요??");

int count = scanner.nextInt();

_InputArr = new String[count];

_OutputArr = new String[count];

for(int i=0; i< count; i++)

{

_OutputArr[i] = "";

_InputArr[i] = scanner.next();

}

capsuleEvt();

}

static void capsuleEvt() {

for (int i = 0; i < _InputArr.length; i++) {

// 초기화&char형으로집어넣기

int cnt = 0;

while (cnt < _CapsuleArr.length) {

_CapsuleArr[cnt] = 0;

if(_InputArr[i].length() > cnt)

{

//string배열 하나를 char형배열 하나하나에 집어 넣기.

_CapsuleArr[cnt] = _InputArr[i].charAt(cnt);

}

cnt++;

}//_CapsuleArr 반복문

cnt = 0;

int counting = 1;

while(_CapsuleArr[cnt] != 0)

{

//앞에 문자와 바로뒤 문자가 같을시.

if( _CapsuleArr[cnt + 1] == _CapsuleArr[cnt])

{

counting++;

}

else if(_CapsuleArr[cnt + 1] != _CapsuleArr[cnt]){

_OutputArr[i] += "" + _CapsuleArr[cnt] + "" + counting; 

counting = 1;

}

cnt++;

//마지막에 총 몇개의 문자열인지?

if(_CapsuleArr[cnt] ==0)

{

_OutputArr[i] += " " + cnt;

}

}

System.out.println("OutPut:: " + (i +1));

System.out.println(_OutputArr[i]);

//스페셜 난이도

specialEvt();

}//_InputArr 반복문

}//capsuleEvt 괄호

static char _SpecialArr [] = new char [21];

static String _SpecialOutput = "";

static void specialEvt(){

//의미없지만 좀더 확인하기 쉽게.

for(int i=0; i< _CapsuleArr.length; i++)

{

_SpecialArr [i] = _CapsuleArr[i];

}

for(int i =0; i<_SpecialArr.length; i++)

{

for(int j=0; j<_SpecialArr.length - 1; j++)

{

if(_SpecialArr[j] > _SpecialArr[j + 1])

{

char _order = _SpecialArr[j + 1];

_SpecialArr[j + 1] = _SpecialArr[j];

_SpecialArr[j] = _order;

}

if(_SpecialArr[j] ==0)

{

break;

}

}

}//반복문

int counting = 1;

_SpecialOutput = "";

for(int i=1; i<_SpecialArr.length - 1; i++)

{

if(_SpecialArr[i] == _SpecialArr[i+1])

{

//같으면

counting++;

}

else if(_SpecialArr[i] != _SpecialArr[i +1] && _SpecialArr[i] !=0)

{

_SpecialOutput += _SpecialArr[i] + "" + counting;

counting = 1;

}

}

System.out.println("Special OutPut ::" + _SpecialOutput);

}//specialEvt 괄호

}

우선 소스는 위와 같습니다.

그럼 하나하나 소스해석을 해보도록 하겠습니다. 

#1 메인함수(main) ☆☆☆☆★

여기는 몇번 압축할건지에 대해서 묻고 그거에 따라서 _InputArr 과 _OutputArr 배열의 크기값

넣고 그것들을 capsuleEvt 함수가 처리해주는 부분이 되겠습니다. 

#2 capsuleEvt 메소드 ☆★★★★

여기에서 연속된 문자열을 압축해주는 메소드가 되겠습니다.

#2.0 (☆☆☆☆★)

" for (int i = 0; i < _InputArr.length; i++) "

이 반복문은 내가 몇번 압축알고리즘을 사용할건지에 따라서 반복하게됩니다.

#2.1 (★★★★★)

이 반복문은 C++ 식으로 해석하면 "memset" 함수를 사용한 것입니다.

즉, _CapsuleArr 배열을 다음 문자열들을 받기전에 깨끗이 청소한다고 생각하시면 되겠습니다. :)

#2.2 (☆★★★★)

"이 반복문은  이 포스팅의 메인 주제인 "연속되는 문자열"을 분석해주는 반복문이 되겠습니다.

주석처리로 설명한것처럼 앞에 단어와 바로 뒤에 단어가 같으면 counting 이 1씩증가하게 되고

다를시에는 counting 이 초기화(1) 가 되면서 출력문에 누적해서 값들이 저장되는 식인 알고리즘이 

되겠습니다."

#3 specialEvt 메소드 ★★★★★

이 메소드는 capsuleEvt 메소드 중간에 호출되는 메소드인데요. 물론 capsuleEvt 메소드에서 

이미 연속되는 문자열 압축 알고리즘은 처리가 되었습니다. 하지만, 여기서 한번더 생각을 더 꼬아서

"전체 문자열들 중에 반복되는 문자열들을 한꺼번에 묶고(몇번 반복했는지)  또한, 

그것들을 오름차순 (가->하) 으로 정렬하면 어떨까?" 

라는 생각으로 한번 만들어 보았습니다.

방법은 정말 간단합니다. 우선 오름차순으로 정렬하게 되면, 연속되는 문자열들이 한꺼번에 정리가 됩니다.  그 후에 몇번 반복한 문자열인지를 중간중간에 숫자로 끼어넣으면 되겠습니다. 

#3.0 (★★★★★)

이 메소드는 오르차순 알고리즘이 되겠습니다. 

i 와 j 는 i 가 3일때에는  j 는 0,1,2 이런식으로 반복하게 되는 반복문이고,

안에 조건문에서는 "아스키 코드" 기준으로 "앞에 단어" 가 "뒤에 단어" 보다 클때 

앞에 단어와 뒤에 단어를 바꿔주는 부분이 되겠습니다. 

그리고 또다른 조건문에서 " _SpecialArr[j] == 0 " 이부분은  애초에 _CapsuleArr 이란 배열에서 문자열이 끝나면 '0' 을 처리하도록 하였습니다. 즉, 저 2차 반복문이 무의미한 진행을 막기 위해서 조건문을 하나 걸어서 

그 반복문을 빠져나오도록 하였습니다. 

#3.1 (☆★★★★)

이부분은 연속되는 문자열 중간중간에 얼만큼 단어들이 연속했는지를 출력할수있도록 도와주는 

반복문이 되겠습니다. 

첫번째 조건문에서 "앞에 단어" 와 "바로 뒤에 단어" 가 같을시에는 counting 이라는 변수가 1씩증가하게 되고, 

만약에 다를시에는 _SpecialOutput 문자열을 누적해서 counting 과 연속된 배열의 값을 저장한 후   counting 변수를 초기화 합니다. 

이상 소스해석은 여기서 마치도록 하겠습니다. 혹시나 기타 궁금하신 사항이 있으면 

j.sieun73@gmail.com 여기로 메일 보내주시길 바랍니다. 

//중간중간에 제가 배열을 초기화 하거나 복사하는 부분에서 다른 부분보다 좀더 높게 중요도를 칠한게 있는데 

그 이유는 제가 생각하기에는 배열을 초기화 하거나 복사하는 것은 이러한 알고리즘 보다 훨씬 중요하다고 생각이 들어서 입니다. 정말 간단하고 별거 아니지 않나?? 라는 생각이 들수 있지만, 

나중에는 메모리 초기화 메모리 복사 메모리 리셋 이러한 것들을 제대로 안해주면 데이터 값들이 혼합되거나 전혀 다른 값들이 출력이 되기때문에 제가 생각하기에는 "초기화" 처리가 알고리즘보다 훨씬 중요하다고 생각이 들어서 중요도를 다른 부분보다 높게 칠했습니다. 

이상 포스팅을 마치도록 하겠습니다. :)