LeetCode 121 Best Time to Buy and Sell Stock 풀이: 최저가를 유지하는 그리디
LeetCode 121 Best Time to Buy and Sell Stock을 한 번 훑으며 최저 매수가와 최대 이익을 갱신한다. 매수일이 매도일보다 앞서야 하는 조건을 지키면서 O(n) 시간과 O(1) 공간에 푸는 방법을 설명한다.
#난이도 2
기초 알고리즘 이해가 필요한 난이도 2 코딩테스트 문제를 다룬다. 현재 24개의 풀이가 있다.
LeetCode 704 Binary Search 풀이: 정렬 배열 이분 탐색
LeetCode 704 Binary Search를 정렬된 배열에서 이분 탐색으로 푼다. 닫힌 구간의 불변식과 경계 갱신을 확인하고, O(log n) 시간과 O(1) 공간으로 목표값의 인덱스를 찾는다.
LeetCode 49 Group Anagrams 풀이: 문자 빈도 해시로 애너그램 그룹화
LeetCode 49 Group Anagrams에서 각 단어의 문자 빈도를 튜플 키로 바꿔 애너그램을 묶는다. 정렬 없이 O(mn) 시간에 그룹을 만드는 방법을 살펴본다.
LeetCode 875 Koko Eating Bananas 풀이: 가능 여부 판정 이분 탐색
LeetCode 875 Koko Eating Bananas에서 주어진 속도로 제한 시간 안에 먹을 수 있는지 판정한다. 이분 탐색으로 필요한 최소 시간당 섭취량을 찾는다.
LeetCode 703 Kth Largest Element in a Stream 풀이: 크기 k 최소 힙
LeetCode 703 Kth Largest Element in a Stream에서 상위 k개만 최소 힙에 유지한다. 새 값이 들어오면 힙 크기를 조절해 k번째 큰 값을 O(log k)에 확인한다.
LeetCode 238 Product of Array Except Self 풀이: 접두사·접미사 곱 누적
LeetCode 238 Product of Array Except Self에서 나눗셈 없이 접두사 곱과 접미사 곱을 결합한다. 결과 배열을 재사용해 0이 포함된 입력도 O(n) 시간과 O(1) 추가 공간에 처리한다.
LeetCode 206 Reverse Linked List 풀이: 포인터 방향을 뒤집는 반복문
LeetCode 206 Reverse Linked List에서 각 노드의 next를 이전 노드로 바꾼다. 다음 노드를 먼저 저장해 연결을 잃지 않고 O(n) 시간과 O(1) 공간에 리스트를 뒤집는다.
LeetCode 74 Search a 2D Matrix 풀이: 2차원 배열을 평탄화한 이분 탐색
LeetCode 74 Search a 2D Matrix에서 행렬을 하나의 정렬된 배열처럼 보고 이분 탐색한다. 가상 1차원 인덱스를 행·열 좌표로 바꿔 O(log(mn)) 시간과 O(1) 공간에 target을 찾는다.
LeetCode 167 Two Sum II 풀이: 정렬 배열 양끝 투 포인터
LeetCode 167 Two Sum II에서 정렬된 배열의 양끝 포인터를 움직여 target을 찾는다. 합의 크기에 따라 후보를 줄여 O(n) 시간과 O(1) 공간에 1-based 인덱스를 반환한다.
LeetCode 125 Valid Palindrome 풀이: 양끝 투 포인터 문자열 판정
LeetCode 125 Valid Palindrome에서 양끝 포인터로 문자를 비교하며 특수문자는 건너뛴다. 대소문자를 무시하고 숫자를 포함하는 조건을 한 번의 순회로 처리한다.
LeetCode 20 Valid Parentheses 풀이: 괄호 짝과 순서를 확인하는 스택
LeetCode 20 Valid Parentheses에서 여는 괄호를 스택에 쌓고 닫는 괄호의 짝과 순서를 확인한다. 한 번 순회해 O(n) 시간과 O(n) 공간에 중첩 구조를 검증한다.
프로그래머스 의상 풀이: 카테고리별 조합의 곱셈 법칙
프로그래머스 의상에서 종류별 개수를 센 뒤 각 종류의 선택지를 곱하고, 아무것도 고르지 않은 경우를 뺀다. 곱셈 법칙으로 조합 수를 계산한다.
프로그래머스 유연근무제 풀이: 시간 변환과 요일 판별
프로그래머스 '유연근무제'에서 HHMM 시각을 분으로 바꾸고 요일을 계산한다. 주말을 제외한 출근 기록으로 조건을 만족하는 직원 수를 구한다.
프로그래머스 지폐 접기 풀이: 긴 변을 줄이는 그리디
프로그래머스 PCCE 지폐 접기에서 매번 긴 변을 절반으로 줄여 지갑에 들어가는지 확인한다. 90도 회전 가능한 크기 비교와 최소 접기 횟수를 다룬다.
프로그래머스 H-Index 풀이: 정렬 후 인용 수와 순위 비교
프로그래머스 H-Index에서 인용 횟수를 내림차순으로 정렬하고 현재 순위와 비교한다. 인용 횟수가 순위보다 작아지는 경계에서 H-Index를 구한다.
프로그래머스 멀쩡한 사각형 풀이: 최대공약수로 대각선 격자 계산
프로그래머스 멀쩡한 사각형에서 전체 칸 수와 대각선이 지나는 칸 수의 차이를 구한다. 최대공약수로 반복되는 대각선 패턴을 계산하는 방법을 설명한다.
프로그래머스 점프와 순간 이동 풀이: 홀수 위치만 점프하는 그리디
프로그래머스 점프와 순간 이동에서 목적지부터 거꾸로 이동하며 홀수 위치에서만 배터리를 쓴다. 짝수 위치는 순간 이동으로 절반씩 줄여 최소 점프 수를 구한다.
프로그래머스 구명보트 풀이: 정렬과 양끝 투 포인터 그리디
프로그래머스 구명보트에서 가장 무거운 사람과 가장 가벼운 사람을 함께 태울 수 있는지 확인한다. 정렬된 배열의 양끝 포인터로 필요한 보트 수를 센다.
프로그래머스 공원 풀이: 가장 큰 돗자리 찾기
프로그래머스 PCCE 공원에서 큰 돗자리부터 각 시작 위치에 놓을 수 있는지 확인한다. 2차원 배열에서 정사각형 영역이 모두 비어 있는지 검사한다.
프로그래머스 비밀지도 풀이: 비트 OR와 고정 길이 이진수
프로그래머스 비밀지도에서 두 지도의 값을 비트 OR로 합쳐 벽과 공백을 구분한다. 이진수 변환 뒤 앞쪽 0을 채워 고정 길이 지도를 만든다.
프로그래머스 서버 증설 횟수 풀이: 만료 시점을 관리하는 구현
프로그래머스 서버 증설 횟수에서 시간별 운영 서버와 반납 시점을 관리한다. 필요한 서버 수와 현재 서버 수의 차이로 추가 증설 횟수를 계산한다.
프로그래머스 스킬트리 풀이: 선행 스킬 접두사 판정
프로그래머스 스킬트리에서 선행 스킬에 포함된 문자만 추려 순서를 확인한다. 추출 결과가 선행 스킬 순서의 접두사인지 판정한다.
프로그래머스 올바른 괄호 풀이: 카운터로 여는 괄호 관리
프로그래머스 올바른 괄호에서 여는 괄호와 닫는 괄호의 잔량을 카운터로 관리한다. 닫는 괄호가 앞서는 순간 종료하고 마지막 잔량을 확인해 O(1) 공간에 판정한다.
프로그래머스 동영상 재생기 풀이: 시간 변환과 시뮬레이션
프로그래머스 PCCP 동영상 재생기에서 시각을 초로 바꿔 명령어를 시뮬레이션한다. 오프닝 자동 건너뛰기와 영상 끝 경계를 처리하는 방법을 다룬다.