문제 링크 1. 아이디어 주어진 광물들을 앞에서부터 연속으로 캐야하며 하나의 곡괭이가 5개의 광물까지 캘 수 있다는 점에서 주어진 광물들을 앞에서부터 5개씩 그룹을 묶어주는 것으로 시작했다. 그룹핑 이후에는 백트래킹 또는 그리디를 활용하면 해결할 수 있는데 먼저 백트래킹의 경우 5개씩 묶은 광물 그룹에 대해 앞에서부터 순서대로 곡괭이를 배치해...

문제 링크 1. 아이디어 지도에서 연결된 땅들의 값의 합을 오름차순으로 정렬하는 문제로 bfs 또는 dfs를 활용해서 해결할 수 있다. 주어진 지도를 순회하며 bfs, dfs로 땅을 발견하면 연결된 땅까지 전부 방문 체크하고 값의 합을 구해 저장한 후 순회가 끝났을 때, 땅이 존재하지 않으면 -1을 담은 배열을, 땅이 존재하면 오름차순으로 정렬...

문제 링크 1. 아이디어 이분 탐색을 직접 구현해보는 문제로 이분 탐색 과정에서 mid가 target이 되면 해당 인덱스를, 양 끝 포인터가 교차할 때까지 target을 찾지 못하면 -1을 반환만 해주면 된다. nums가 오름차순으로 정렬된채로 주어지기 때문에 바로 이분 탐색을 구현해줬다. 이분 탐색 과정에서 구간이 절반씩 줄어드므로 $O(\l...

문제 링크 1. 아이디어 주어진 문자열이 팰린드롬인지 판단하는 문제로 이때 알파벳이나 숫자가 아닌 문자는 제거하고 알파벳은 소문자로 치환한 후 팰린드롬이 되는지 판단하는 문제다. 해당 문제는 투 포인터를 활용하면 해결할 수 있는데 주어진 문자열의 양 끝에서부터 서로 교차하는 방향으로 포인터를 진행시키는데 알파벳이나 숫자가 아닌 문자는 건너뛰고 ...

문제 링크 1. 아이디어 x, -x, x, … 와 같이 x의 부호가 뒤바뀌며 n번 반복되는 수열의 합을 구하는 문제로 첫 항부터 두 항씩 묶어보면 두 항의 합이 0이 된다는 점에서 n이 짝수이면 모든 항이 두 항씩 짝이 묶이므로 수열의 합은 0이 되며, n이 홀수이면 가장 마지막 항을 제외한 모든 항이 두 항씩 짝이 묶이고 가장 마지막 항은 x...

문제 링크 1. 아이디어 올바른 괄호 문자열을 판단하는 문제로 올바른 괄호 문자열은 괄호들로 이루어진 문자열이 유효한 괄호 규칙을 이루는 문자열이다. 괄호 문제를 해결하는 대표적인 기법인 스택 자료구조를 활용해서 해결했는데 열린 괄호열이면 스택에 담고 닫힌 괄호열이면 스택의 top에 위치한 괄호와 쌍이 맞는지 판단해서 쌍이 맞으면 해당 괄호를 ...

문제 링크 1. 아이디어 유효한 괄호열인지 판단하는 문제로 스택 자료구조를 활용하는 대표적인 문제이다. 열린 괄호가 등장하면 스택에 담고 닫힌 괄호가 등장하면 스택의 top에 위치한 괄호와 짝이 맞는지 판단해서 짝이 맞으면 top에 위치한 괄호를 제거하는 과정을 반복하면 괄호 규칙에 맞는지 판단할 수 있다. 괄호열을 전부 확인한 이후에는 스택에...

문제 링크 1. 아이디어 정수 삼각형에서 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾는 문제로 삼각형의 높이가 최대 500이어서 DFS를 활용할 경우 시간 초과가 발생하게 된다. 해당 문제는 다이나믹 프로그래밍을 활용하면 해결할 수 있는데 특정 위치까지 오는데 거쳐간 숫자의 합이 가장 큰 경우는 해당 위치로 올...

문제 링크 1. 아이디어 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하는 문제로 k번째 수를 구하는 command가 여러번 등장하기에 원본 배열을 직접 수정하면 안된다. 따라서 주어진 구간을 별도의 임시 배열에 복사한 후 정렬을 수행하고 k번째 수를 구하는 과정을 반복해줬다. 2. 복잡도 ...

문제 링크 1. 아이디어 중심으로부터 2m, 3m, 4m 거리의 지점에 좌석이 하나씩 있는 시소에서 시소 짝꿍의 쌍을 구하는 문제로 해시맵을 활용해서 해결했다. weight 목록에서 동일한 몸무게가 주어질 수 있으므로 몸무게를 key, 수를 value로 먼저 전처리해줬다. 시소 짝꿍의 수는 각 몸무게 단위로 계산을 해줬는데 동일한 몸무게의 사...