24년 새해가 밝은 뒤 쓰는 첫 글이다.
이번 문제는 백준의 실버 2 문제 다각형 그리기 문제이다.
문제를 차근차근 한 번 읽어보자.
최대 50 길이의 표본 다각형 수열이 주어진다.
이후로 최대 100개의 다각형 수열이 주어지게 되며,
각 수열이 표본 수열과 동일한 모양인지 판단해야 하는 문제이다.
어떻게 문제를 해결해야 할까?
동형 조건
가장 먼저 드는 생각은, 동일한 모양일 조건이 무엇인지이다.
아래와 같은 두 조건하에 두 수열은 같은 모양일 것이다.
- 수열의 순서가 동일하다
상 하,좌 우를 반전시켜도 동일한 순서면 된다.
이제 문제는 수열의 순서를 어떻게 구현할 것인가이다.
순서 검사
가장 먼저 생각나는 것은 단순히 for문을 통해 검사하는 것이다.
최대 100개, 최대 길이 50이므로 O(N^2)의 검사를 한다고 생각하면,
한 수열을 검사하는 데에 최대 2500의 시간이 걸리고
100개의 수열을 모두 검사하는 데에는 250000의 시간 밖에 걸리지 않는다.
따라서 시간 복잡도는 문제 없을 것이다.
그렇다면 반대 방향으로 도는 경우는?
수열의 각 원소를 반대 방향으로 우선 뒤집어 주어야 한다.
또한, 중요한 점은 표본 수열을 뒤에서 부터 훑어야 한다는 점이다.
각 함수는 아래와 같이 구현하였다.
// 순방향 수열 검사
bool check_sequence(int target) {
for (int i = 0; i < len; i++) {
int iter = 0;
while (true) {
if (specimen[iter] == seq[target][(iter + i) % len])
iter++;
else
break;
if (iter >= len)
return true;
}
}
return false;
}// 역방향 수열 검사
bool check_reversed_sequence(int target) {
int rev_seq[50];
reverse_sequence(target, rev_seq);
for (int i = 0; i < len; i++) {
int iter = 0;
int reversed_iter = len - 1;
while (true) {
if (specimen[reversed_iter] == rev_seq[(iter + i) % len]) {
iter++;
reversed_iter--;
}
else
break;
if (iter >= len || reversed_iter <= 0)
return true;
}
}
return false;
}요새는 구현 문제 위주로 풀며, 구현하는 힘을 기르고 있다.
코딩 테스트에서 점점 구현력의 중요성이 대두되고 있다고 생각한다.
기본 구현부터 차근차근 연습해보도록 하자.