2024년 정보처리기사 실기 2회 17번 문제 공부 및 풀이

class Main {
    public static void main(String[] args) {
        String str = "abacabcd";
        boolean[] seen = new boolean[256];
        System.out.print(calculFn(str, str.length()-1, seen));
    }

    public static String calculFn(String str, int index, boolean[] seen) {
        if(index < 0) return "";
        char c = str.charAt(index);
        String result = calculFn(str, index-1, seen);
        if(!seen[c]) {
            seen[c] = true;
            return c + result;
        }
        return result;
    }
}

 

 

풀이 흐름

1. 입력 문자열
   "abacabcd" 라는 문자열 줌
2. boolean 배열 초기화
   seen = new boolean[256];
   → 아스키 코드 기준으로 각 문자가 이미 등장했는지 기록하는 용도임
3. 재귀 호출
   calculFn(str, str.length()-1, seen) 실행
   → 문자열 끝에서부터 한 글자씩 거꾸로 확인하면서 새로운 문자만 남김
4. 동작 과정
   • index = 7 → 'd' 아직 안 나옴 → d 추가
   • index = 6 → 'c' 아직 안 나옴 → cd
   • index = 5 → 'b' 아직 안 나옴 → bcd
   • index = 4 → 'a' 아직 안 나옴 → abcd
   • index = 3 → 'c' 이미 있음 → 스킵
   • index = 2 → 'a' 이미 있음 → 스킵
   • index = 1 → 'b' 이미 있음 → 스킵
   • index = 0 → 'a' 이미 있음 → 스킵
5. 최종 결과
   출력값 → "abcd"

calculFn(str, 7)  ──> c = 'd'
   └ calculFn(str, 6)  ──> c = 'c'
       └ calculFn(str, 5)  ──> c = 'b'
           └ calculFn(str, 4)  ──> c = 'a'
               └ calculFn(str, 3)  ──> c = 'c' (이미 나옴)
                   └ calculFn(str, 2)  ──> c = 'a' (이미 나옴)
                       └ calculFn(str, 1)  ──> c = 'b' (이미 나옴)
                           └ calculFn(str, 0)  ──> c = 'a' (이미 나옴)
                               └ calculFn(str, -1)  ──> ""

 

 

 

결과 합치기 과정

• index=7 → 'd' 추가 → "d"
• index=6 → 'c' 추가 → "cd"
• index=5 → 'b' 추가 → "bcd"
• index=4 → 'a' 추가 → "abcd"
• index=3 → 'c' 이미 있음 → "abcd" 유지
• index=2 → 'a' 이미 있음 → "abcd" 유지
• index=1 → 'b' 이미 있음 → "abcd" 유지
• index=0 → 'a' 이미 있음 → "abcd" 유지

 

 

한줄평

재귀 함수를 봐도 정신만 차리면 풀수있다.

 

출처

https://chobopark.tistory.com/483#google_vignette