문제 링크 1. 아이디어 세균은 1시간에 두 배만큼 증식하므로 처음 세균의 마리수 n과 경과한 시간 t에 대해 t시간 후 세균의 수는 $n \times 2^t$마리다. 2. 복잡도 접근 시간 공간 풀이 $O(1)$ $O(1)$ ...

문제 링크 1. 아이디어 정수 n에 대해 n이 제곱수인지 여부를 판단하는 문제로 1부터 제곱수를 구해 n과 동일한지 비교하는 방식으로 해결해도 되고, 제곱근을 구하는 내장 함수를 활용해서 해결해도 된다. 2. 복잡도 접근 시간 공간 풀이 ...

문제 링크 1. 아이디어 문자열 str1안에 문자열 str2가 존재하는지 판단하면 되는 문제다. 언어별 내장 함수를 활용하면 간단하게 해결할 수 있다. 2. 복잡도 접근 시간 공간 풀이 $O(N \times M)$ $O(1)$ ...

문제 링크 1. 아이디어 정수 배열 nums에 대해 두 번 이상 등장한 원소가 있으면 true를 아니면 false를 반환하는 문제다. 각 정수의 중복 여부를 판단한다는 점에서 해시셋을 활용하면 간단하게 해결할 수 있다. 2. 복잡도 접근 시간 공간 ...

문제 링크 1. 아이디어 약어가 만들어질 수 있는지는 그 약어의 모든 글자가 초기 단어들의 첫 글자 집합 안에 있는지로 결정되는데, 새로 만든 약어를 집합에 다시 넣어도 이 판정이 달라지지 않는다는 점이 핵심이다. 약어가 이후에 다른 약어의 재료로 쓰일 때 기여하는 건 자기 첫 글자 하나뿐이고, 그 첫 글자는 약어를 이루는 수열 맨 앞 단어의...

문제 링크 1. 아이디어 각 단어를 정점으로 두고 한 글자만 다른 두 단어를 간선으로 잇는 그래프를 생각하면, begin에서 target까지의 최소 변환 횟수는 이 그래프의 최단 경로 길이다. 간선 비용이 모두 1이므로 최단 거리 BFS로 구하면 된다. 어떤 단어의 인접 단어는 각 자리를 a부터 z까지 바꿔 본 후보 중 words에 실제로 ...

문제 링크 1. 아이디어 인접한 칸으로의 이동 비용이 모두 1이므로 최단 거리는 BFS로 구하면 된다. 시작 칸 $(0, 0)$에서 큐를 초기화하고, 상하좌우 네 방향 중 맵 안이면서 벽이 아니고 아직 방문하지 않은 칸을 큐에 넣으며 거리를 하나씩 늘려 나갔다. 거리는 dist 배열을 활용했으며 시작 칸부터 거리 1로 세므로 0으로 초기화한...

문제 링크 1. 아이디어 첫 원소를 1번으로 셀 때 홀수 번째 원소는 0-indexed 인덱스로는 짝수 자리(0, 2, 4, …)에, 짝수 번째 원소는 홀수 자리에 놓인다. 짝수 자리와 홀수 자리에 위치한 원소들의 합을 각각 구해서 더 큰 값을 반환하면 된다. 2. 복잡도 접근 시간 공간...

문제 링크 1. 아이디어 앞에서부터 5명씩 묶으므로 각 그룹의 맨 앞 사람은 인덱스 0, 5, 10, …에 위치한다. 시작 인덱스부터 5칸 간격으로 원소를 골라 순서대로 담으면 된다. 마지막 그룹이 5명이 안 되더라도 그 그룹의 맨 앞 사람은 세어야 하므로 그룹의 개수는 $\lceil N / 5 \rceil$이 된다. 2. 복잡도 ...

문제 링크 1. 아이디어 todo_list와 finished를 인덱스를 맞춰 함께 순회하며 finished가 거짓인 항목만 순서대로 결과 배열에 담으면 된다. 2. 복잡도 접근 시간 공간 풀이 $O(N)$ $O(N)$ ...