LeetCode 383번: Ransom Note(JAVA)
문제출처 383번: Ransom Note
❔ 문제
두 문자열 ransomNote와 magazine에서 magazine의 각 구성요소를 중복없이 사용했을 때, ransomNote 문자열이 구성 가능한가에 대한 문제.
⏩ 예시
Input: ransomNote = “aa”, magazine = “aab”
Output: true
❕ 문제풀이
public boolean canConstruct(String ransomNote, String magazine) {
for (int i = 0; i < magazine.length() - ransomNote.length(); i++) { // 1.
for (int j = i; j < ransomNote.length(); j++) { // 2.
if(ransomNote.charAt(j) != magazine.charAt(j)) continue; // 3.
}
return true;
}
return false;
}
- magazine 문자열의 각 구성요소를 순회한다.
- magazine 문자열의 순회 인덱스 i로부터 rasomNote와 각 문자를 비교한다.
- 하나라도 문자가 같지 않다면 loop를 다시 순회한다.
💯 고찰
위 풀이는 처음 해결방식을 고안했을 때의 코드이다 하지만 내가 생각한 풀이는 magazine의 연속된 부분 문자열 중 ransomNote와 일치하는 것이 있는지를 생각했기에 결국 풀이 방식은 잘못되었다. 또한 위의 풀이보다 성능이 더 개선된 KMP 알고리즘 등이 있기 때문에 더 알아봐야 할 것 같다.
public boolean canConstruct(String ransomNote, String magazine) {
for (int i = 0; i < magazine.length() - ransomNote.length(); i++) {
for (int j = i; j < ransomNote.length(); j++) {
if(ransomNote.charAt(j) != magazine.charAt(j)) continue;
}
return true;
}
return false;
}
참고한 위 솔루션은 HashMap 을 이용한 풀이였다.
연속되지 않아도 되기에 magazine의 각 요소의 개수를 저장한 후 ransomNote와 비교하며 하나씩 차감하는 방식이다.
