문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 유형 스택 문제 풀이 처음에는 인덱스를 사용한 순회 방식을 생각해 현재 인덱스를 다음 인덱스와 차례대로 비교하면서 큰 수를 만나면 다음 인덱스를 비교하는 방식으로 구현했다. 그 결과 테스트 케이스 20~22가 시간 초과가 발생했다. 인덱스를 사용한 순회 방식으로는 해결 안되는 테스트 케이스 인 것 같아 다른 방법을 찾아보던 중 스택을 사용하라는 힌트를 발견했다. 스택을 사용할 때는 다음의 사항을 고려했다. 가장 마지막 배열 요소부터 순회하며 스택에 추가한다. 그럼 스택에는 현재 요소 기준 뒤에..
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 유형 문자열, Map 문제 풀이 이번 문제는 문자열 타입의 두 숫자가 주어지고, 공통으로 나타나는 정수들을 이용하여 만들 수 있는 가장 큰 숫자를 반환하는 문제이다. 처음에 생각한 문제 접근법은 다음과 같다. 1. 숫자 X의 맵을 만들고, 각 자리에 해당하는 숫자가 나온 횟수를 저장한다. 2. 숫자 Y를 순회하면서 각 자리에 해당하는 숫자가 X에 있으면 공통으로 나타나는 숫자임을 확인하고 따로 저장한다. 3. '000'과 같은 수는 '0'을, 공통 수가 없으면 -1을, 그 이외의 수는 내림차순..
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 유형 큐, 투 포인터 문제 풀이 해당 문제는 두 큐가 주어지고, 각 큐의 총합이 같게 나오도록 pop과 insert한 횟수를 반환하는 문제이다. 처음에 pop과 push를 사용해 두 큐의 요소들을 이동시켰다. 하지만 이는 너무 많은 push, pop 연산이 일어나 다른 방법을 찾아보았다. 처음에는 각 큐에 투 포인터를 두고 요소를 넣고 빼고 해볼까 생각했지만 구현이 어려웠다. 그러다 두개의 큐를 합친 후 투 포인터를 사용하는 접근법 힌트를 얻고 문제를 구현할 수 있었다. 두 큐를 합친 후 하나..
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 유형 DFS/ BFS 문제 풀이 해당 문제는 상대 팀 진영에 도착하기 위해 지나가야 하는 칸의 최소 개수 즉, 최단 거리를 구하는 문제이다. 최단 거리를 구할 때는 DFS 보다 BFS가 유리하다. DFS는 도착점으로 가기 위한 모든 경로를 탐색해야 하지만 BFS는 타겟에 도착한 순간 종료할 수 있기 때문이다. 큐에는 출발점과 칸의 최소 개수를 넣는다. 큐에서 요소를 하나씩 꺼내고 현재 지점이 상대 팀 진영인 매트릭스의 가장 오른쪽 아래라면 칸의 개수를 리턴한다. 그렇지 않으면 현재 지점의 아래..
문제 링크 Minimum Path Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 유형 다이나믹 프로그래밍 (Dynamic Programming) 문제 풀이 해당 문제는 n x m 매트릭스를 나타내는 2차원 배열이 주어지고, (0,0)에서 (n, m)으로 가는 경로의 최소 합을 구하는 문제이다. 경로 이동은 현재 원소에서 오른쪽이나 아래로만 할 수 있다. 그러므로 각 원소의 이전 경로의 원소는 왼쪽에 있거나 위에 있다. 이는 왼쪽 원소까지의 최소 ..
문제 링크 Min Cost Climbing Stairs - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 유형 다이나믹 프로그래밍(Dynamic Programming) 문제 풀이 해당 문제는 각 계단을 올랐을 때의 비용을 나타내는 숫자 배열이 주어지고, 계단을 다 올랐을 때의 최소 비용을 구하는 문제이다. 계단은 1칸 또는 2칸을 오를 수 있다. 생각해보면 출발 지점의 비용은 없으므로 Index 0과 Index 1 계단까지 올라가는 최소 비용은 0이다. 그..
문제 링크 Top K Frequent Words - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Top K Frequent Elements - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 유형 해쉬 맵, 정렬 ..
문제 링크 First Unique Character in a String - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 유형 해쉬 맵(Hash Map) 문제 풀이 이 문제는 문자열이 주어지고, 문자열에서 처음으로 중복되지 않는 문자의 인덱스를 반환하는 문제이다. 해당 문제는 해쉬 맵을 사용하면 쉽게 해결할 수 있다. 먼저, 각 문자를 확인하면서 키를 각 문자를 저장하고, 값에 중복된 횟수를 저장하는 해쉬 맵을 만든다. 다시 각 문자를 확인하면서 해당 문..
