순열, 브루트포스
https://www.acmicpc.net/problem/2503
숫자 야구로 주어진 질문과 답에 맞는 경우의 수를 찾는 문제이다.
숫자는 1~9의 서로 다른 숫자로 이루어져 있으므로 순열을 통해 으로 구하려고 했지만
풀고 보니 i = 123 부터 987 까지 1씩 증가하면서 체크하면 굳이 순열을 만들 필요가 없었다....
그래도 의 순열을 구하는 방법은 익혔으니까...ㅎ
순열 구하기
do
{
for (int i = 0; i < 3; i++)
{
cout << arr[i];
}
cout << "\n";
reverse(arr + 3, arr + 9);
} while (next_permutation(arr, arr + 9));중간에 reverse 의 이유는
순열 함수 next_permuatation 에 의해 을 구한다면
1 2 3 4 5 6 -> 1 2 3 4 6 5 -> 1 2 3 5 4 6 ...
이런 식으로 진행이 될 텐데 reverse 를 빼고 진행할 경우 r = 3 이므로
123 이 계속 중복되어 나오게 될 것이다.
따라서 1 2 3 4 5 6 로 1 2 3 을 얻은 후에 r 에 해당하는 인덱스 3 뒤에 있는 값을
일부러 가장 마지막 값인 1 2 3 6 5 4 로 만들어 next_permutation 이 바로 다음 값인
1 2 4 3 5 6 으로 이동할 수 있도록 한다.
조건에 맞게 소거, 브루트 포스
- 백준 14369번 : 전화번호 수수께끼
https://www.acmicpc.net/problem/14369
또 다른 브루트포스 문제로 "ONE", "TWO", "FIVE" 로 이루어진 문자열들이
무작위로 섞인 문자열이 있을 때 어떤 숫자가 섞여있는지 확인하는 문제이다.
처음 구현은 막연하게 "ONE" 과 "TWO" 에 대해 한문자 한문자씩 찾아서
모두 찾은 경우 문자열에서 삭제하면서 찾아가는 방식을 사용하고자 했지만
너무 코드가 복잡해지고 답이 틀렸다고 나와 반례를 찾는 과정이 너무 어려워서
검색! 을 참고해 문제 접근 방식을 확인하였다.
문제의 접근 방식은 다음과 같다.
"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"
위의 문자열은 각각의 고유로 구분할 수 있는 문자가 있다.
고유 문자 선정은 문자열이 서로 중복되지 않게 찾는 것이 중요하며 다음과 같이 구분할 수 있다.
pair<char, int> uni[10] = {
{'Z', 0},
{'X', 6},
{'S', 7},
{'V', 5},
{'F', 4},
{'R', 3},
{'G', 8},
{'W', 2},
{'O', 1},
{'N', 9}};위의 순서대로 탐색하면 모든 문자열을 각각의 고유 문자로 구분해서 찾아낼 수 있다.
이렇게 찾아낸 문자에 대한 전체 문자열을 주어진 문자열 S 에서 삭제하고 탐색을 이어가며
찾은 후에 탐색은 다시 처음부터 진행된다. {("ONEONEFOUR") 같은 문자열도 존재하므로}
전체 코드는 다음과 같이 된다.
#include <bits/stdc++.h>
using namespace std;
string numToString(int n)
{
string num[10] = {"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"};
return num[n];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
pair<char, int> uni[10] = {
{'Z', 0},
{'X', 6},
{'S', 7},
{'V', 5},
{'F', 4},
{'R', 3},
{'G', 8},
{'W', 2},
{'O', 1},
{'N', 9}};
int case_cnt = 1;
cin >> N;
while (N--)
{
string S;
string res = "";
cin >> S;
for (int i = 0; i < 10; i++)
{
if (S.find(uni[i].first) != string::npos)
{
res += to_string(uni[i].second);
string erase_str = numToString(uni[i].second);
for (char c : erase_str)
{
S.erase(find(S.begin(), S.end(), c));
}
i = -1;
}
}
sort(res.begin(), res.end());
cout << "Case #" << case_cnt << ": " << res << "\n";
case_cnt++;
}
return 0;
}막무가내로 풀다가 복잡하거나 너무 어려운 방식으로 접근된다면
이렇게 특정 지을 문자나 패턴이 있는지 확인해보자!!!
사용할 STL 과 메서드도 고려 사항!
- 백준 7696번 : 반복하지 않는 수
https://www.acmicpc.net/problem/7696
또 다른 브루트포스 문제로 로직 자체는
각 자릿수를 확인해서 중복되는 지를 확인해보는 아이디어로
금방 풀이 방법이 떠올라 구현해봤지만 계속되는 시간 초과 때문에 애를 많이 먹었다.....
도움을 받아 수정된 부분은 다음과 같다!!
- 테스트 케이스가 실행될 때마다 새로 구하지 말고 테스트 케이스 입력 전 미리 구해서 저장
- STL 과 메서드의 사용을 줄여 호출로 인한 지연 막기
얘기했듯이 각 자릿수를 비교해 중복을 체크하는 것을 바로 떠올렸기 때문에
map 에 0 ~ 9 까지의 숫자를 넣어 만약 숫자에 대한 Value 가 1 보다 클 경우
중복되었다고 판단하도록 하였다.
그러나 이를 테스트 케이스가 입력될 때마다 계속 구하게 되면
중복되는 경우가 계속 존재하므로 이를 줄이기 위해
미리 반복된 숫자가 존재하지 않는 경우에 대해 미리 구해서 배열에 저장해
테스트 케이스 입력에는 해당 인덱스에 맞는 값만 출력해주는 것을 수정하였다!
하지만 이렇게 함수로 따로 빼서 테스트 케이스 입력 전에 미리 구했음에도
시간 초과가 발생했다....
그래서 같이 푼 형의 코드와 비교해보니 다른 점은 반복 숫자에서
사용하기 위해 선택한 자료구조 에 있었다.
아까 얘기했듯이 나는 반복 체크에 map 을 사용하였고 형의 코드에서는 arr 를 사용하였다.
map 을 불러와 사용하며 map 에 키와 value 로 접근하는 것이 배열의 인덱스 접근보다
부하가 더 있어서 그로 인한 지연으로 시간 초과가 발생하는 것이었다.
-
map 사용 (시간 초과)
https://www.acmicpc.net/source/68522165 -
arr 사용 (통과)
https://www.acmicpc.net/source/68522263
같이 푼 친구는 파이썬 코드였는데 배열에 인덱스 접근이 아닌 append 사용으로 시간초과가 떴다...
브루트포스와 같이 큰 시간 복잡도를 가지거나 주어진 시간 제한에 근접한 풀이 과정을 가진 경우
코드에 사용하는 자료구조와 메서드를 주의해서 사용하자!
멋진 청년.