이 글에서는 push, pop, top 연산과 함께 최솟값 조회(getMin)까지 모두 상수 시간 O(1)에 수행할 수 있는 스택을 파이썬으로 구현하는 방법을 알아봅니다. 일반적인 스택은 push, pop, top 연산은 빠르지만, 최솟값을 찾으려면 전체를 순회해야 하는 O(n)의 비용이 듭니다. 이 문제를 해결하는 핵심 아이디어는 이전 최솟값을 스택 자체에 함께 저장하는 것입니다.알고리즘 설계구현해야 할 네 가지 연산은 다음과 같습니다.push(x): 요소 x를 스택에 삽입pop(): 스택의 최상단 요소 제거top(): 스택의 최

문제 개요두 개의 연결 리스트 A와 B가 있다고 가정해 보겠습니다. 각 리스트에는 여러 개의 노드가 있으며, 우리가 구해야 할 것은 두 리스트가 만나는 교차점(intersection node)에 대한 참조입니다.예를 들어 입력이 intersectionVal = 8, A = [4,1,8,4,5], B = [5,0,1,8,4,5], skipA = 2, skipB = 3이라면, 이 값들은 A에서 앞의 2개 노드를, B에서 앞의 3개 노드를 건너뛴 지점부터 두 리스트가 같은 노드(8)를 공유한다는 의미입니다.해결 알고리즘이 문제는 해시맵(

문제 개요 부호 없는 32비트 정수 x가 하나 주어졌다고 가정해 봅시다. 이 숫자의 이진 표현에서 모든 비트의 순서를 거꾸로 뒤집는 것이 우리의 과제입니다. 예를 들어 이진 표현이 00000000000000000000001001110100이라면, 비트를 반전한 결과는 00101110010000000000000000000000이 됩니다. 마지막에는 비트를 뒤집은 후의 실제 숫자 값을 반환해야 합니다. 알고리즘 접근 방법 이 문제는 다음 단계를 따라 해결할 수 있습니다. 주어진 수를 n이라고 합니다. 결과를 저장할 변수 answer

이 글에서는 주어진 숫자 n이 행복한 숫자(Happy Number)인지 아닌지를 파이썬으로 판별하는 방법을 알아보겠습니다.행복한 숫자란?행복한 숫자는 다음과 같은 성질을 가진 수입니다. 임의의 양의 정수에서 시작하여 그 숫자를 각 자릿수의 제곱의 합으로 계속 바꾸어 나갈 때, 최종적으로 1에 도달하면 그 수는 행복한 숫자입니다. 반대로 1에 도달하지 못하고 같은 사이클을 무한히 반복하게 되면 행복한 숫자가 아닙니다.예시: 19숫자 19를 예로 들어 보겠습니다. 19는 행복한 숫자이므로 결과는 True가 됩니다.12 + 92 = 82

이진 트리가 주어졌을 때, 주어진 두 노드의 최소 공통 조상(Lowest Common Ancestor, LCA)을 찾는 문제입니다. 두 노드 p와 q의 LCA란, 트리 전체에서 p와 q를 모두 자손으로 가지면서 가장 깊은(낮은) 위치에 있는 노드를 의미합니다.예를 들어 이진 트리가 [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]와 같이 구성되어 있다면, 트리의 구조는 다음과 같습니다.위 트리에서 노드 2와 노드 8의 LCA는 6입니다. 두 노드 모두 6을 조상으로 가지며, 그보다 더 깊은 노드 중에서는 두 노

한 회사에서 어떤 제품 관리자가 새로운 제품을 개발하는 팀을 이끌고 있다고 가정해 봅시다. 최신 버전이 품질 검사에서 통과하지 못했고, 각 버전은 이전 버전을 기반으로 개발되기 때문에 한 번 잘못된(bad) 버전이 나오면 그 이후의 모든 버전 역시 잘못된 버전이 됩니다. 따라서 [1, 2, …, n]의 n개 요소로 이루어진 배열 A가 주어졌을 때, 우리는 이 배열에서 첫 번째 잘못된 버전을 찾아야 합니다.이 문제에서는 특정 버전이 잘못된 버전인지 여부를 알려주는 함수 isBadVersion(version_id)를 사용할 수 있습니다

소문자로 이루어진 문자열이 주어졌을 때, 문자열에 포함된 모음(vowel)들만 골라서 순서를 거꾸로 뒤집는 문제를 생각해 볼 수 있습니다. 예를 들어 문자열이 hello라면 모음 e와 o의 위치를 서로 바꿔 결과는 holle이 됩니다. 마찬가지로 programming은 prigrammong으로 변환됩니다.이 문제를 해결하기 위한 접근 방식은 다음과 같습니다.주어진 문자열을 순회하면서 모음을 찾아 별도의 리스트에 저장하고, 해당 모음의 인덱스(위치)도 함께 기록합니다.저장된 모음 리스트를 역순으로 뒤집습니다.인덱스 추적용 변수 idx

두 개의 배열 A와 B가 주어졌을 때, 두 배열에 공통으로 존재하는 원소들, 즉 교집합을 찾는 문제입니다. 예를 들어 A = [1, 4, 5, 3, 6]이고 B = [2, 3, 5, 7, 9]라면, 두 배열 모두에 포함된 원소는 3과 5이므로 교집합은 [3, 5]가 됩니다.해결 접근 방법이 문제는 해시맵(딕셔너리)을 이용해 각 원소의 등장 횟수를 추적하면 효율적으로 해결할 수 있습니다. 알고리즘은 다음과 같습니다.두 배열 A와 B를 입력받습니다.A의 길이가 B보다 작으면 두 배열을 서로 교환합니다. (더 긴 배열의 빈도수를 미리 계

이진 트리가 하나 주어졌을 때, 해당 트리의 지름(diameter) 길이를 계산하는 문제를 살펴보겠습니다.이진 트리의 지름이란 트리 안에 있는 임의의 두 노드 사이에서 가장 긴 경로의 길이를 의미합니다. 여기서 중요한 점은 이 경로가 반드시 루트(root)를 거쳐야 하는 것은 아니라는 것입니다.예를 들어 아래와 같은 트리가 있다고 가정해 보겠습니다. 경로 [4, 2, 1, 3] 또는 [5, 2, 1, 3]의 길이가 3이므로, 이 트리의 지름은 3이 됩니다.문제 해결 접근 방식이 문제는 DFS(깊이 우선 탐색)를 활용하면 효율적으로

문제 개요2n개의 정수로 이루어진 배열이 주어졌을 때, 이 숫자들을 (a1, b1), (a2, b2), ..., (an, bn) 형태로 n개의 쌍(pair)으로 묶어야 합니다. 목표는 모든 쌍에 대해 min(ai, bi)의 합, 즉 각 쌍에서 작은 값들의 총합이 최대가 되도록 만드는 것입니다.예를 들어 입력이 [1, 4, 3, 2]라고 가정해 보겠습니다. 이 경우 n은 2이며, 최대 합은 4가 됩니다. (1, 2)와 (3, 4)로 묶으면 min(1, 2) + min(3, 4) = 1 + 3 = 4가 되기 때문입니다.해결 접근 방법이

문제 소개문자열 J는 보석(Jewel)으로 간주되는 문자들의 목록을 나타내고, 문자열 S는 현재 가지고 있는 돌(Stone)들을 의미합니다. 이 문제의 목표는 돌 문자열 S에 포함된 문자 중, 보석 문자열 J에도 해당하는 것이 몇 개인지 세는 것입니다.여기서 주의할 점은 대소문자를 구분한다는 것입니다. 즉, a와 A는 서로 다른 문자로 취급됩니다.예시J = aZc → 보석은 a, Z, cS = catTableZebraPicnic결과: 보석에 해당하는 문자가 총 7개해결 접근 방법가장 직관적인 방법은 다음과 같습니다.문자열 J의 각

두 개의 문자열 A와 B가 있다고 가정해 봅시다. 이때 문자열 A를 회전시켜 가면서 어느 시점에서라도 B와 일치하는지 확인하고, 일치한다면 True를, 그렇지 않다면 False를 반환하는 문제입니다.예를 들어 A = abcde, B = bcdea라고 할 때, A를 왼쪽으로 한 칸 회전하면 bcdea가 되므로 결과는 True입니다.문제 해결 접근 방법이 문제는 다음 단계에 따라 해결할 수 있습니다.A와 B가 모두 빈 문자열이라면 True를 반환합니다.A와 B의 길이가 다르다면 회전으로 같아질 수 없으므로 False를 반환합니다.A를

염소 라틴어(Goat Latin)란?영어로 작성된 문장이 주어졌을 때, 이를 특정 규칙에 따라 변환하는 것이 이번 문제의 목표입니다. 염소 라틴어(Goat Latin)는 잘 알려진 피그 라틴어(Pig Latin)와 유사한 언어 유희로, 다음 세 가지 조건을 따릅니다.모음으로 시작하는 단어: 단어 끝에 ma를 그대로 붙입니다.자음으로 시작하는 단어: 맨 앞 글자를 잘라내어 단어 끝으로 옮긴 뒤, ma를 붙입니다.인덱스별 a 추가: 문장 내 단어의 순서(1부터 시작)만큼 단어 끝에 a를 반복해서 붙입니다.예를 들어 Adam wants

문제 소개A와 B라는 두 친구가 서로 다른 크기의 사탕 바를 가지고 있다고 가정해 봅시다. 여기서 A[i]는 A가 가진 i번째 사탕 바의 크기를, B[j]는 B가 가진 j번째 사탕 바의 크기를 의미합니다.두 사람은 친구이기 때문에 각자 사탕 바 하나씩을 서로 교환한 뒤, 두 사람이 가진 사탕의 총량(가진 사탕 바 크기들의 합)이 완전히 같아지도록 만들고 싶어 합니다. 따라서 우리는 정수 배열 ans를 반환해야 하며, ans[0]에는 A가 내놓아야 할 사탕 바의 크기를, ans[1]에는 B가 내놓아야 할 사탕 바의 크기를 담으면 됩니

숫자로 이루어진 배열 A가 있을 때, 배열 안의 숫자들을 짝수가 먼저 오고 그 뒤에 홀수가 오도록 재배치해야 하는 문제를 생각해 볼 수 있습니다.예를 들어 배열이 A = [1, 5, 6, 8, 7, 2, 3]이라면, 결과는 [6, 8, 2, 1, 5, 7, 3]처럼 앞쪽에는 짝수, 뒤쪽에는 홀수가 배치되어야 합니다.해결 접근 방식이 문제는 두 포인터(two pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.포인터 i와 j를 모두 0으로 초기화합니다.j가 배열의 길이보다 작은 동안

문자열 S가 주어졌을 때, 영문자가 아닌 문자들은 원래 위치에 그대로 두고 영문자들의 위치만 서로 뒤바꾼 새로운 문자열을 구하는 문제입니다. 예를 들어 입력이 a-bC-dEf-ghIj라면 하이픈(-)의 위치는 변하지 않고 영문자만 역순으로 배치되어 j-Ih-gfE-dCba가 출력됩니다. 해결 접근 방식 이 문제는 두 포인터(two pointer) 기법으로 효율적으로 해결할 수 있습니다. 앞쪽을 가리키는 index1과 뒤쪽을 가리키는 index2를 사용해 다음 단계대로 진행합니다. 문자열 S가 비어 있으면 그대로 반환합니다. 결과

정수로 이루어진 배열 A와 쿼리 배열 queries가 주어졌다고 가정해 봅시다. i번째 쿼리에서는 value = queries[i][0], index = queries[i][1]이며, 각 쿼리마다 A[index]에 value를 더하게 됩니다. 그런 다음 i번째 쿼리의 답은 배열 A에 남아 있는 짝수 값들의 합입니다. 우리가 해야 할 일은 모든 쿼리에 대한 답을 순서대로 담은 배열, 즉 answer[i]가 i번째 쿼리의 답이 되는 배열을 반환하는 것입니다.문제 이해하기예를 들어 배열이 [1, 2, 3, 4]이고, 쿼리 배열이 [[1,

어떤 숫자가 배열 형태로 저장되어 있다고 가정해 봅시다. 예를 들어 숫자가 534라면 [5, 3, 4]처럼 각 자릿수별로 저장되는 방식입니다. 이번 문제는 이러한 배열 형태의 숫자에 또 다른 정수 k를 더하고, 그 결과 역시 자릿수 배열 형태로 반환하는 것입니다.문제 해결 접근 방법이 문제는 다음과 같은 단계로 해결할 수 있습니다.배열의 각 자릿수를 문자열로 변환한 뒤 하나의 문자열로 연결합니다.연결된 문자열을 정수(int)로 변환하고, 여기에 k를 더합니다.결과값을 다시 문자열로 변환한 후, 각 자릿수를 분리하여 새로운 배열을 만

10진수로 표현된 숫자가 하나 주어졌다고 가정해 봅시다. 이 숫자를 2진수 형태로 변환한 뒤 각 비트를 반전시켜 보수(complement)를 구하고, 그 결과를 다시 10진수로 바꿔 반환하는 것이 목표입니다. 예를 들어 숫자가 20이라면, 2진수 표현은 10100입니다. 각 비트를 반전하면 01011이 되고, 이를 다시 10진수로 변환하면 11이 됩니다. 해결 접근 방법 이 문제는 다음 단계를 따라 해결할 수 있습니다. 숫자 n의 2진수 문자열을 s에 저장합니다. (Python의 bin() 함수는 0b10100처럼 접두사 0b를

문제 이해하기 노래 목록이 하나 주어져 있고, i번째 노래의 재생 시간이 time[i]초라고 가정해 보겠습니다. 우리가 구해야 할 것은 두 노래의 재생 시간을 초 단위로 더했을 때 그 합이 60으로 나누어 떨어지는 노래 쌍의 개수입니다. 예를 들어 time 배열이 [30, 20, 150, 100, 40]이라면 정답은 3입니다. 실제로 (30, 150), (20, 100), (20, 40)이라는 세 쌍은 각각 재생 시간의 합이 180초, 120초, 60초로 모두 60으로 나누어 떨어지기 때문입니다. 해결 접근 방법 모든 노래 쌍을