문제 링크 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로 먼저 전처리해줬다. 시소 짝꿍의 수는 각 몸무게 단위로 계산을 해줬는데 동일한 몸무게의 사...

문제 링크 1. 아이디어 문자열 s와 t에 대해 t가 s의 애너그램이면 true, 아니면 false를 반환하는 문제다. s와 t 모두 알파벳 소문자로만 이루어져 있으므로 카운팅 배열을 활용해 s에 등장한 알파벳을 카운팅 배열에서 더해주고, t에 등장한 알파벳을 카운팅 배열에서 빼주어서 최종적으로 카운팅 배열이 모두 0으로 이루어져 있으면 애너그...

문제 링크 1. 아이디어 정수 배열 nums와 정수 target이 주어졌을 때, nums에서 두 수의 합이 target이 되는 쌍이 딱 하나 존재하며 이때 두 수의 인덱스를 찾는 문제다. 간단한 방법으로는 2중 반복문을 통한 브루트 포스로 해결할 수 있다. 바깥쪽 반복문이 두 수 중 앞쪽 인덱스를, 안쪽 반복문이 뒤쪽 인덱스를 찾아내는 방식으...

문제 링크 1. 아이디어 의상은 종류와 이름 두 가지로 구분되며 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있다. 코니가 최소 한 개의 의상은 입어야 할 경우 코니가 입을 수 있는 서로 다른 옷의 조합의 수를 구해야 한다. 해당 문제는 경우의 수를 구하면 해결할 수 있는데 같은 이름을 가진 의상이 존재하지 않으므로 모든 의상에 대해 각...