[Java]goormtest(구름TEST) 이진압축

안녕하세요 Leo 입니다.

 

이번 소개해줄 알고리즘 사이트는 구름TEST 라는 사이트 인데요,

 

NHN에서 투자 받아 개발한 알고리즘 사이트 입니다.

 

회사면접 코딩테스트를 하는 유명한 사이트죠...

 

저는 IOS (Object-c , Swift) 위주로 개발을 하고 가끔 안드로이드 개발을 하는데요...

 

 

회사에서 Java 로 코딩테스트를 하라고 해서 ... 하라면 해야죠... 풀어봤습니다.

 

제가 20문제 이상 푼것 같은데 이걸 공유 해드리도록 하죠...

 

 

이 글이 누군가에겐 "약"이 되고 누군가에겐 "독"이 될 것이다.

개발자라면 적어도 기본 알고리즘 정도는 스스로 학습하여 풀어봐야 한다.참고로 코딩테스트 문제를 제출 한 심사위원 분도제 블로그에서 답을 확인 한다는 것을 역으로 알아두고 보세요!! ㅎㅎ

 

 

 

알고리즘 문제

 

문제 : [템플릿] 이진 압축

이진 압축은 0 또는 1로 이루어진 길이가 2^k인 문자열에 대해서, 모두 같은 문자가 될 때까지의 크기가 2^(k-1)인 두 그룹으로 분할하여 모두 같은 문자가 되도록 하는 과정으로 암호화를 합니다.

예를 들어보면 길이가 4인 '1101'을 압축하는 과정은 모든 문자가 같지 않기 때문에 '11 01'로 먼저 분할하고 다시 뒷부분은 '0 1'로 분할해야 합니다.

이렇게 만들어진 압축본은 '-1-01"이 됩니다.

- : 먼저 전체를 분할하고

1 : 분할된 왼쪽 부분은 모두 1이고

- : 오른쪽 분할은 다시 분할하며,

01 : 분할된 결과는 0과 1이라는 의미이다.



길이가 n인 원본을 압축본으로 출력하는 프로그램을 작성하십시오.



입력

첫 줄에 이진 문자의 길이 n

두 번째 줄에 길이가 n인 0, 1로 구성된 이진 문자열이 입력된다.

출력

만들어진 압축본




입/출력 예시
⋇ 입출력 형식을 잘 지켜주세요.
␣ : 공백
↵ : 줄바꿈
−⇥ : 탭
보기 입력 1
4
1101
출력 1
-1-01

보기 입력 2
8
00111101
출력 2
--01-1-01

 

 

======================================================================================================

풀이

======================================================================================================

 

//Please don't change class name 'Main'
import java.util.Scanner;

/**
문제 이해가 어려웠다.

문제 해결방법(조건)
0.분할할때마다 "-" 들어간다.
1.전체 분할을 하고
-0011/1101
2.왼쪽부분부터 분할을 한번더 하고
--00/11/1101
3.값이 같으니 같은 값으로 표시
--01/1101
4.다시 1101을 분할 하고
--01-11/01
5. 같은값이면 그대로 하고 아니면 분할하고
--01-1-0 1
6. 결과는
--01-1-01

이해 완료.
*/

class Main {
	
  public static void main(String[] args) {

		String count,binaryNum;
		Scanner scan = new Scanner(System.in);
		
		count = scan.nextLine();
		binaryNum = scan.nextLine();
		int nLength = Integer.parseInt(count);
		
		 String[] binaryArr = binaryNum.split("");
		
		String returnStr ="";
		Boolean isCombine = false;
		for(int i=0; i < nLength; i++){
			
				if(i % 4 == 0){
					returnStr = returnStr + "-";
				}
			
				if(i % 2 == 1){

					if(binaryArr[i-1].equals(binaryArr[i])){
						
						returnStr = returnStr.substring(0,returnStr.length()-1);
						returnStr = returnStr + binaryArr[i-1];

					}else{
						returnStr =  "-" + returnStr + binaryArr[i-1] + binaryArr[i];
					}

				}else{
					
					if(i == 0){
						if(nLength > 4){
							returnStr = returnStr + "-";	
						}
					}else{
						returnStr = returnStr + "-";	
					}
						
				}
		}
		System.out.print(returnStr);
	
	}
}

 

 

참고로 점수는 높은 점수는 아닙니다. 

 

일단 푸는 거에 집중했으니 알고리즘에 정답은 없습니다.

 

더 좋은 알고리즘을 만들어 내는게 목표 입니다.

 

 

알고리즘에 대하여 더 이야기 하실분은 댓글남겨주세요!

 

 

 

 

 

 

 

구름TEST 화면

 

 

 

 

https://codingtest.goorm.io/

구름TEST - 개발자 채용을 위한 코딩 테스트, 프로그래밍 시험

 

구름테스트, 구름TEST 가 지원하는 프로그래밍 언어

 

그 외 Scala, Pascal, Lua, Objective-C, Rust, Cobol, Clojure, Smalltalk, Dart, Haskell, Perl, Common Lisp, D, Erlang 등 

 

 

 

구름테스트, 구름TEST 를 2019년 현재 적용중인 회사