-
[LeetCode] 1079. Letter Tile Possibilities알고리즘 문제 풀이 2021. 6. 7. 12:31
문제 출처: https://leetcode.com/problems/letter-tile-possibilities/
Letter Tile Possibilities - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제
n
개의tiles
이 있고, 각 타일에는 한 개의 문자tiles[i]
가 출력되어 있다.이
tiles
를 이용하여 만들 수 있는 비어있지 않는 문자 시퀀스의 수 를 반환하라.예제
Input: tiles = "AAB" Output: 8 Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".
Input: tiles = "V" Output: 1
풀이
문제를 단순화하면, 주어진 문자로 만들 수 있는 순열의 수를 구하는 문제이다. 단, 예제에서 볼 수 있듯이 주어지는 문자에 중복되는 문자가 존재할 수 있다는 점에 주의를 해야 한다.
우선 맵 자료구조를 이용하여 어떤 문자들이 중복되는지 확인한다.
dup = new Map(); for ( let i = 0; i < tiles.length; i++ ) { const letter = tilse[i]; if (!dup.has(letter)) { dup.set(letter, 0); } dup.set(letter, dup.get(letter) + 1); }
이를 이용하여 순열을 구하는
getPerms(map, prefix, remainder)
를 작성한다.function getPerms(map, prefix, remainder) { if (remainder == 0) return 1; count = 0; for ( let [key, value] of map ) { // 맵 순회: 중복된 현재 단계에서 중복된 단어가 선택되지 않도록 함 map.set(key, value-1); count += getPerms(prefix+key, remainder-1); map.set(key, value); } return count; }
핵심은 순열을 계산하는 각 단계에서 중복되는 단어가 선택되지 않도록 하는 것이다.
마지막은
getPerms(map, prefix, remainder)
를 이용하여 모든 케이스를 체크하는 것이다.totalCount = 0 for (let i = 1; i <= tiles.length; i++) { totalCount += getPerms(dup, "", i); }
Github: 1079.js
opwe37/Algorithm-Study
Contribute to opwe37/Algorithm-Study development by creating an account on GitHub.
github.com
'알고리즘 문제 풀이' 카테고리의 다른 글
[LeetCode] 1039. Minimum Score Triangulation of Polygon (0) 2021.06.09 [LeetCode] 98. Validate Binary Search Tree (0) 2021.06.08 [LeetCode] 893. Groups of Special-Equivalent Strings (0) 2021.06.04 [LeetCode] 704. Binary Search (0) 2021.06.03 [LeetCode] 1814. Count Nice Pairs in an Array (0) 2021.06.02