Minystory

[프로그래머스/카카오 60059] 자물쇠와 열쇠 (Python)

May 6, 2022
Algorithm, Programmers, Lv3
Algorithm, Problem Solving, 프로그래머스, 프로그래머스 Lv3, Python, Matrix

문제 링크 #

개요 #

  • numpy 라이브러리와 중복 순열을 사용해 해결할 수 있는 문제다.

문제 조건 #

  • 2차원 배열인 열쇠(M)를 회전하거나 이동해 2차원 배열인 자물쇠(N)에 맞는지 여부를 반환하는 문제다.

문제 해설 #

  • 2차원 배열을 numpy.ndarray 형식으로 변환하면 회전 및 이동 연산을 쉽게 처리할 수 있다.
  • 90도 단위로 4번 회전된 각각의 목록을 구하고 상하좌우 이동을 위해 바깥쪽에 0으로 채워진 padding을 추가한다.
  • padding이 채워진 N+M-1크기의 2차원 배열에 대해 자물쇠 크기만큼의 부분만 잘라내어 자물쇠의 구멍과 비교한다.
  • OR 연산 시 자물쇠가 1로 채워지고 열쇠와 자물쇠 사이에 겹치는 부분이 없다면 열쇠가 자물쇠에 맞다고 판단한다.

시행착오 #

  • 열쇠의 크기가 자물쇠의 크기보다 작을 경우를 고려하지 못하고 둘의 사이즈를 맞추는 과정을 무시해 에러가 생겼다.
  • 처음엔 0으로 채워진 단일 행 또는 열과 concatenate 연산을 진행해 열쇠를 아래쪽과 오른쪽으로만 이동했는데,
    그 반대의 경우를 고려하지 못해서 에러가 생겼다. 이후 padding을 사용하는 코드로 변경했다.
  • 통계학적 지식이 부족해 인덱스 목록에 대해 중복 조합 연산을 했었는데 잘못됨을 인지하고 중복 순열로 변경했다.
  • 열쇠와 자물쇠의 돌기가 만나선 안된다는 부분을 처리하지 않아 특정 케이스에 대해 실패가 발생하는 이유를 인지하지 못했다.
    XOR 연산도 하나의 방법일 수 있지만 대신에 두 배열의 합을 사용해 중복되는 부분을 판단했다.
  • 프로그래머스가 백준처럼 NumPy 라이브러리를 지원하지 않았다면 매우 난해한 문제였을테지만,
    다행히 NumPy 라이브러리를 활용해 비교적 단순한 방법으로 풀 수 있었다.

해설 코드 #

python
import numpy as np
from itertools import product

def solution(key, lock):
    key, lock = np.array(key), np.array(lock)
    rotated_keys = [np.pad(np.rot90(key, i),len(lock)-1) for i in range(4)]

    index_list = list(range(len(rotated_keys[0])-len(lock)+1))
    for rotated_key in rotated_keys:
        for i, j in list(product(index_list, index_list)):
            key = rotated_key[i:i+len(lock),j:j+len(lock)]
            if (0 not in np.logical_or(key,lock)) and (2 not in (key + lock)):
                return True

    return False

[프로그래머스/카카오 81301] 숫자 문자열과 영단어 (Python)

May 6, 2022
Algorithm, Programmers
Algorithm, Problem Solving, 프로그래머스, 프로그래머스 Lv1, Python, Dictionary

문제 링크 #

개요 #

  • 딕셔너리를 사용해 해결할 수 있는 문제다.

문제 조건 #

  • 일부 숫자가 영단어로 변환된 문자열을 원래의 숫자로 되돌려 반환하는 문제다.

문제 해설 #

  • 각각의 영단어에 대한 숫자 맵과 문자열의 replace 함수를 사용하면 쉽게 해결할 수 있다.

해설 코드 #

python
def solution(s):
    answer = s
    word_dict = {'zero':'0','one':'1','two':'2','three':'3',
                'four':'4','five':'5','six':'6','seven':'7',
                'eight':'8','nine':'9'}
    for key, value in word_dict.items():
        answer = answer.replace(key, value)
    return int(answer)

