Algorithm

🗂️ 문제 링크: https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 💡 접근법 단어의 알파벳 하나하나를 스택의 마지막 요소와 비교한다. 이때 같을 경우 스택의 마지막 요소를 pop하고, 같지 않을 경우 알파벳을 스택에 append한다. 알파벳을 모두 순회하고 결과적으로 스택이 비어있다면 좋은 단어로 판단할 수 있다. 😎 내 코드 import sys N = int(sys.stdin.readline()) words = [] for _ in range(N): w..

🗂️ 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42746 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 접근법 numbers 리스트 내 값들의 자릿수를 3자리로 맞춘다. 자릿수를 맞출 때 부족한 자릿수만큼 첫 번째 자리에 해당하는 수로 채운다. 즉 numbers=[3, 30, 34, 5, 9] → numbers=[333, 303, 343, 555, 999]가 된다. 이를 정렬하면 numbers = [999, 555, 343, 333, 303]이다. 이것의 원래 값을 이어붙여서 ..

🗂️ 문제 링크: https://www.acmicpc.net/problem/1141 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net 💡 접근법 접두사X 집합이란 집합의 어떤 한 단어가 다른 단어의 접두어가 되지 않는 집합을 말한다. 즉 전체 집합에서 다른 단어의 접두어가 되는 단어들 제외한 단어들의 개수를 구하는 문제이다. 리스트를 정렬하고 각각의 요소를 순회하면서 현재 문자열이 다음 문자열에 접두어가 되는지 확인한다. 여기서 문자열을 정렬했기 때문에..

🗂️ 문제 링크: https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 💡 접근법 가운데를 말해요 문제와 비슷한 문제이다. 즉, 최대 힙과 최소 힙을 생성하여 중앙값을 구하면 된다. leftHeap에는 중간값보다 같거나 작은 값들이 저장되고, rightHeap에는 중간값보다 큰 값들이 저장된다. leftHeap의 루트를 중간값으로 꺼낼 것이다. 이때 만약 수의 개수가 짝수 개라면 중간에 있는 두 수 중 작은 수를 말해야 ..

🗂️ 문제 링크: https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 💡 접근법 중간값을 뽑아내기 위해서 최대 힙(leftHeap)과 최소 힙(rightHeap), 총 2개의 힙을 사용한다. leftHeap에는 중간값보다 같거나 작은 값들이 저장되고, rightHeap에는 중간값보다 큰 값들이 저장된다. leftHeap의 루트를 중간값으로 꺼낼 것이다. 이때 만약 수의 개수가 짝수 개라면 중간에 있는 두 수 중 작은 수를 말해야 한..

🗂️ 문제 링크: https://www.acmicpc.net/problem/14235 14235번: 크리스마스 선물 크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 www.acmicpc.net 💡 접근법 heapq 라이브러리를 사용하여 a가 0이 아니라면 선물의 가치를 heap에 저장하고, a가 0이라면 선물의 가치가 큰 순서대로 힙에서 요소를 꺼내 출력한다. 이때 힙에 남아있는 요소의 개수가 0이라면 -1을 출력한다. 또한 최대힙을 구성하기 위해 push할때 -부호를 붙여서 힙에 요소를 넣어주고, pop할 때는 -부호를 붙여서 출력한다. 😎 내 코드 import sys..

🗂️ 문제 링크: ttps://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 💡 접근법 heapq 라이브러리를 사용하면 간단하게 풀 수 있다. 입력으로 들어오는 값들을 1차원 리스트로 만든다. 이때 메모리 초과를 고려하여 heap의 크기를 N으로 고정해야 한다. 따라서 heapq.nlargest(N, arr)를 사용하여 arr에 N번째까지 큰 수들만 남기면서 새로운 입력 값들을 arr에 업데이트한다. 😎 내 코드 import heapq import sys N = ..

🗂️ 문제 링크: https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 💡 접근법 N의 범위가 1,000,000이므로 시간복잡도 O(NLogN)을 갖는 정렬 알고리즘을 사용해야 한다. 파이썬 내장 정렬함수, 퀵정렬, 병합정렬, 힙정렬이 제한 시간 내에 해결할 수 있는 알고리즘이다. 이 중 힙정렬을 사용하여 구현한다. 파이썬의 heapq 라이브러리는 최소 힙으로 구현되어 있기 때문에 heap 배열을 생성하여 입력값을 push하고 하나씩 po..