[Programmers] #120886 - A로 B 만들기 [Java][C++][Python]

문제 링크

---

1. 아이디어

문자열 before를 순서를 바꿔서 after를 만들 수 있는지 판단하는 문제로 애너그램 여부를 구하면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(1)$

($N$ = before의 길이(= after의 길이). C++ 풀이는 정렬 기반이라 시간 $O(N \log N)$)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(String before, String after) {
        int[] cnt = new int[26];
        for (char c : before.toCharArray()) {
            cnt[c - 'a']++;
        }
        for (char c : after.toCharArray()) {
            cnt[c - 'a']--;
        }

        for (int x : cnt) {
            if (x != 0) return 0;
        }

        return 1;
    }
}

카운팅 배열을 활용해 카운팅 배열이 전부 0인지로 애너그램 여부를 판단할 수 있다.

#include <bits/stdc++.h>
using namespace std;

int solution(string before, string after) {
    sort(before.begin(), before.end());
    sort(after.begin(), after.end());
    return before == after;
}

애너그램은 각 문자열의 문자를 사전순으로 정렬하면 동일한 문자열이 된다.

from collections import Counter


def solution(before, after):
    return int(Counter(before) == Counter(after))

---