문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 유형 스택 문제 풀이 처음에는 인덱스를 사용한 순회 방식을 생각해 현재 인덱스를 다음 인덱스와 차례대로 비교하면서 큰 수를 만나면 다음 인덱스를 비교하는 방식으로 구현했다. 그 결과 테스트 케이스 20~22가 시간 초과가 발생했다. 인덱스를 사용한 순회 방식으로는 해결 안되는 테스트 케이스 인 것 같아 다른 방법을 찾아보던 중 스택을 사용하라는 힌트를 발견했다. 스택을 사용할 때는 다음의 사항을 고려했다. 가장 마지막 배열 요소부터 순회하며 스택에 추가한다. 그럼 스택에는 현재 요소 기준 뒤에..
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 유형 Map, 정렬 문제 풀이 처음에 보자마자 떠오른 방식은 1000개짜리 배열을 만들어서 매개변수 array의 각 요소에 해당하는 인덱스 자리에 카운팅을 해주는 것이었다. 하지만 이는 테스트 케이스에 따라 1000개짜리 배열을 생성하면서 사용하지 않는 메모리가 많을 수도 있겠다는 생각이 들었다. 다른 방법을 떠올리던 중 이전에 풀었던 top K Frequent element 가 생각났고, 해당 풀이를 참고하여 풀었다. 1. Map 객체를 만들고, array를 순회하며 Map에 각 숫자가 나온..
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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는 타겟에 도착한 순간 종료할 수 있기 때문이다. 큐에는 출발점과 칸의 최소 개수를 넣는다. 큐에서 요소를 하나씩 꺼내고 현재 지점이 상대 팀 진영인 매트릭스의 가장 오른쪽 아래라면 칸의 개수를 리턴한다. 그렇지 않으면 현재 지점의 아래..
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 유형 DFS/BFS 문제 풀이 이번 문제는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 주어지고 배열 내의 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 리턴하는 문제이다. 해당 문제는 recursive DFS를 구현하여 해결할 수 있다. 0번 인덱스부터 dfs 함수를 호출하여 마지막 인덱스까지 모든 숫자를 더한 값을 계산하고 계산한 결과가 타겟 넘버인지를 확인한다. 마지막 인덱스까지 확인 후 재귀를 빠져나와 숫자가 음수인 경우를 탐색한다. 코드 function so..
문제 링크 Keys and Rooms - 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 문제 유형 그래프, DFS/ BFS 문제 풀이 이번 문제는 0 ~ (n - 1)번 방 n개와 각 방에는 번호가 적힌 키가 있다. 키에 적힌 번호는 해당 키로 열 수 있는 방의 번호이다. 0번 방에서부터 모든 방을 열 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다. 해당 문제는 그래프 문제로 생각하여 DFS나 BFS를 이용해 그래프를 순회하여 해결 할 수 ..
문제 링크 Diameter of Binary Tree - 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 문제 유형 트리, 백트래킹 문제 풀이 이번 문제는 트리의 지름을 구하는 문제이다. 여기서 지름(diameter)는 트리의 어떤 두 노드 사이의 가장 긴 경로의 길이를 말한다. 해당 문제는 백트래킹을 적용하여 각 노드를 post-order 순회한다. 이를 통해 각 노드의 left depth와 right depth를 구한다. 저장된 지름보다 left depth와 ..