[프로그래머스/카카오 17676] 추석 트래픽 (Python)

May 6, 2022
Algorithm, Programmers
Algorithm, Problem Solving, 프로그래머스, 프로그래머스 Lv3, Python, Sliding Window

문제 링크 #

개요 #

  • datetime 라이브러리를 사용해 해결할 수 있는 문제다.

문제 조건 #

  • 트래픽 처리 종료 시간 및 처리 시간이 짝지어진 로그 문자열을 해석하여 초당 최대 처리량을 반환하는 문제다.

문제 해설 #

  • datetime과 timedelta 모듈을 활용하여 각각의 트래픽 로그에 대한 시작과 끝 시간을 계산한다.
  • 트래픽의 시작 또는 끝을 1초 구간의 시작으로 정의하고 해당 구간에서 시작됐거나 진행 중인 트래픽 수를 합산한다.
  • 합산된 트래픽 수 중에서 최댓값을 초당 최대 처리량으로 판단하여 반환한다.

한계 #

  • 트래픽 로그를 시작 시간과 끝 시간으로 분리하지 않고 시간 범위로 변환할 수 있다면,
    굳이 2N 길이의 반복문을 사용하지 않고 교집합 연산을 사용해서 시간 복잡도를 개선할 수 있었을 것이다.

해설 코드 #

python
from datetime import datetime, timedelta

def solution(lines):
    answer = 0
    lines = sorted(map(interpret_log, lines))

    delta = timedelta(seconds=1)
    for start in sum(lines, []):
        t = sum([check_time_range(time_range, start, start+delta) for time_range in lines])
        answer = max(t, answer)
        start += delta

    return answer

def interpret_log(line):
    line = line.split()
    line = [word.split(s) for word, s in zip(line, ['-',':','s'])]
    Y,m,d,H,M,S,ms = list(map(int,line[0]+line[1][:-1]+line[1][-1].split('.')))
    end_date = datetime(Y,m,d,H,M,S,ms*1000)
    duration = line[2][0] if '.' in line[2][0] else line[2][0]+'.0'
    S,ms = list(map(int,duration.split('.')))
    start_date = end_date - timedelta(seconds=S,milliseconds=ms-1)

    return [start_date, end_date]

def check_time_range(time_range, start, end):
    con1 = start <= time_range[0] < end
    con2 = time_range[0] <= start <= time_range[1]
    return con1 or con2

[프로그래머스/카카오 42888] 오픈채팅방 (Python)

May 6, 2022
Algorithm, Programmers
Algorithm, Problem Solving, 프로그래머스, 프로그래머스 Lv2, Python, Dictionary

문제 링크 #

개요 #

  • 딕셔너리를 사용해 해결할 수 있는 문제다.

문제 조건 #

  • 채팅방 상태 메시지에 대해 닉네임 변경 사항을 적용하여
    최종적으로 UI 상에서 보여지는 메시지를 목록을 반환하는 문제다.

문제 해설 #

  • uid에 대한 닉네임이 짝지어진 딕셔너리(name_dict)를 기반으로 최종적인 닉네임 목록을 기록한다.
  • 메시지가 Enter와 Change로 시작하는 경우 닉네임이 설정 또는 변경된 것이라 인지하여 딕셔너리를 수정한다.
  • name_dict에서 uid에 대한 닉네임을 참조하여 상태 메시지를 조건에 맞는 형식으로 변환한다.

해설 코드 #

python
def solution(record):
    answer = []

    record = [rec.split() for rec in record]
    name_dict = {rec[1]:rec[2] for rec in record if rec[0] in {'Enter','Change'}}
    msg_dict = {'Enter':'들어왔습니다.','Leave':'나갔습니다.'}

    for rec in record:
        if rec[0] in {'Enter','Leave'}:
            answer.append(name_dict[rec[1]]+'님이 '+msg_dict[rec[0]])

    return answer

[프로그래머스/카카오 60057] 문자열 압축 (Python)

May 6, 2022
Algorithm, Programmers
Algorithm, Problem Solving, 프로그래머스, 프로그래머스 Lv2, Python, String

문제 링크 #

개요 #

  • 문자열 처리 능력이 요구되는 문제다.

