프로그래머스 | 문자열 압축 파이썬

문제 설명 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘..

• format_list_bulleted 공부하자!/알고리즘
• · 2021. 8. 17.
• textsms

프로그래머스 | 멀쩡한 사각형 파이썬

문제 설명 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다. 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solutio..

• format_list_bulleted 공부하자!/알고리즘
• · 2021. 8. 17.
• textsms

백준 1406 에디터 파이썬

문제 풀이 첫 번째 시도 for _ in range(M): t = list(map(str, sys.stdin.readline())) if t[0] == 'L' and cursor != 0: cursor -= 1 elif t[0] == 'D' and cursor != len(N): cursor += 1 elif t[0] == 'B' and cursor != 0: del N[cursor - 1] cursor -= 1 elif t[0] == 'P': N.insert(cursor, t[2]) cursor += 1 시간 초과가 나왔다. insert와 del을 썼는데, 시간복잡도가 O(n)이어서 그런 것 같았다. 두 번째 시도 시간복잡도 O(1)인 append, pop을 써서 다시 시도! 커서를 옮길 때 curso..

• format_list_bulleted 공부하자!/알고리즘
• · 2021. 8. 3.
• textsms

프로그래머스 | 불량 사용자 파이썬

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

• format_list_bulleted 공부하자!/알고리즘
• · 2021. 8. 3.
• textsms

백준 10816번 숫자 카드 2 파이썬

숫자 카드 1이랑 똑같은 문제다! 하고 방심했는데 아니었음.. 해쉬테이블 배워둬서 정말 다행이야!! A 안의 요소 있으면 해쉬테이블 안에 +1 씩 하고 나중에 그걸 출력하면 된다~ 마지막에 출력할 때는 없는 부분은 0으로 바꿔야 함! # 숫자 카드 2 import sys N = int(sys.stdin.readline()) A = list(map(int, sys.stdin.readline().split())) M = int(sys.stdin.readline()) B = list(map(int, sys.stdin.readline().split())) hashmap = {} for i in A: if i in hashmap: hashmap[i] += 1 else: hashmap[i] = 1 print(' '..

• format_list_bulleted 공부하자!/알고리즘
• · 2021. 6. 11.
• textsms

백준 10815 파이썬 숫자 카드

처음에는 그냥 하나하나 다 탐색해야 하는 건 줄 알고 가볍게 풀었다. import sys N = int(sys.stdin.readline()) A = list(map(int, sys.stdin.readline().split())) M = int(sys.stdin.readline()) B = list(map(int, sys.stdin.readline().split())) for i in range(len(B)): if B[i] in A: B[i] = 1 else: B[i] = 0 for i in B: print(i, end=' ') 쉽다쉬워~ 그런데 계속 시간초과가 뜬다. 알고리즘 뭐 쓰이는지 봤더니 이분탐색..! 주어지는 리스트의 크기가 작지 않은 이상 전체 탐색은 시간이 너무 오래 걸리는 것이었다 im..

• format_list_bulleted 공부하자!/알고리즘
• · 2021. 6. 9.
• textsms