[BaekJoon 1436][⚪5] 영화감독 숌
❓ 문제
🎯 난이도
Silver ⚪5
🧠 풀이
1. 내 풀이 (브루트 포스 + 문자열)
- 알고리즘
Brute Force,string
- 설명
string의 find 함수를 사용해서 푸는 방식이다.
string의 함수에는 특정 문자열이 포함되어 있는지를 검사하는 find라는 함수가 있다. 문자열을 찾은 경우에는 찾은 문자열의 첫 번째 인덱스값을 int형으로 반환하고, 그렇지 않은 경우에는 string::npos라는 일종의 쓰레기값을 반환한다.
이 함수를 사용하면 매우 쉽게 특정 문자열의 '포함 여부'를 확인할 수 있다.
약 N개의 숫자를 검사하고 find를 할 때 각각의 자릿수만큼의 시간이 걸리므로 시간 복잡도는 O(N log N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
long long llCurr{ 666 };
int iIndex{};
while(true)
{
string strCurr{ to_string(llCurr) };
// string의 find로 찾았을 때 string::npos (쓰레기 값) 나오면 해당 단어가 존재하지 않음
if(to_string(llCurr).find("666") != string::npos)
{
++iIndex;
if(iIndex == iN)
{
break;
}
}
++llCurr;
}
cout << llCurr;
return 0;
}
2. 추가 풀이 (브루트 포스 + 정수 계산)
- 알고리즘
Brute Force
- 설명
문자열로 치환하는 대신에, 정수 계산을 사용하는 풀이이다.
흔하게 쓰이는 각각의 자릿수 판별 식을 사용해서, 문자열로 치환하는 대신에 정수 그대로의 상태에서 산술 계산을 하는 방식이다.
string를 쓰게 되면 정수를 문자열로 치환하고, find로 문자열의 길이만큼 검사를 하는 오버헤드가 발생하는데, 이 방법은 그러한 '오버헤드'가 없이 간단한 계산만으로 끝나므로 이 문제에서는 훨씬 최적화된 방식이라고 볼 수 있다.
N개의 숫자의 자릿수 검사를 하므로 전체적인 시간 복잡도는 문자열 방식과 동일한 O(N log N)이다.
- 코드
내 풀이 코드
#include <iostream>
using namespace std;
bool Is666(long long llNum);
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
long long llCurr{ 666 };
int iIndex{};
while(true)
{
if(Is666(llCurr))
{
++iIndex;
if(iIndex == iN)
{
break;
}
}
++llCurr;
}
cout << llCurr;
return 0;
}
// 666이 있는지를 정수 계산으로 알아내는 함수
bool Is666(long long llNum)
{
int iConse{};
while(llNum)
{
if(llNum % 10 == 6)
{
++iConse;
}
else
{
iConse = 0;
}
// 3번 연속으로 6 나오면 true 반환
if(iConse == 3)
{
return true;
}
llNum /= 10;
}
return false;
}
💭 후기
개인적으로는 string의 find를 사용한 방식이 더 간단하고, 직관성도 좋다고 생각한다. 하지만 두 방식의 실제 실행 시간은 생각보다 차이가 많이 난다.
- 첫 번째 풀이 :
96ms - 두 번째 풀이 :
32ms
이는 정수를 string 치환하는 과정에서의 변환, 객체 생성, 힙 할당, find 함수의 문자열 길이만큼을 모두 계산하는 동작 방식 등에서 나오는 오버헤드가 만만치 않기 때문이다.
그에 반해 정수 계산은 정말 간단한 산술 연산만 있기 때문에, 두 방식의 시간 복잡도가 같더라도 실제 실행 시간은 차이가 많이 날 수 있다는 것을 알 수 있는 케이스이다.
Comments