๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

Algorithm

๐Ÿ˜Ž ์นด์นด์˜ค 2019 ๊ฒจ์šธ ์ธํ„ด์‹ญ: ๋ถˆ๋Ÿ‰ ์‚ฌ์šฉ์ž(Lv3)

๐Ÿ“Œ ๋ฌธ์ œ

๊ฐœ๋ฐœํŒ€ ๋‚ด์—์„œ ์ด๋ฒคํŠธ ๊ฐœ๋ฐœ์„ ๋‹ด๋‹นํ•˜๊ณ  ์žˆ๋Š” ๋ฌด์ง€๋Š” ์ตœ๊ทผ ์ง„ํ–‰๋œ ์นด์นด์˜ค์ด๋ชจํ‹ฐ์ฝ˜ ์ด๋ฒคํŠธ์— ๋น„์ •์ƒ์ ์ธ ๋ฐฉ๋ฒ•์œผ๋กœ ๋‹น์ฒจ์„ ์‹œ๋„ํ•œ ์‘๋ชจ์ž๋“ค์„ ๋ฐœ๊ฒฌํ•˜์˜€์Šต๋‹ˆ๋‹ค. ์ด๋Ÿฐ ์‘๋ชจ์ž๋“ค์„ ๋”ฐ๋กœ ๋ชจ์•„ ๋ถˆ๋Ÿ‰ ์‚ฌ์šฉ์ž๋ผ๋Š” ์ด๋ฆ„์œผ๋กœ ๋ชฉ๋ก์„ ๋งŒ๋“ค์–ด์„œ ๋‹น์ฒจ ์ฒ˜๋ฆฌ ์‹œ ์ œ์™ธํ•˜๋„๋ก ์ด๋ฒคํŠธ ๋‹น์ฒจ์ž ๋‹ด๋‹น์ž์ธ ํ”„๋กœ๋„ ์—๊ฒŒ ์ „๋‹ฌํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์ด ๋•Œ ๊ฐœ์ธ์ •๋ณด ๋ณดํ˜ธ์„ ์œ„ํ•ด ์‚ฌ์šฉ์ž ์•„์ด๋”” ์ค‘ ์ผ๋ถ€ ๋ฌธ์ž๋ฅผ '*' ๋ฌธ์ž๋กœ ๊ฐ€๋ ค์„œ ์ „๋‹ฌํ–ˆ์Šต๋‹ˆ๋‹ค. ๊ฐ€๋ฆฌ๊ณ ์ž ํ•˜๋Š” ๋ฌธ์ž ํ•˜๋‚˜์— '*' ๋ฌธ์ž ํ•˜๋‚˜๋ฅผ ์‚ฌ์šฉํ•˜์˜€๊ณ  ์•„์ด๋”” ๋‹น ์ตœ์†Œ ํ•˜๋‚˜ ์ด์ƒ์˜ '*' ๋ฌธ์ž๋ฅผ ์‚ฌ์šฉํ•˜์˜€์Šต๋‹ˆ๋‹ค.
๋ฌด์ง€์™€ ํ”„๋กœ๋„๋Š” ๋ถˆ๋Ÿ‰ ์‚ฌ์šฉ์ž ๋ชฉ๋ก์— ๋งคํ•‘๋œ ์‘๋ชจ์ž ์•„์ด๋””๋ฅผ ์ œ์žฌ ์•„์ด๋”” ๋ผ๊ณ  ๋ถ€๋ฅด๊ธฐ๋กœ ํ•˜์˜€์Šต๋‹ˆ๋‹ค.

์ด๋ฒคํŠธ ์‘๋ชจ์ž ์•„์ด๋”” ๋ชฉ๋ก์ด ๋‹ด๊ธด ๋ฐฐ์—ด 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)
  1. dfs(int cnt): ์ˆœ์—ด์„ ๊ตฌํ•˜๊ณ , ์ค‘๋ณต์„ ์ œ๊ฑฐํ•œ๋‹ค.
    1. result.add(new HashSet<>(users)): ์ค‘๋ณต์„ ์ œ๊ฑฐํ•˜๋Š” Set
  2. match(String userId, String banId): ์œ ์ € ID์™€ banId์˜ ํŒจํ„ด์ด ์ผ์น˜ํ•˜๋Š”์ง€ ํ™•์ธํ•˜๋Š” ๋ฉ”์†Œ๋“œ
    1. ์œ ์ € ์•„์ด๋””์™€ ๋ถˆ๋Ÿ‰ ์‚ฌ์šฉ์ž ์•„์ด๋””์˜ ๊ธธ์ด๊ฐ€ ๋‹ค๋ฅด๋‹ค๋ฉด false
    2. ๋ชจ๋“  ๊ธ€์ž๊ฐ€ ์ผ์น˜ํ•˜๋ฉด 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