문제 조건 #

  • 문자열에서 반복되는 문자 또는 단어를 압축하고 가장 짧게 압축된 길이를 반환한다.

문제 해설 #

  • 문자열을 단일 문자부터 2등분이 될 때까지 한 단위씩 늘려가면서 분리된 문자들에 대한 압축 과정을 진행한다.
  • 분리된 문자들을 순회하면서 반복되는 문자열을 무시하고 남은 문자열의 길이를 세는 방법도 있지만,
    여기선 문자열을 형식에 맞게 압축시키고 그 길이를 구한다.
  • 이전 문자열이 담길 메모리와 해당 문자열이 반복된 횟수를 기록하는 변수를 각각 선언한다.
  • 분리된 문자들을 순회하면서 현재 문자와 메모리가 다르면(반복되지 않으면)
    압축된 문자열에 메모리를 추가하고 초기화한다.
  • 모든 과정에 대한 최소 길이 값을 기록하고 반환한다.

해설 코드 #

python
def solution(s):
    answer = len(s)

    for unit in range(1,len(s)//2+1):
        s_range = list(range(0, len(s), unit))+[None]
        s_split = [s[s_range[i]:s_range[i+1]] for i in range(len(s_range)-1)]+['']
        new_s, memory, cnt = str(), s_split[0], 1
        for s_unit in s_split[1:]:
            if memory != s_unit:
                new_s += ((str(cnt) if cnt > 1 else str()) + memory)
                memory, cnt = s_unit, 1
            else:
                cnt += 1
        answer = min(answer, len(new_s))

    return answer

[프로그래머스/카카오 72410] 신규 아이디 추천 (Python)

May 6, 2022
Algorithm, Programmers
Algorithm, Problem Solving, 프로그래머스, 프로그래머스 Lv1, Python, Regex

문제 링크 #

개요 #

  • 정규식을 사용해 해결할 수 있는 문제다.

문제 조건 #

  • 유저가 제시한 아이디 문자열을 규칙에 맞게 변경하여 반환하는 문제다.

문제 해설 #

  • 제시된 조건에 대해 정규식을 구현하여 문자열에 적용하면 된다.
  • 정규식 활용 능력에 따라 더욱 간단한 코드로 구현할 수도 있다.

해설 코드 #

python
import re

def solution(new_id):
    answer = new_id.lower()
    answer = re.sub(r"[^a-z0-9-_\.]","",answer)
    answer = re.sub(r"\.+",".",answer)
    answer = re.sub(r"^\.","",answer)
    answer = re.sub(r"\.$","",answer)
    answer = 'a' if not answer else answer
    answer = answer[:15]
    answer = answer[:-1] if answer[-1] == '.' else answer
    answer += answer[-1]*(3-len(answer))
    return answer

[프로그래머스/카카오 92334] 신고 결과 받기 (Python)

May 6, 2022
Algorithm, Programmers
Algorithm, Problem Solving, 프로그래머스, 프로그래머스 Lv1, Python, Dictionary

문제 링크 #

개요 #

  • 딕셔너리를 사용해 해결할 수 있는 문제다.

문제 조건 #

  • 일정 횟수 이상 신고당한 불량 이용자를 신고한 이용자들에게 발송되는 메일의 횟수를 리스트로 반환하는 문제다.

문제 해설 #

  • 이용자 자신이 신고당한 횟수(report_dict)와 이용자가 신고한 대상 목록(mail_dict)을 각각 기록할 필요가 있다.
  • 각각의 신고 건수에 대해 반복하며 두 가지 딕셔너리에 기록한다.
  • 이용자id를 key로 참고하여 각각의 이용자마다 자신이 신고한 대상 중 정지된 대상의 수를 계산한다.

해설 코드 #

python
def solution(id_list, report, k):
    report_dict = {id: 0 for id in id_list}
    mail_dict = {id: set() for id in id_list}

    for rep in set(report):
        user, target = rep.split()
        report_dict[target] += 1
        mail_dict[user].add(target)

    answer = []

    for user, targets in mail_dict.items():
        answer.append(sum([1 if report_dict[target] >= k else 0
                            for target in targets]))

    return answer