๐ ๋ฌธ์
๊ฐ๋ฐํ ๋ด์์ ์ด๋ฒคํธ ๊ฐ๋ฐ์ ๋ด๋นํ๊ณ ์๋ ๋ฌด์ง๋ ์ต๊ทผ ์งํ๋ ์นด์นด์ค์ด๋ชจํฐ์ฝ ์ด๋ฒคํธ์ ๋น์ ์์ ์ธ ๋ฐฉ๋ฒ์ผ๋ก ๋น์ฒจ์ ์๋ํ ์๋ชจ์๋ค์ ๋ฐ๊ฒฌํ์์ต๋๋ค. ์ด๋ฐ ์๋ชจ์๋ค์ ๋ฐ๋ก ๋ชจ์ ๋ถ๋ ์ฌ์ฉ์๋ผ๋ ์ด๋ฆ์ผ๋ก ๋ชฉ๋ก์ ๋ง๋ค์ด์ ๋น์ฒจ ์ฒ๋ฆฌ ์ ์ ์ธํ๋๋ก ์ด๋ฒคํธ ๋น์ฒจ์ ๋ด๋น์์ธ ํ๋ก๋ ์๊ฒ ์ ๋ฌํ๋ ค๊ณ ํฉ๋๋ค. ์ด ๋ ๊ฐ์ธ์ ๋ณด ๋ณดํธ์ ์ํด ์ฌ์ฉ์ ์์ด๋ ์ค ์ผ๋ถ ๋ฌธ์๋ฅผ '*' ๋ฌธ์๋ก ๊ฐ๋ ค์ ์ ๋ฌํ์ต๋๋ค. ๊ฐ๋ฆฌ๊ณ ์ ํ๋ ๋ฌธ์ ํ๋์ '*' ๋ฌธ์ ํ๋๋ฅผ ์ฌ์ฉํ์๊ณ ์์ด๋ ๋น ์ต์ ํ๋ ์ด์์ '*' ๋ฌธ์๋ฅผ ์ฌ์ฉํ์์ต๋๋ค.
๋ฌด์ง์ ํ๋ก๋๋ ๋ถ๋ ์ฌ์ฉ์ ๋ชฉ๋ก์ ๋งคํ๋ ์๋ชจ์ ์์ด๋๋ฅผ ์ ์ฌ ์์ด๋ ๋ผ๊ณ ๋ถ๋ฅด๊ธฐ๋ก ํ์์ต๋๋ค.
์ด๋ฒคํธ ์๋ชจ์ ์์ด๋ ๋ชฉ๋ก์ด ๋ด๊ธด ๋ฐฐ์ด user_id์ ๋ถ๋ ์ฌ์ฉ์ ์์ด๋ ๋ชฉ๋ก์ด ๋ด๊ธด ๋ฐฐ์ด banned_id๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋น์ฒจ์์ ์ ์ธ๋์ด์ผ ํ ์ ์ฌ ์์ด๋ ๋ชฉ๋ก์ ๋ช๊ฐ์ง ๊ฒฝ์ฐ์ ์๊ฐ ๊ฐ๋ฅํ ์ง return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
๐ ์ ํ์ฌํญ
- user_id ๋ฐฐ์ด์ ํฌ๊ธฐ๋ 1 ์ด์ 8 ์ดํ์ ๋๋ค.
- user_id ๋ฐฐ์ด ๊ฐ ์์๋ค์ ๊ฐ์ ๊ธธ์ด๊ฐ 1 ์ด์ 8 ์ดํ์ธ ๋ฌธ์์ด์
๋๋ค.
- ์๋ชจํ ์ฌ์ฉ์ ์์ด๋๋ค์ ์๋ก ์ค๋ณต๋์ง ์์ต๋๋ค.
- ์๋ชจํ ์ฌ์ฉ์ ์์ด๋๋ ์ํ๋ฒณ ์๋ฌธ์์ ์ซ์๋ก๋ง์ผ๋ก ๊ตฌ์ฑ๋์ด ์์ต๋๋ค.
- banned_id ๋ฐฐ์ด์ ํฌ๊ธฐ๋ 1 ์ด์ user_id ๋ฐฐ์ด์ ํฌ๊ธฐ ์ดํ์ ๋๋ค.
- banned_id ๋ฐฐ์ด ๊ฐ ์์๋ค์ ๊ฐ์ ๊ธธ์ด๊ฐ 1 ์ด์ 8 ์ดํ์ธ ๋ฌธ์์ด์
๋๋ค.
- ๋ถ๋ ์ฌ์ฉ์ ์์ด๋๋ ์ํ๋ฒณ ์๋ฌธ์์ ์ซ์, ๊ฐ๋ฆฌ๊ธฐ ์ํ ๋ฌธ์ '*' ๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
- ๋ถ๋ ์ฌ์ฉ์ ์์ด๋๋ '*' ๋ฌธ์๋ฅผ ํ๋ ์ด์ ํฌํจํ๊ณ ์์ต๋๋ค.
- ๋ถ๋ ์ฌ์ฉ์ ์์ด๋ ํ๋๋ ์๋ชจ์ ์์ด๋ ์ค ํ๋์ ํด๋นํ๊ณ ๊ฐ์ ์๋ชจ์ ์์ด๋๊ฐ ์ค๋ณตํด์ ์ ์ฌ ์์ด๋ ๋ชฉ๋ก์ ๋ค์ด๊ฐ๋ ๊ฒฝ์ฐ๋ ์์ต๋๋ค.
- ์ ์ฌ ์์ด๋ ๋ชฉ๋ก๋ค์ ๊ตฌํ์ ๋ ์์ด๋๋ค์ด ๋์ด๋ ์์์ ๊ด๊ณ์์ด ์์ด๋ ๋ชฉ๋ก์ ๋ด์ฉ์ด ๋์ผํ๋ค๋ฉด ๊ฐ์ ๊ฒ์ผ๋ก ์ฒ๋ฆฌํ์ฌ ํ๋๋ก ์ธ๋ฉด ๋ฉ๋๋ค.
๐ ํ์ด
ํจ์จ์ฑ์ ๊ณ ๋ คํ์ง ์์๋ ๋๋ ๋ฌธ์ . dfs๋ก ์์ด์ ๊ตฌํด์ ํ๋ฉด ๋์ง ์์๊น? ์๊ฐํ๋ค. ๊ทธ๋ฐ๋ฐ ๋ฌธ์ ๋ ์์ด์ ๊ตฌํ๊ณ ์ค๋ณต์ ์ ๊ฑฐํด์ผ ํ๋ค๋ ์ . ๋ค์ dfs๋ก ๊ตฌํด์ผ ํ๋? ์๊ฐํ๋๋ฐ ๋๋ฌด ๋นํจ์จ์ ์ธ ๋๋์ด์๋ค. ๊ณ์ํด์ ์ฝ์งํ๋ค Set์ ์ฌ์ฉํด์ ์ค๋ณต์ ์ ๊ฑฐํ๊ธฐ๋ก ํ๋ค.
- ๋ชจ๋ ์ ์ ๋ชฉ๋ก (String[] user_id)
- ๋ถ๋ ์ฌ์ฉ์ ๋ชฉ๋ก (String[] banned_id)
- ์ ํ๋ ์ ์ ๋ค์ ์ฒดํฌํ๋ ๋ชฉ๋ก (boolean[] select)
- ๋ถ๋ ์ฌ์ฉ์ ๋ชฉ๋ก์ ๊ฐ์๋งํผ ์์๋ก ์ ์ ๋ฅผ ๋ด๋ ๋ชฉ๋ก (LinkedList<String> users)
- ์ค๋ณต๋ ์ฌ์ฉ์๋ค์ ์ ๊ฑฐํ๋ ๋ฐฐ์ด (Set<Set<String>> result)
- dfs(int cnt): ์์ด์ ๊ตฌํ๊ณ , ์ค๋ณต์ ์ ๊ฑฐํ๋ค.
- result.add(new HashSet<>(users)): ์ค๋ณต์ ์ ๊ฑฐํ๋ Set
- match(String userId, String banId): ์ ์ ID์ banId์ ํจํด์ด ์ผ์นํ๋์ง ํ์ธํ๋ ๋ฉ์๋
- ์ ์ ์์ด๋์ ๋ถ๋ ์ฌ์ฉ์ ์์ด๋์ ๊ธธ์ด๊ฐ ๋ค๋ฅด๋ค๋ฉด false
- ๋ชจ๋ ๊ธ์๊ฐ ์ผ์นํ๋ฉด true (๋ถ๋ ์ฌ์ฉ์ ์์ด๋์ ๊ธ์๊ฐ '*'๋ผ๋ฉด ๋ฌด์กฐ๊ฑด ์ผ์น)
๊ฒฐ๊ณผ๋ ์ค๋ณต์ ์ ๊ฑฐํ๊ณ ๋จ์ ๊ฐ์๋ฅผ ๋ฆฌํดํ๋ค. ์ฆ, result์ size๊ฐ ๊ฒฝ์ฐ์ ์๋ฅผ ์๋ฏธํ๋ค.
๐ ์ฝ๋
public class ๋ถ๋์ฌ์ฉ์ {
@Test
void test() {
int solution1 = solution(new String[]{"frodo", "fradi", "crodo", "abc123", "frodoc"}, new String[]{"fr*d*", "abc1**"});
int solution2 = solution(new String[]{"frodo", "fradi", "crodo", "abc123", "frodoc"}, new String[]{"*rodo", "*rodo", "******"});
int solution3 = solution(new String[]{"frodo", "fradi", "crodo", "abc123", "frodoc"}, new String[]{"fr*d*", "*rodo", "******", "******"});
assertThat(solution1).isEqualTo(2);
assertThat(solution2).isEqualTo(2);
assertThat(solution3).isEqualTo(3);
}
String[] user_id;
String[] banned_id;
boolean[] select;
LinkedList<String> users = new LinkedList<>();
Set<Set<String>> result = new HashSet<>();
public int solution(String[] user_id, String[] banned_id) {
this.user_id = user_id;
this.banned_id = banned_id;
this.select = new boolean[user_id.length];
dfs(0);
return result.size();
}
public void dfs(int cnt) {
if (cnt == banned_id.length) {
for (int i = 0; i < users.size(); i++) {
if (!match(users.get(i), banned_id[i])) {
return;
}
}
result.add(new HashSet<>(users));
}
for (int i = 0; i < user_id.length; i++) {
if (select[i]) continue;
select[i] = true;
users.add(user_id[i]);
dfs(cnt + 1);
select[i] = false;
users.removeLast();
}
}
private boolean match(String userId, String banId) {
if (userId.length() != banId.length()) return false;
for (int i = 0; i < userId.length(); i++) {
if (banId.charAt(i) == '*') continue;
if (userId.charAt(i) != banId.charAt(i)) return false;
}
return true;
}
}
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
'Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๐ 2019 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ๊ณต์ฑ: ํ๋ณดํค (Java) (0) | 2020.05.03 |
---|---|
๐ค 2020 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ๊ณต์ฑ: ์๋ฌผ์ ์ ์ด์ (Java) (0) | 2020.04.28 |
๐ ํ๋ก๊ทธ๋๋จธ์ค: Lv3. ์ ๊ตญ ์ฌ์ฌ (Java) (0) | 2020.04.25 |
๐ ์นด์นด์ค 2019 ๊ฒจ์ธ ์ธํด์ญ: ๋ถ๋ ์ฌ์ฉ์(Lv3) (0) | 2020.04.05 |
๐ ์นด์นด์ค 2019 ๊ฒจ์ธ ์ธํด์ญ: ํฌ๋ ์ธ ์ธํ๋ฝ๊ธฐ ๊ฒ์(Lv2) (0) | 2020.04.01 |
๐จ ์นด์นด์ค 2019 ๊ฒจ์ธ ์ธํด์ญ: ํธํ ๋ฐฉ ๋ฐฐ์ (Lv4) (0) | 2020.04.01 |