[프로그래머스, LV.0] A로 B 만들기

목차

문제 설명

문자열 before와 after가 매개변수로 주어질 때, before의 순서를 바꾸어 after를 만들 수 있으면 1을, 만들 수 없으면 0을 return 하도록 solution 함수를 완성해보세요.

---

 

제한사항

• 0 < before의 길이 == after의 길이 < 1,000
• before와 after는 모두 소문자로 이루어져 있습니다.

import java.util.Arrays;

class Solution {
    public int solution(String before, String after) {
        // 문자열을 문자 배열로 변환 후 정렬
        char[] beforeArray = before.toCharArray();
        char[] afterArray = after.toCharArray();
        Arrays.sort(beforeArray);
        Arrays.sort(afterArray);

        // 정렬된 배열 비교
        return Arrays.equals(beforeArray, afterArray) ? 1 : 0;
    }
}

코드 설명

1. 문자 배열로 변환
   • before.toCharArray()와 after.toCharArray()를 통해 두 문자열을 문자 배열로 변환한다.
2. 문자 배열 정렬
   • Arrays.sort()를 사용해 두 문자 배열을 각각 정렬한다.
3. 배열 비교
   • Arrays.equals()를 사용해 두 정렬된 배열이 같은지 비교한다.
   • 같으면 1, 다르면 0을 반환한다.

 

1. 문제의 본질 이해

주어진 문제는 두 문자열 before와 after의 문자 구성이 동일한지를 확인하는 것이다.

• 즉, before의 순서를 바꾸어 after를 만들 수 있다는 것은 두 문자열이 동일한 문자 집합을 같는지 판단하는 문제다.
• 이를 해결하기 위해 문자열의 문자 구성을 비교하면 충분하다.

---

2. 문자 구성을 비교하는 가장 쉬운 방법: 정렬

정렬이 적합한 이유

1. 두 문자열의 길이가 같을 경우:
   • 정렬된 결과가 같다면 두 문자열은 동일한 문자 구성을 가진다.
   • 예: "olleh" → 정렬 → "ehllo", "hello" → 정렬 → "ehllo"
2. 정렬된 결과가 다르다면:
   • 두 문자열은 문자 구성이 다르며, 하나를 순서를 바꾸어 다른 하나로 만들 수 없다.
   • 예: "allpe" → 정렬 → "aellp", "apple" → 정렬 → "aelpp"

정렬 기반 접근법의 장점

• 직관적: 정렬은 문자 집합을 정돈하여 쉽게 비교할 수 있는 방식이다.
• 효율적: Java의 Arrays.sort()는 시간 복잡도가 O(nlog⁡n)O(n \log n)O(nlogn)이며, n<1000n < 1000n<1000인 문제 제한사항에서 충분히 효율적이다.
• 간결함: 정렬 후 비교라는 두 단계로 문제를 단순화할 수 있다.