문제 개요
자석을 표현하는 숫자에서 1은 양극(N극)을, 0은 음극(S극)을 의미합니다.
각 자석은 두 개의 극을 가지며, 10 또는 01의 형태로 표현됩니다. 서로 이끌어당기는(인력이 작용하는) 자석들은 하나의 그룹을 이룰 수 있으며, 서로 마주 보는 면의 극이 다른 자석들이 같은 그룹에 속하게 됩니다.
여기서 N개의 자석이 주어졌을 때, 이 자석들로 형성할 수 있는 그룹의 개수를 구해야 합니다.
핵심 규칙은 간단합니다. 서로 다른 자석이 나란히 배치될 때마다 새로운 그룹이 형성되며, 이 경우 그룹 개수를 하나씩 증가시키면 됩니다.
예시
입력
magnets = ["10", "01", "01", "01", "10", "01"]
출력
4
위 배열에서는 인접한 자석끼리 서로 다른 극이 마주쳐 이끌어당기는 경우가 총 4번 발생하므로, 형성되는 그룹의 개수는 4개입니다.
알고리즘
- 자석 정보로 배열을 초기화합니다.
- 그룹 개수(count)를 1로 초기화합니다. 첫 번째 자석이 이미 하나의 그룹을 형성하기 때문입니다.
- 인덱스 1부터 배열의 끝까지 반복하는 루프를 작성합니다.
- 현재 자석이 이전 자석과 다르다면, 새로운 그룹이 형성된 것이므로 count를 증가시킵니다.
- 반복이 끝나면 count를 반환합니다.
C++ 구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
int getMagnetGroupsCount(string magnets[], int n) {
int count = 1;
for (int i = 1; i < n; i++) {
if (magnets[i] != magnets[i - 1]) {
count++;
}
}
return count;
}
int main() {
string magnets[] = { "10", "01", "01", "01", "10", "01" };
int n = 6;
cout << getMagnetGroupsCount(magnets, n) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
4
정리
이 문제는 인접한 원소 간의 비교만으로 해결할 수 있는 간단한 탐색 문제입니다. 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적이며, 문자열 배열 대신 각 자석의 상태를 정수나 불리언 값으로 저장하면 더욱 최적화할 수 있습니다.