문제 링크 1. 아이디어 소괄호, 중괄호, 대괄호들로 이루어진 문자열 s에 대해 유효한 문자열인지 판단하는 문제로 괄호 유효성 검사라는 면에서 스택을 활용하면 해결할 수 있다. 열린 괄호는 스택에 넣고 닫힌 괄호는 스택의 top과 같으면 top을 제거 후 반복, top과 다르거나 스택이 비어있으면 유효하지 않은 괄호열이다. 2. 복잡도 ...

문제 링크 1. 아이디어 정수 배열 nums에 대해 하나의 원소를 제외한 나머지 원소가 모두 두 번씩 등장할 때, 한 번만 등장한 원소를 구하는 문제다. 비트 XOR 연산을 활용하면 간단하게 해결할 수 있는데 같은 수에 대한 비트 XOR 연산은 0이 된다는 점에서 모든 원소를 전부 비트 XOR 연산을 하면 한 번만 등장했던 원소를 구할 수 있...

문제 링크 1. 아이디어 여러 선분의 시작점과 끝점이 담긴 lines가 주어질 때, 두 개 이상의 선분이 겹치는 구간의 길이의 합을 구하는 문제로 좌표 범위가 -100 ~ 100으로 좁다는 점을 이용해 각 단위 구간마다 겹치는 선분의 개수를 센 다음 2개 이상 겹친 구간의 개수를 세면 그게 곧 정답이 된다. 좌표에 음수가 포함돼 배열 인덱스...

문제 링크 1. 아이디어 네 점의 좌표가 담긴 dots를 두 점씩 묶어 만든 두 직선 중 평행한 경우가 하나라도 있으면 1을, 없으면 0을 반환하는 문제로 네 점을 두 쌍으로 나누는 경우의 수 3가지를 전부 확인하면서 각 경우 두 직선이 평행한지 판별하면 된다. 평행 여부는 기울기를 구해 비교하면 되지만 실수 나눗셈이라 정밀도 오차가 생길 ...

문제 링크 1. 아이디어 삼각형의 두 변이 주어질 때, 나머지 한 변이 될 수 있는 정수의 개수를 구하는 문제로 나머지 한 변이 가장 긴 변이 되는 경우와 그렇지 않은 경우 두 가지로 케이스 분류를 해보면 된다. 주어진 두 변을 $a$, $b$($a \le b$) 나머지 한 변을 $c$라고 할 때, $c$가 가장 긴 변이 되는 경우는 $c$...

문제 링크 1. 아이디어 소문자, 대문자, 자연수로 구성된 문자열 my_string에 대해 자연수들의 합을 구하는 문제로 my_string에서 자연수가 아닌 부분을 전부 공백 문자로 변환 후 숫자 부분만 취해서 합을 구하면 된다. 2. 복잡도 접근 시간 공간 ...

문제 링크 1. 아이디어 x를 1 줄이고 y를 1 늘리는 연산을 몇 번이든 반복해 XOR을 최대화하고, 그중 연산 횟수가 최소인 경우를 찾아야 한다. 한쪽에서 줄어든 만큼 다른 쪽에 그대로 더해지므로 두 값의 합은 연산 전후로 항상 같다(sum = x + y). 합이 고정된 두 수의 XOR은 두 수가 겹치는 비트가 없을 때 최대가 되고 그 값...

문제 링크 1. 아이디어 각 달마다 직원 수와 프로젝트 수가 함께 1씩 늘어나는 k개월 동안 Monocarp가 직접 처리하는 프로젝트 수의 총합을 구해야 한다. i번째 달엔 직원이 x + i명, 프로젝트가 y + i개이므로 그 달 Monocarp가 처리하는 양은 y + i를 x + i로 나눈 나머지다. d = y - x는 매달 그대로 유지되는...

문제 링크 1. 아이디어 n개의 문제들이 주어지며 각 문제는 쉬우면 0, 어려우면 1로 표현된다. 이때 두 문제의 위치를 변경할 수 있을 때 첫 번째 문제와 마지막 문제에 쉬운 문제를 두기 위한 최소 연산 횟수를 구해야 한다. 첫 번째 문제와 마지막 문제가 쉬운 문제인지 어려운 문제인지를 구하고 그 사이 문제들 중 쉬운 문제의 수를 구해 조건...

문제 링크 1. 아이디어 myString의 모든 문자를 대문자로 변경하면 되는 간단한 문제다. 2. 복잡도 접근 시간 공간 풀이 $O(N)$ $O(N)$ ($N$ = myString의 길이. C++는 인자를 제...