부분수열이 중복되지 않는 특정한 문자열 생성

문제

1, 2, 3으로만 이루어진 수열 바코드를 만들어야 하며 바코드에서 인접한 두 개의 부분 수열이 동일하다면 제작할 수 없다고 할 때, 주어진 길이 len의 바코드 중 가장 작은 수를 반환하는 함수를 작성.

 

 

만들 수 없는 바코드	만들 수 있는 바코드
112	1312
1231312	3
232312	231213

• 부분 수열? 주어진 수열에서 연속된 모든 구간을 말합니다. 수열 123의 부분 수열은 1, 2, 3, 12, 23, 123.
• 인접한 두 부분 수열? 첫번째 부분 수열과 두번째 부분 수열이 연속된 경우.
• 수열 1234에서 인접한 부분 수열 (우리는 두 부분수열이 같은지 관심이 있으므로 길이가 서로 다른 경우는 무시한다)
  • 1과 2, 2와 3, 3과 4, 12와 34
• 만들 수 없는 바코드:
  • '11'2
  • 12'3131'2
  • '2323'12 인접한 두 개의 부분 수열이 동일하기 때문에 만들 수 없다. 고로, '12131213'과 같이 네 자리씩 중복되어도 만들 수 없다. 자릿수와 상관없이, 인접한(붙어있는) 부분 수열이 같다면 바코드를 만들 수 없다.

 

입력

• int타입의 1이상 50이하의 자연수

 

 

출력

• String 타입을 리턴
• 만들수 있는 바코드중 제일 작은수를 반환

 

 

입출력 예시

String output = barcode(3);
System.out.println(output); // "121"

output = barcode(7);
System.out.println(output); // "1213121"

output = barcode(20);
System.out.println(output); // "12131231321231213123"

 

 

풀이

class Solution {
    public String barcode(int len) {
        return aux("",len); // 재귀를 위해 첫번째 매개변수를 문자열타입으로 지정
    }

    String aux(String str, int len){
        String[] chars = new String[]{"1","2","3"};
        //바코드의 구성은 1,2,3으로만 이루어저있으며 반복문을 위해 배열로 초기화
        
        if(str.length()==len) return str; // base case

        for(String cha : chars){ 
        // 사용할수 있는 바코드중 제일 작은값을 구해야하므로 제일 작은 값인 1부터
        // 검증한 뒤 검증이 완료되면 해당 문자를 매개변수에 더해준뒤 재귀 호출
        
            String testStr = str+cha;
            if(isValid(testStr)){ 
            // 검증을 위한 메서드, 검증이 완료되면 재귀 호출
            // 검증에 실패한다면 다음 숫자를 가지고와 계속 검증
            
                String validStr = aux(testStr,len);
                // 검증이 완료되면 재귀를 호출하여 1~3까지의 숫자를 한개씩 붙여 계속 검증;
                
                if(validStr != null) return validStr;
                //검증에 실패하면 밑에 null이 반환되며 향상된 for문을 계속 실행하게됨
                // 검증이 마지막까지 성공하면 base case를 통해 완성된 바코드를 반환
            }
        }
        return null;
    }

    boolean isValid(String str){
        StringBuffer sb = new StringBuffer(str);
        String reversed = sb.reverse().toString();
        int halfLen =  str.length() / 2;

        for(int i = 1; i<=halfLen; i++){
            if(reversed.substring(0,i).equals(reversed.substring(i,i*2)))  return false;
        }
        return true;
    }// 검증 메서드는 재귀적으로 한글자씩 추가된 문자열이 반복적으로 매개변수로 전달받으며
    //해당 문자열의 순서를 반전시킨뒤 문자열을 반으로 갈라 두 문자열로 만들어 비교한뒤
    // 값이 동일하다면 false, 이후 다음 문자를 가저와 새로운 문자열로 전달받은뒤 반복실행
}

 

전체적인 흐름은 이해했지만 세부적인 로직은 아직 조금 햇갈린다....