티스토리

개발하는 장씨

검색하기

블로그 홈

개발하는 장씨

dev-jjang.tistory.com/m

장호진의 개발 블로그

구독자: 3

방명록 방문하기

주요 글 목록

프로그래머스 [디펜스 게임] 📌 프로그래머스 [디펜스 게임]🔗 문제 링크문제 설명 📄n개의 병력을 가지고 있으며, enemy 리스트에 나타나는 적들과 매 라운드 전투를 진행해야 한다.단, 최대 k번은 병력을 사용하지 않고 방어할 수 있다.방어 기회를 최적화하여 가장 많은 라운드를 버틸 수 있도록 해야 한다.문제 접근 방식 💡우선순위 큐 (heapq)를 사용하여 가장 적은 병력의 적을 우선적으로 넘긴다.현재 적이 기존에 넘긴 적 중 최소값(q[0])보다 크다면 교체한다.병력(n)을 초과하여 소모하면 게임 종료.Solution 💻import heapqdef solution(n, k, enemy): answer = 0 q = [] for enem in enemy: if len(q) = enem.. 공감수 0 댓글수 0 2025. 2. 19.
프로그래머스 [리코쳇 로봇] 📌 프로그래머스 [리코쳇 로봇]🔗 문제 링크문제 설명 📄2차원 보드에서 R(로봇) → G(목표 지점)까지의 최소 이동 횟수를 구하는 문제.로봇은 상하좌우로 움직일 수 있지만, 한 번 움직이면 벽 또는 D(장애물)에 부딪힐 때까지 미끄러진다.최소 이동 횟수를 반환하고, 도달할 수 없는 경우 -1을 반환해야 한다. 문제 접근 방식 💡BFS(너비 우선 탐색) 를 사용하여 최단 경로 탐색.R의 시작 위치를 찾고, 큐에 (좌표, 이동 횟수) 를 넣어 탐색 시작.4방향 이동 후 벽이나 장애물에서 멈춘 지점을 새로운 탐색 지점으로 추가.방문한 위치를 visit 집합으로 저장하여 중복 탐색 방지.목표 지점 G에 도달하면 이동 횟수를 반환, 끝까지 도달하지 못하면 -1을 반환.Solution 💻from coll.. 공감수 1 댓글수 1 2025. 2. 18.
프로그래머스 [행렬 테두리 회전하기] 📌 프로그래머스 [행렬 테두리 회전하기]🔗 문제 링크문제 설명 📄rows × columns 크기의 행렬이 주어지며, 일부 영역의 테두리를 시계방향으로 회전시키는 연산을 수행해야 한다.각 회전 후, 회전된 값들 중 최솟값을 반환하는 문제.문제 접근 방식 💡2차원 배열을 생성하여 초기 행렬을 구성.주어진 queries를 순회하며 해당 범위의 테두리를 회전.회전 과정:상, 우, 하, 좌 순서로 테두리를 이동.이동 중 만난 숫자들의 최솟값을 추출.최솟값을 answer 리스트에 추가 후 반환.Solution 💻def solution(rows, columns, queries): answer = [] arr = [[i + (columns * j) for i in range(1, columns + .. 공감수 0 댓글수 0 2025. 2. 18.
프로그래머스 [수식 최대화] 📌 프로그래머스 [수식 최대화]🔗 문제 링크문제 설명 📄주어진 수식에서 연산자의 우선순위를 조정하여 최댓값을 구하는 문제.가능한 연산자는 +, -, *이며, 이들의 우선순위를 자유롭게 설정할 수 있음.연산자의 우선순위에 따라 계산을 수행한 후, 최댓값을 반환해야 함.문제 접근 방식 💡토큰화: 정규 표현식을 활용하여 숫자와 연산자를 분리.우선순위 조합 생성: permutations을 이용하여 연산자 우선순위 경우의 수 생성.계산 수행:현재 우선순위에 따라 반복적으로 연산을 수행.deque를 활용하여 좌에서 우로 연산을 적용하며 피연산자를 갱신.최댓값 갱신: 모든 경우의 수를 수행한 후, 절댓값이 가장 큰 결과 반환.Solution 💻import refrom itertools import permu.. 공감수 0 댓글수 0 2025. 2. 18.
백준 [11052]: 카드 구매하기 📌 백준 [11052]: 카드 구매하기🔗 문제 링크문제 설명 📄카드 팩의 개수 n이 주어지고, 각 팩의 가격이 주어진다.n개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구하시오.문제 접근 방식 💡동적 프로그래밍(DP)을 사용하여 최대 구매 비용을 계산.dp[i]를 i개의 카드를 구매할 때의 최대 비용으로 정의.점화식:dp[i] = max(dp[i], dp[i-j] + cards[j])여기서 j는 선택한 카드 팩의 개수를 의미.초기값:dp[0] = 0 (카드를 구매하지 않은 경우).Solution 💻n = int(input())cards = [0] + list(map(int, input().split()))dp = [0] * (n + 1)for i in range(1, n + 1): .. 공감수 0 댓글수 0 2025. 1. 22.
백준 [1309]: 동물원 📌 백준 [1309]: 동물원🔗 문제 링크문제 설명 📄가로의 길이가 2이고 세로의 길이가 N인 우리에 사자를 배치하려 한다.사자는 가로로 붙어있는 두 칸에 함께 있을 수 없다.우리에 사자를 배치하는 방법의 수를 9901로 나눈 나머지를 구하시오.문제 접근 방식 💡동적 프로그래밍(DP)을 사용하여 사자를 배치하는 경우의 수를 계산.세 가지 경우를 고려:사자를 왼쪽 칸에 배치 (b)사자를 오른쪽 칸에 배치 (c)사자를 배치하지 않음 (a)점화식:a(n) = a(n-1) + b(n-1) + c(n-1) (배치하지 않는 경우)b(n) = a(n-1) + c(n-1) (왼쪽에 배치)c(n) = a(n-1) + b(n-1) (오른쪽에 배치)최종 답은 a + b + cSolution 💻n = int(inpu.. 공감수 0 댓글수 0 2025. 1. 21.
백준 [1890]: 점프 📌 백준 [1890]: 점프🔗 문제 링크문제 설명 📄N×N 크기의 게임판이 주어진다. 각 칸에는 해당 칸에서 이동할 수 있는 거리가 적혀 있다.오른쪽 또는 아래쪽으로만 이동 가능하며, 도착점 (N-1, N-1)에 도달할 수 있는 경로의 개수를 구하시오.시작점은 (0,0)이며, 도착점의 값은 항상 0이다.문제 접근 방식 💡재귀 + 메모이제이션을 사용하여 도착점까지의 경로 개수를 계산.dp[x][y]를 (x, y)에서 도착점까지 도달할 수 있는 경로의 수로 정의.종료 조건:(x, y)가 도착점이면 1 반환.arr[x][y] == 0이면 이동 불가하므로 0 반환.점화식:오른쪽과 아래쪽 이동을 고려해 dp[x][y] = count_paths(x + step, y) + count_paths(x, y + s.. 공감수 0 댓글수 1 2025. 1. 20.
백준 [11053]: 가장 긴 증가하는 부분 수열 📌 백준 [11053]: 가장 긴 증가하는 부분 수열🔗 문제 링크문제 설명 📄수열 A가 주어졌을 때, 그 수열의 부분 수열 중에서 가장 긴 증가하는 부분 수열의 길이를 구하시오.예를 들어, A = [10, 20, 10, 30, 20, 50]일 때 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]로 길이는 4이다.문제 접근 방식 💡동적 프로그래밍(DP)을 사용하여 각 원소를 기준으로 증가하는 부분 수열의 길이를 계산.dp[i]를 arr[i]를 끝으로 하는 가장 긴 증가하는 부분 수열의 길이로 정의.점화식:dp[i] = max(dp[j] + 1) (단, j 초기값:dp[i] = 1 (최소한 자기 자신 하나로 구성된 수열의 길이는 1).Solution 💻n = int(input())arr .. 공감수 0 댓글수 0 2025. 1. 18.
백준 [10844]: 쉬운 계단 수 📌 백준 [10844]: 쉬운 계단 수🔗 문제 링크문제 설명 📄길이가 N인 계단 수의 개수를 구하시오.계단 수는 다음 조건을 만족하는 숫자이다:숫자의 각 자릿수가 인접한 자릿수보다 1만큼 차이가 남.0으로 시작하는 숫자는 계단 수가 아님.결과를 1,000,000,000으로 나눈 나머지를 출력하시오.문제 접근 방식 💡동적 프로그래밍(DP)을 사용하여 길이가 N인 계단 수를 계산.dp[i][j]를 길이가 i이고 마지막 자릿수가 j인 계단 수의 개수로 정의.점화식:dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]경계 조건:j=0이면, dp[i][j] = dp[i-1][1]j=9이면, dp[i][j] = dp[i-1][8]초기값:dp[1][j] = 1 (단, j ≠ 0).Solutio.. 공감수 1 댓글수 0 2025. 1. 18.
백준 [1699]: 제곱수의 합 📌 백준 [1699]: 제곱수의 합🔗 문제 링크문제 설명 📄자연수 n이 주어졌을 때, 자연수들의 제곱수의 합으로 표현할 때 필요한 최소 개수를 구하시오.예를 들어 n=7일 때, 4+1+1+1로 4개의 제곱수의 합으로 표현할 수 있고, 이는 최소값이다.문제 접근 방식 💡동적 프로그래밍(DP)을 활용하여 최소 제곱수 개수를 계산.dp[i]를 자연수 i를 제곱수의 합으로 표현할 때 필요한 최소 개수로 정의.점화식:dp[i] = min(dp[i], dp[i - j*j] + 1) (j*j 초기값:dp[0] = 0.Solution 💻n = int(input())dp = [float('inf')] * (n + 1)dp[0] = 0for i in range(1, n + 1): j = 1 while .. 공감수 0 댓글수 0 2025. 1. 16.
백준 [11048]: 이동하기 📌 백준 [11048]: 이동하기🔗 문제 링크문제 설명 📄N×M 크기의 미로가 주어진다. 각각의 칸에는 아이템의 개수가 적혀 있다.왼쪽 위에서 시작하여 오른쪽 아래까지 이동하려고 한다.이때, 한 번에 오른쪽, 아래쪽, 또는 대각선 아래로만 이동할 수 있다.아이템을 최대한 많이 줍기 위해 가져올 수 있는 아이템의 최대 개수를 구하시오.문제 접근 방식 💡동적 프로그래밍(DP) 배열 dp[i][j]를 사용하여 (i, j)까지 이동했을 때의 최대 아이템 개수를 저장.초기값: dp[0][0] = miro[0][0].점화식:dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + miro[i][j] (단, 경계를 벗어나지 않도록 조건 추가).Solution 💻n, .. 공감수 0 댓글수 0 2025. 1. 14.
백준 [11726]: 2×n 타일링 📌 백준 [11726]: 2×n 타일링🔗 문제 링크문제 설명 📄2×n 크기의 직사각형을 1×2와 2×1 타일로 채우는 방법의 수를 구하시오.결과를 10007로 나눈 나머지를 출력하시오.문제 접근 방식 💡동적 프로그래밍(DP)을 사용하여 타일 채우는 방법의 수를 계산.dp[i]를 2×i 크기의 직사각형을 채우는 방법의 수로 정의.점화식:dp[i] = dp[i-1] + dp[i-2]초기값:dp[1] = 1dp[2] = 2Solution 💻n = int(input())dp = [1] * nfor i in range(2, n): dp[i] = dp[i - 1] + dp[i - 2]print(dp[-1])시간 복잡도 분석 ⏲️시간 복잡도: O(n)1부터 n까지 반복문을 통해 DP 배열을 채움.공간 .. 공감수 0 댓글수 0 2025. 1. 14.
백준 [11057]: 오르막 수 📌 백준 [11057]: 오르막 수🔗 문제 링크문제 설명 📄수의 자릿수가 N이고, 각 자릿수가 0부터 9까지 증가하는 수를 오르막 수라고 한다.N이 주어졌을 때, 오르막 수의 개수를 10007로 나눈 나머지를 구하시오.문제 접근 방식 💡DP 테이블 dp[i][j]를 정의:i: 자리 수j: 마지막 자릿값이 j인 오르막 수의 개수점화식:dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + ... + dp[i-1][9]최종 결과:sum(dp[n-1]) % 10007Solution 💻n = int(input())dp = [[1] * 10 for _ in range(n)]for i in range(1, n): for j in range(10): dp[i][j] = sum.. 공감수 0 댓글수 0 2025. 1. 14.
백준 [11727]: 2×n 타일링 2 📌 백준 [11727]: 2×n 타일링 2🔗 문제 링크문제 설명 📄2×n 크기의 직사각형을 1×2, 2×1, 2×2 크기의 타일로 채우는 방법의 수를 구하시오.결과를 10007로 나눈 나머지를 출력하시오.문제 접근 방식 💡동적 프로그래밍(DP)을 사용하여 타일 채우는 방법의 수를 계산.dp[i]를 2×i 크기의 직사각형을 채우는 방법의 수로 정의.점화식:dp[i] = dp[i-1] + dp[i-2] * 2초기값:dp[1] = 1dp[2] = 3Solution 💻n = int(input())dp = [0] * (n + 1)if n == 1: print(1)elif n == 2: print(3)else: dp[1] = 1 dp[2] = 3 for i in range(3, .. 공감수 0 댓글수 0 2025. 1. 13.
백준 [2579]: 계단 오르기 📌 백준 [2579]: 계단 오르기🔗 문제 링크문제 설명 📄계단을 오를 때 다음 규칙을 따라야 한다:계단은 한 번에 한 계단 또는 두 계단씩 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다.마지막 계단은 반드시 밟아야 한다.각 계단에는 점수가 있으며, 계단을 밟을 때 그 점수가 더해진다. 계단의 점수가 주어질 때, 얻을 수 있는 총 점수의 최댓값을 구하시오.문제 접근 방식 💡동적 프로그래밍(DP)을 사용하여 최댓값을 계산.각 계단에서 얻을 수 있는 점수를 dp[i]로 정의.규칙을 만족하며 마지막 계단을 밟는 경우를 고려해 점수를 누적.Solution 💻stairs = [int(input()) for _ in range(int(input()))]if len(stairs) == 1: .. 공감수 0 댓글수 0 2025. 1. 12.
백준 [9095]: 1, 2, 3 더하기 📌 백준 [9095]: 1, 2, 3 더하기🔗 문제 링크문제 설명 📄정수 n이 주어졌을 때, 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.예를 들어, n=4라면 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1과 같이 7가지 방법이 있다.문제 접근 방식 💡재귀를 사용해 숫자를 1, 2, 3을 더해가며 n에 도달하는 모든 경우의 수를 계산.주어진 숫자를 초과하는 경우 탐색을 종료.최적화를 위해 재귀를 반복적으로 호출.Solution 💻count = int(input())def func(num): global answer global target if num == target: answer += 1 r.. 공감수 0 댓글수 0 2025. 1. 11.
백준 [1463]: 1로 만들기 📌 백준 [1463]: 1로 만들기🔗 문제 링크문제 설명 📄양의 정수 X가 주어질 때, 정수 X에 사용할 수 있는 연산은 다음과 같다:X가 3으로 나누어떨어지면, 3으로 나눈다.X가 2로 나누어떨어지면, 2로 나눈다.1을 뺀다.정수 X를 1로 만들기 위해 필요한 최소 연산 횟수를 구하라.문제 접근 방식 💡BFS(너비 우선 탐색)를 사용하여 최단 경로를 탐색.큐를 활용해 상태를 저장하고, 방문 여부를 체크하여 중복 계산 방지.Solution 💻from collections import dequeinput = int(input())q = deque()pattern = {}q.append((input,0))while q: p,count = q.popleft() if p in pattern.. 공감수 0 댓글수 0 2025. 1. 10.
LeetCode [962]: Maximum Width Ramp 📌 LeetCode [962]: Maximum Width Ramp🔗 https://leetcode.com/problems/maximum-width-ramp/문제 설명 📄주어진 배열 nums에서 가장 긴 Ramp를 찾아야 합니다. Ramp는 두 인덱스 (i, j)에 대해 다음 조건을 만족합니다:i nums[i] 목표는 가능한 Ramp 중 j - i를 최대화하는 값을 반환하는 것입니다.문제 접근 방식스택 빌드:배열을 왼쪽에서 오른쪽으로 순회하면서, 작아지는 값의 인덱스만 스택에 추가합니다.스택에는 Ramp의 시작점이 될 가능성이 있는 인덱스만 남습니다.스택 활용:배열을 오른쪽에서 왼쪽으로 순회하면서, 스택의 값과 비교해 Ramp를 계산합니다.스택의 값이 조건을 만족하면 길이를 계산하고, 더 이상 조건을.. 공감수 0 댓글수 0 2025. 1. 10.
LeetCode [528]: Random Pick with Weight 📌 LeetCode [528]: Random Pick with Weight🔗 https://leetcode.com/problems/random-pick-with-weight/문제 설명 📄0부터 시작하는 양의 정수 배열 w가 주어집니다.각 w[i]는 i번째 인덱스의 가중치를 나타냅니다.pickIndex() 함수는 각 인덱스를 가중치에 비례한 확률로 무작위 선택하여 반환해야 합니다.문제 접근 방식w의 전체 합을 계산하여 각 가중치를 비율로 구합니다.각 가중치를 누적 합 형태로 저장하여 확률 구간을 만듭니다.무작위로 생성된 값이 해당 구간에 속하는 인덱스를 반환합니다.효율성을 높이기 위해 이분 탐색을 사용하여 인덱스를 찾는 방식으로 리팩토링할 수 있습니다.Solution 💻import randomfro.. 공감수 0 댓글수 0 2025. 1. 9.
LeetCode [190]: Reverse Bits 📌 LeetCode [190]: Reverse Bits🔗 문제 링크문제 설명 📄32비트의 부호 없는 정수가 주어지면, 해당 정수의 비트를 뒤집은 값을 반환하세요.문제 접근 방식32비트 정수의 각 비트를 순차적으로 검사하며 뒤집는 방식으로 접근합니다.주어진 정수에서 비트를 오른쪽으로 이동시키며 최하위 비트를 추출합니다.추출된 비트를 결과 변수에 왼쪽으로 이동하여 반대로 삽입합니다.모든 비트를 처리한 후 결과를 반환합니다.Solution 💻class Solution: def reverseBits(self, n: int) -> int: result = 0 for _ in range(32): result = (result >= 1 return.. 공감수 0 댓글수 0 2025. 1. 8.
LeetCode [539]: Minimum Time Difference 📌 LeetCode [539]: Minimum Time Difference🔗 문제 링크문제 설명 📄주어진 시간 리스트에서 두 시간 간의 차이가 가장 작은 값을 계산하세요.시간은 "HH:MM" 형식의 문자열로 제공됩니다.하루는 1440분이며, 경계를 넘어가는 시간 차이도 고려해야 합니다.문제 접근 방식 🚶시간을 분 단위로 변환:각 "HH:MM" 문자열을 분 단위의 정수로 변환합니다.정렬:시간 값을 정렬하여 인접한 시간 간의 차이를 계산합니다.최소 차이 계산:인접한 시간 간의 차이를 계산하며 최소값을 업데이트합니다.첫 번째와 마지막 시간의 차이를 하루의 경계로 연결하여 계산합니다.Solution 💻class Solution: def findMinDifference(self, timePoints.. 공감수 0 댓글수 0 2025. 1. 7.
LeetCode [874]: Walking Robot Simulation 📌 LeetCode [874]: Walking Robot Simulation🔗 문제 링크문제 설명 📄로봇이 무한한 XY 평면에서 (0, 0)에서 시작하여 북쪽을 바라보고 있다.명령과 장애물 배열이 주어졌을 때, 로봇이 이동 중 도달할 수 있는 최대 제곱 거리를 계산하라.명령:-2: 왼쪽으로 90도 회전-1: 오른쪽으로 90도 회전1 장애물: 특정 위치에 있는 장애물 좌표.문제 접근 방식 🚶방향 정의:북, 동, 남, 서 순으로 이동 벡터를 정의.회전 명령에 따라 방향 인덱스를 갱신.전진 명령:장애물이 없는 경우에만 이동.이동 중 최대 유클리드 거리 제곱 값을 갱신.장애물 처리:장애물 좌표를 set으로 변환하여 빠른 조회 가능.Solution 💻class Solution: def robotSi.. 공감수 0 댓글수 0 2025. 1. 6.
LeetCode [53]: Maximum Subarray 📌 LeetCode [53]: Maximum Subarray🔗 문제 링크문제 설명 📄배열에서 연속된 부분 배열의 합 중 가장 큰 값을 반환합니다.Solution 💻from typing import Listclass Solution: def maxSubArray(self, nums: List[int]) -> int: max_sum = float('-inf') current_sum = 0 for num in nums: current_sum = max(num, current_sum + num) max_sum = max(max_sum, current_sum) return max_sum시간 복잡도.. 공감수 0 댓글수 0 2025. 1. 5.
LeetCode [1508]: Range Sum of Sorted Subarray Sums 📌 LeetCode [1508]: Range Sum of Sorted Subarray Sums🔗 문제 링크문제 설명 📄주어진 배열 nums에서 모든 부분합을 계산하고, 이를 오름차순으로 정렬했을 때 left번째부터 right번째까지의 부분합의 합을 반환해야 합니다. 결과는 10**9 + 7로 나눈 나머지를 반환합니다.문제 접근 방식 🔍부분합 계산과 정렬:배열에서 모든 부분합을 계산하면 시간 복잡도는 O(n²)입니다.이후 이를 정렬하여 특정 구간만 선택하면 추가적으로 O(n² x log(n²))의 비용이 발생합니다.효율적인 부분합 계산:최소힙을 활용하여 가장 작은 부분합부터 정렬된 순서로 처리합니다.힙 연산으로 시간 복잡도를 O(n² x log(n))로 줄일 수 있습니다.Solution 💻impo.. 공감수 1 댓글수 0 2025. 1. 5.
LeetCode [380]: Insert Delete GetRandom O(1) 📌 LeetCode [380]: Insert Delete GetRandom O(1)🔗 문제 링크문제 설명 📄다음의 연산을 평균적으로 O(1) 시간 복잡도로 지원하는 자료 구조를 설계하세요:insert(val) : 값을 삽입합니다. 값이 이미 존재하면 False를 반환하고, 그렇지 않으면 True를 반환합니다.remove(val) : 값을 삭제합니다. 값이 존재하지 않으면 False를 반환하고, 그렇지 않으면 True를 반환합니다.getRandom() : 자료 구조에서 임의의 값을 반환합니다. 각 값은 동일한 확률로 선택됩니다.문제 해결 접근 방법 🔍딕셔너리와 리스트를 조합하여 구현:딕셔너리는 값의 인덱스를 빠르게 접근하기 위해 사용합니다.리스트는 getRandom 연산에서 임의의 값을 O(1)로 .. 공감수 0 댓글수 0 2025. 1. 4.
LeetCode [560]: Subarray Sum Equals K 📌 LeetCode [560]: Subarray Sum Equals K🔗 문제 링크문제 설명 📄정수 배열 nums와 정수 k가 주어졌습니다.배열 nums에서 합이 정확히 k인 연속적인 부분 배열의 개수를 반환하세요.문제 해결 접근 🚀누적합(Prefix Sum)과 해시맵 활용누적합을 계산하며 이전에 나타난 누적합의 빈도를 해시맵(pattern)에 저장합니다.현재 누적합에서 k를 뺀 값이 해시맵에 존재한다면, 해당 값이 등장했던 지점 이후의 부분 배열이 k와 같은 합을 가진다는 뜻입니다.효율적인 계산한 번의 순회로 모든 경우를 계산하며, 시간 복잡도는 O(n)입니다.공간 복잡도는 누적합의 종류에 비례하며, 최악의 경우 O(n)입니다.Solution 💻from collections import def.. 공감수 0 댓글수 0 2025. 1. 3.
LeetCode [1717]: Maximum Score From Removing Substrings 📌 LeetCode [1717]: Maximum Score From Removing Substrings🔗 문제 링크문제 설명 📄문자열 s에서 다음 두 종류의 패턴을 제거할 수 있습니다:"ab" 제거 시 점수 x 추가"ba" 제거 시 점수 y 추가문자열을 적절히 조작하여 얻을 수 있는 최대 점수를 반환하세요.문제 해결 접근 🚀"ab"와 "ba" 중 점수가 더 높은 것을 먼저 제거합니다.점수 크기 (x와 y)에 따라 처리 순서를 결정하여 불필요한 계산을 줄입니다.스택을 활용하여 문자열을 효율적으로 조작합니다.두 번의 제거 과정을 거쳐 최종 점수를 계산합니다.Solution 💻class Solution: def maximumGain(self, s: str, x: int, y: int) -> in.. 공감수 0 댓글수 0 2025. 1. 2.
LeetCode [215]: Kth Largest Element in an Array 📌 LeetCode [215]: Kth Largest Element in an Array🔗 문제 링크문제 설명 📄정수 배열 nums와 정수 k가 주어질 때, 배열에서 k번째로 큰 요소를 반환하세요.k번째로 큰 요소는 배열이 정렬되었을 때의 k번째 요소를 의미합니다.문제 해결 접근 🧩최대 힙을 사용한 접근:모든 숫자를 -num 형태로 힙에 추가하여 최대 힙처럼 동작하도록 만듦.힙에서 k-1번 heappop으로 요소를 제거한 후, k번째로 큰 요소를 반환.시간 복잡도는 O(n + k log n).리팩토링 가능 여부:더 빠른 방법:Python의 heapq.nsmallest를 사용하여 O(n + k log n)에서 불필요한 반복 제거 가능.효율적 접근:nums.sort(reverse=True)를 사용해 .. 공감수 0 댓글수 0 2025. 1. 1.
LeetCode [179]: Largest Number 📌 LeetCode [179]: Largest Number🔗 문제 링크문제 설명 📄주어진 비음수 정수 배열 nums를 사용해 숫자를 조합하여 가장 큰 숫자를 생성하세요.결과는 문자열로 반환하며, 숫자가 0만 포함된 경우에는 "0"을 반환합니다.문제 해결 접근 🧩숫자를 조합하여 가장 큰 수를 만들기 위해 문자열로 변환.두 문자열 x와 y를 비교할 때, x+y와 y+x를 비교하여 정렬 순서를 결정.정렬된 숫자를 이어붙여 결과를 반환.첫 번째 숫자가 "0"인 경우 전체 숫자가 0이므로 "0"을 반환.Solution 💻원래 코드from functools import cmp_to_keyclass Solution: def largestNumber(self, nums: List[int]) -> str:.. 공감수 0 댓글수 0 2024. 12. 31.
LeetCode [1190]: Reverse Substrings Between Each Pair of Parentheses 📌 LeetCode [1190]: Reverse Substrings Between Each Pair of Parentheses🔗 문제 링크문제 설명 📄주어진 문자열 s에서 각 괄호 쌍 안에 있는 문자열을 뒤집은 결과를 반환하세요. 중첩된 괄호를 처리해야 하며, 모든 괄호는 유효합니다.문제 해결 접근문자열을 순회하면서 괄호에 따라 처리를 나눕니다.괄호가 열리면(() 재귀적으로 내부를 처리합니다.괄호가 닫히면()) 현재까지 쌓인 문자열을 뒤집어 반환합니다.문자열의 끝까지 탐색 후 스택에 남은 모든 문자를 합쳐 반환합니다.Solution 💻class Solution: def reverseParentheses(self, s: str) -> str: index = 0 def .. 공감수 0 댓글수 0 2024. 12. 30.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.