[정보처리기사] [Java] 문자열 중복 제거 | 재귀 알고리즘 | 2024년 2회 정보처리기사 실기 기출문제

2024년 2회 정보처리기사 실기 기출문제

문제

다음 Java 코드를 실행했을 때 출력 결과를 쓰시오.

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;
    }
}

정답

dcba

반응형

---

해설

1️⃣ 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 void main(String[] args) {

• 프로그램의 진입점인 main() 메서드입니다.

  String str = "abacabcd";

• 문자열 str에 "abacabcd"를 저장합니다.
• 이 문자열의 각 문자에 대해 중복 여부를 검사하고, 결과 문자열을 만들게 됩니다.

   boolean[] seen = new boolean[256];

• seen이라는 이름의 boolean 타입 배열입니다.
• boolean은 참(true) 또는 거짓(false)의 값을 가지는 자료형입니다.
• 배열의 크기를 256으로 설정한 이유는 바로 ASCII 문자 체계 때문입니다. ASCII(아스키)는 문자를 숫자로 표현하는 규칙이고, 총 256개(0 ~ 255)의 문자 코드가 정의되어 있습니다. 즉, 모든 ASCII 문자(영문자, 숫자, 특수문자 포함)를 다룰 수 있도록 배열 크기를 256으로 설정한 것입니다.
  • 'a' → ASCII 코드 97
  • 'A' → ASCII 코드 65
  • '0' → ASCII 코드 48
  • '!' → ASCII 코드 33 등
• Java에서 boolean[] 배열을 생성하면, 모든 요소가 자동으로 false로 초기화됩니다.

      System.out.print(calculFn(str, str.length() - 1, seen));

• calculFn()을 호출하고 결과를 출력합니다.
• str : 문자열 "abacabcd"입니다. 이 문자열을 한 글자씩 분석하기 위해 전달합니다.
• str.length() - 1 : str.length()는 문자열의 길이 → "abacabcd"는 8글자 → 8, - 1을 하면 7
• seen : boolean[] seen = new boolean[256]; 배열, 각 문자의 등장 여부를 저장해두는 배열입니다.

728x90

2️⃣ calculFn

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;
    }

