[프로그래머스] 불량 사용자

문제링크

문제 설명

개발팀 내에서 이벤트 개발을 담당하고 있는 “무지”는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 “프로도” 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 ‘’ 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 ‘’ 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 ‘*’ 문자를 사용하였습니다. “무지”와 “프로도”는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.

예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면

응모자 아이디
frodo
fradi
crodo
abc123
frodoc

다음과 같이 불량 사용자 아이디 목록이 전달된 경우,

불량 사용자
frd
abc1**

불량 사용자에 매핑되어 당첨에서 제외되어야 야 할 제재 아이디 목록은 다음과 같이 두 가지 경우가 있을 수 있습니다.

제재 아이디
frodo
abc123
제재 아이디
fradi
abc123

이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.

[제한사항]

  • user_id 배열의 크기는 1 이상 8 이하입니다.
  • user_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
    • 응모한 사용자 아이디들은 서로 중복되지 않습니다.
    • 응모한 사용자 아이디는 알파벳 소문자와 숫자로만으로 구성되어 있습니다.
  • banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다.
  • banned_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
    • 불량 사용자 아이디는 알파벳 소문자와 숫자, 가리기 위한 문자 ‘*’ 로만 이루어져 있습니다.
    • 불량 사용자 아이디는 ‘*’ 문자를 하나 이상 포함하고 있습니다.
    • 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
  • 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.

[입출력 예]
user_id banned_id result
["frodo", "fradi", "crodo", "abc123", "frodoc"] ["fr*d*", "abc1**"] 2
["frodo", "fradi", "crodo", "abc123", "frodoc"] ["*rodo", "*rodo", "******"] 2
["frodo", "fradi", "crodo", "abc123", "frodoc"] ["fr*d*", "*rodo", "******", "******"] 3
입출력 예에 대한 설명
입출력 예 #1

문제 설명과 같습니다.

입출력 예 #2

다음과 같이 두 가지 경우가 있습니다.

제재 아이디
frodo
crodo
abc123
제재 아이디
frodo
crodo
frodoc
입출력 예 #3

다음과 같이 세 가지 경우가 있습니다.

제재 아이디
frodo
crodo
abc123
frodoc
제재 아이디
fradi
crodo
abc123
frodoc
제재 아이디
fradi
frodo
abc123
frodoc


Sol

카카오 코딩테스트 문제치고는 상당히 쉽게 해결되는 문제였습니다.

최근 일주일정도 일이 몰려서 알고리즘을 못 풀고 지내다가 오랜만에 워밍업(?) 하기 좋은 문제였습니다.

제가 접근한 풀이의 핵심은 ‘순열’을 활용한 경우의 수 탐색 방법이었습니다.


  1. 먼저 board를 만들어 주었습니다. 사용자 목록과 불량 사용자명이 매핑이 되는지 여부를 판단하였습니다.

    (글씨가 많이 날라가네요 머쓱ㅎㅎㅎ)

    image-20210709003603185

  2. python에서 제가 애정하는 패키지 itertools를 활용해 permutation(순열) 을 생성해 줍니다.

    image-20210709003937727

  3. 이제 board를 참조하며

    board[_][myperm[_]]
    

    이 모두 1인(가능한) 경우의 수를 모두 answer에 append() 해줍니다.

  4. answer에서 중복을 제거한 후, len(answer)를 반환해 주면 해결!


Code

import itertools
def candi_checker(id1, id2):  # (banned_id, user_id)
    if len(id1) != len(id2):
        return 0
    idx = 0
    while idx < len(id1):
        if id1[idx] != '*' and id1[idx] != id2[idx]:
            return 0
        idx += 1
    return 1


def solution(user_id, banned_id):
    answer = []
    idxs = [_ for _ in range(len(user_id))]
    # make board
    board = [[0 for j in range(len(user_id))] for i in range(len(banned_id))]
    for i in range(len(banned_id)):
        for j in range(len(user_id)):
            board[i][j] = candi_checker(banned_id[i], user_id[j])

    mypermutation = itertools.permutations(idxs,len(banned_id))
    for myperm in mypermutation:
        cnt = len(banned_id)
        for _ in range(len(banned_id)):
            if board[_][myperm[_]] == 1:
                cnt -= 1
                if cnt == 0:
                    answer.append(myperm)
            else:
                break

    answer = len(list(set([tuple(set(ans)) for ans in answer])))
    return answer

2021

[LeetCode] Word Search

2 minute read

문제링크 문제 설명 Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters o...

[프로그래머스] 기지국 설치

2 minute read

문제링크 문제 설명 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기...

[백준] 괄호 제거

2 minute read

문제링크 괄호 제거 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 2016 680 ...

[LeetCode] Longest Palindromic Substring

1 minute read

문제링크 문제 설명 Given a string s, return the longest palindromic substring in s. Example 1: Input: s = "babad" Output: "bab" Note: "aba" is also a valid ans...

[프로그래머스] 거리두기 확인하기

6 minute read

문제링크 문제 설명 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다. 대기실은 5...

[프로그래머스] 불량 사용자

2 minute read

문제링크 문제 설명 개발팀 내에서 이벤트 개발을 담당하고 있는 “무지”는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자...

[프로그래머스] 문자열 압축

3 minute read

문제링크 문제 설명 데이터 처리 전문가가 되고 싶은 “어피치”는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되...

[LeetCode] Container With Most Water

2 minute read

문제링크 Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpo...

[LeetCode] Trapping Rain Water

1 minute read

문제링크 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. Exam...

[LeetCode] Median of Two Sorted Arrays

2 minute read

문제링크 Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time c...

[LeetCode] First Missing Positive

1 minute read

문제링크 Given an unsorted integer array nums, find the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses co...

[백준] 나무 자르기

3 minute read

문제링크 나무 자르기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 72052 20773 ...

[프로그래머스] 광고삽입

5 minute read

문제링크 문제 설명 카카오TV에서 유명한 크리에이터로 활동 중인 죠르디는 환경 단체로부터 자신의 가장 인기있는 동영상에 지구온난화의 심각성을 알리기 위한 공익광고를 넣어 달라는 요청을 받았습니다. 평소에 환경 문제에 관심을 가지고 있던 “죠르디”는 요청을 받아들였고 광고효과...

[LeetCode] Climbing Stairs

1 minute read

문제링크 Easy You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you ...

[프로그래머스] 거스름돈

1 minute read

문제링크 문제 설명 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 ...

[LeetCode] Unique Paths

1 minute read

문제링크 A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any p...

[LeetCode] 3Sum

1 minute read

문제링크 Medium Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + ...

Back to top ↑