---

    public static String calculFn(String str, int index, boolean[] seen) {

• calculFn() 함수 정의
  • 매개변수:
    • str: 원본 문자열
    • index: 현재 검사할 문자 위치
    • seen: 중복 체크용 배열

   if (index < 0) return "";
   // 기본형
	if (index < 0) {
    		return "";
	}

• Java의 if 문은 일반적으로 중괄호 {}를 사용합니다. 조건이 참일 경우 return "" 문장을 실행합니다.
• 조건문 다음에 실행할 코드가 딱 한 줄일 경우, 중괄호 {}를 생략할 수 있습니다.
• index가 0보다 작아지면 재귀 호출을 멈추는 종료 조건(base case)입니다.

 char c = str.charAt(index);
 
// charAt 메서드 : 문자열(String)의 특정 위치에 있는 문자 하나를 가져오는 메서드
char c = 문자열.charAt(인덱스);
- 문자열: "hello" 같은 String 객체
- 인덱스: 가져오고 싶은 문자 위치 (0부터 시작)
- 반환값: char 타입 (한 글자)

• 현재 인덱스에 해당하는 문자를 꺼냅니다.
• 예: index = 7이면 str.charAt(7) → 'd'

String result = calculFn(str, index - 1, seen);

• 현재 함수 안에서 자기 자신을 다시 호출하고 있습니다. (재귀 호출)
• 재귀 호출이 완료되면, 그 결과 문자열을 result에 저장합니다.
• calculFn 함수가 처음 호출될 때 인자 값
  • str = "abacabcd"
  • index = str.length() - 1 : str.length()는 문자열의 길이 → "abacabcd"는 8글자 → 8, - 1을 하면 7
  • seen = new boolean[256]. 모든 값이 false인 boolean 배열입니다.

3️⃣ 함수 작동 원리

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

🎯 목표

문자열을 오른쪽부터 왼쪽으로 탐색하면서 중복되지 않은 문자만 남기는 재귀함수 : 
문자열 "abacabcd"를 뒤에서부터 한 글자씩 보면서, 중복되지 않은 문자만 남기기. 그리고 그 문자를 뒤에서 처음 등장한 순서로 이어붙이는 것.

🎯 재귀 함수의 흐름

• 주어진 문자열: "abacabcd"

문자 :  a  b  a  c  a  b  c  d
인덱스: 0  1  2  3  4  5  6  7

 

1. index가 음수인지 확인

if (index < 0) return "";

• base case: 종료 조건입니다. index가 0 이상이면 다음 단계로 진행합니다.
• index = str.length() - 1 : str.length()는 문자열의 길이 → "abacabcd"는 8글자 → 8, - 1을 하면 7
• 따라서 종료 조건에 해당하지 않기 때문에 다음 단계로 진행

2. 현재 문자 꺼내기

char c = str.charAt(index);

• 현재 index에 있는 문자를 c에 저장
• 7에 있는 문자 d 저장

3. 재귀 호출

String result = calculFn(str, index - 1, seen);

• 이전 문자를 확인하기 위해 함수 자신을 호출 여기서 계속해서 호출만 되고, 결과는 잠시 멈춥니다! 여기까지는 단지 호출만 계속하고, 모두 멈춰 결과 기다리는 상태입니다
• 예: calculFn(str, 6, seen) → calculFn(5) → calculFn(4) … → calculFn(-1)까지 간 다음에야 result 값이 생깁니다.
• index = 7 이므로 7-1=6
  calculFn(str, 6, seen) 호출
      ↓
  calculFn("abacabcd", 6) → 'c'
  다음 호출로 진행 (index-1 = 5)
      ↓
  calculFn("abacabcd", 5) → 'b'
  다음 호출로 진행 (index-1 = 4)
      ↓
  calculFn("abacabcd", 4) → 'a'
  다음 호출로 진행 (index-1 = 3)
      ↓
  calculFn("abacabcd", 3) → 'c'
  다음 호출로 진행 (index-1 = 2)
      ↓
  calculFn("abacabcd", 2) → 'a'
  다음 호출로 진행 (index-1 = 1)
      ↓
  calculFn("abacabcd", 1) → 'b'
  다음 호출로 진행 (index-1 = 0)
      ↓
  calculFn("abacabcd", 0) → 'a'
  다음 호출로 진행 (index-1 = -1)
      ↓
  calculFn("abacabcd", -1) → base case, return ""
  재귀 종료, 빈 문자열 "" 반환

4. 재귀 복귀 시작 (결과 결합)

함수는 자기가 호출한 다른 함수의 결과가 돌아오기 전까지는 return을 못합니다. 그래서 맨 마지막 함수만 먼저 return하고,그 다음부터 하나씩 위로 올라오며 순차적으로 return되는 것처럼 보입니다 이게 바로 재귀 복귀 단계입니다.

📌 seen[c] 검사

if (!seen[c]) { // 아직 c 문자가 등장한 적이 없다면
    seen[c] = true;  // 이제 이 문자가 등장했으니까 true로 바꿔줌
    return c + result; // 현재 문자 c를 앞에 붙여서 반환
}

• seen[c]를 계산하면, 'a' → ASCII 코드 97이므로 seen['a'] = seen[97] 그리고 seen은 모든 값이 false인 boolean 배열
• 따라서 seen[c]는 false이지만 !연사자로 인해 true
• [참고] 아스키코드(ASCII code)에서 문자 'a'부터 'Z'까지의 범위
  대문자 A~Z : A(65)~Z(90)
  소문자 a~z : a(97)~z(122)

return result;

• seen[c]가 true면 그냥 result만 반환

📌 재귀 복귀

• index = 0, 문자 = 'a'
  • result = ""
  • seen['a'] = false → true로 바꾸고
  • 반환: 'a' + "" = "a"
• index = 1, 문자 = 'b'
  • result = "a"
  • seen['b'] = false → true로 바꾸고
  • 반환: 'b' + "a" = "ba"
• index = 2, 문자 = 'a'
  • result = "ba"
  • seen['a'] = true → 이미 등장했으므로
  • 반환: "ba"
• index = 3, 문자 = 'c'
  • result = "ba"
  • seen['c'] = false → true로 바꾸고
  • 반환: 'c' + "ba" = "cba"
• index = 4, 문자 = 'a'
  • result = "cba"
  • seen['a'] = true → 이미 등장
  • 반환: "cba"
• index = 5, 문자 = 'b'
  • result = "cba"
  • seen['b'] = true → 이미 등장
  • 반환: "cba"
• index = 6, 문자 = 'c'
  • result = "cba"
  • seen['c'] = true → 이미 등장
  • 반환: "cba"
• index = 7, 문자 = 'd'
  • result = "cba"
  • seen['d'] = false → true로 바꾸고
  • 반환: 'd' + "cba" = "dcba"

[ 재귀 호출 & 복귀 흐름 표 ]

[ 재귀 호출 & 복귀 흐름 표 ]

4️⃣ 출력

 System.out.print(calculFn(str, str.length() - 1, seen));

 

• 출력값: dcba

---

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."