2021. 12. 2. 17:34γETC/Algorithm
λ¬Έμ μ€λͺ
κ°μμ λ§μ μΉ΄μΉ΄μ€νλ μ¦λ λ¨μ²΄λ‘ μνμ λ λ¬λ€. μ¦κ±°μ΄ μκ°μ 보λ΄κ³ λ§μ§λ§μ λ¨μ²΄μ¬μ§μ μ°κΈ° μν΄ μΉ΄λ©λΌ μμ μΌλ ¬λ‘ λλν μ°λ€. κ·Έλ°λ° κ°μκ° μνλ λ°°μΉκ° λͺ¨λ λ¬λΌ μ΄λ€ μμλ‘ μ€μ§ μ νλλ° μκ°μ΄ μ€λ κ±Έλ Έλ€. λ€μ€λ νλ‘λμ λλν μκΈ°λ₯Ό μνκ³ , νλΈκ° λΏμ λΆμ λ§μ μ μ΄ μλ λΌμ΄μΈμ νλΈμκ²μ μ μ΄λ μΈ μΉΈ μ΄μ λ¨μ΄μ Έμ μκΈ°λ₯Ό μνλ€. μ¬μ§μ μ°κ³ λμ λμμ€λ κΈΈμ, 무μ§λ λͺ¨λκ° μνλ 쑰건μ λ§μ‘±νλ©΄μλ λ€λ₯΄κ² μλ λ°©λ²μ΄ μμ§ μμμκΉ μκ°ν΄λ³΄κ² λμλ€. κ° νλ μ¦κ° μνλ 쑰건μ μ λ ₯μΌλ‘ λ°μμ λ λͺ¨λ 쑰건μ λ§μ‘±ν μ μλλ‘ μλ κ²½μ°μ μλ₯Ό κ³μ°νλ νλ‘κ·Έλ¨μ μμ±ν΄λ³΄μ.
μ λ ₯ νμ
μ λ ₯μ 쑰건μ κ°μλ₯Ό λνλ΄λ μ μ nκ³Ό nκ°μ μμλ‘ κ΅¬μ±λ λ¬Έμμ΄ λ°°μ΄ dataλ‘ μ£Όμ΄μ§λ€. dataμ μμλ κ° νλ μ¦κ° μνλ μ‘°κ±΄μ΄ N~F=0κ³Ό κ°μ ννμ λ¬Έμμ΄λ‘ ꡬμ±λμ΄ μλ€. μ ν쑰건μ μλμ κ°λ€.
- 1 <= n <= 100
- dataμ μμλ λ€μ― κΈμλ‘ κ΅¬μ±λ λ¬Έμμ΄μ΄λ€. κ° μμμ 쑰건μ λ€μκ³Ό κ°λ€.
- 첫 λ²μ§Έ κΈμμ μΈ λ²μ§Έ κΈμλ λ€μ 8κ° μ€ νλμ΄λ€. {A, C, F, J, M, N, R, T} κ°κ° μ΄νΌμΉ, μ½, νλ‘λ, μ μ΄μ§, 무μ§, λ€μ€, λΌμ΄μΈ, νλΈλ₯Ό μλ―Ένλ€. 첫 λ²μ§Έ κΈμλ 쑰건μ μ μν νλ μ¦, μΈ λ²μ§Έ κΈμλ μλλ°©μ΄λ€. 첫 λ²μ§Έ κΈμμ μΈ λ²μ§Έ κΈμλ νμ λ€λ₯΄λ€.
- λ λ²μ§Έ κΈμλ νμ ~μ΄λ€.
- λ€ λ²μ§Έ κΈμλ λ€μ 3κ° μ€ νλμ΄λ€. {=, <, >} κ°κ° κ°μ, λ―Έλ§, μ΄κ³Όλ₯Ό μλ―Ένλ€.
- λ€μ― λ²μ§Έ κΈμλ 0 μ΄μ 6 μ΄νμ μ μμ λ¬Έμνμ΄λ©°, 쑰건μ μ μλλ κ°κ²©μ μλ―Ένλ€. μ΄λ κ°κ²©μ λ νλ μ¦ μ¬μ΄μ μλ λ€λ₯Έ νλ μ¦μ μμ΄λ€.
μΆλ ₯ νμ
λͺ¨λ 쑰건μ λ§μ‘±νλ κ²½μ°μ μλ₯Ό 리ν΄νλ€.
μμ μ μΆλ ₯
n | data | answer |
2 | ["N~F=0", "R~T>2"] | 3648 |
2 | ["M~C<2", "C~M>1"] | 0 |
μμ μ λν μ€λͺ
첫 λ²μ§Έ μμ λ λ¬Έμ μ μ€λͺ λ λ°μ κ°μ΄, λ€μ€λ νλ‘λμμ κ°κ²©μ΄ 0μ΄κΈ°λ₯Ό μνκ³ λΌμ΄μΈμ νλΈμμ κ°κ²©μ΄ 2λ³΄λ€ ν¬κΈ°λ₯Ό μνλ μν©μ΄λ€.
λ λ²μ§Έ μμ λ 무μ§κ° μ½κ³Όμ κ°κ²©μ΄ 2λ³΄λ€ μκΈ°λ₯Ό μνκ³ , λ°λλ‘ μ½μ 무μ§μμ κ°κ²©μ΄ 1λ³΄λ€ ν¬κΈ°λ₯Ό μνλ μν©μ΄λ€. μ΄λ λμμ λ§μ‘±ν μ μλ 쑰건μ΄λ―λ‘ κ²½μ°μ μλ 0μ΄λ€.
λ¬Έμ ν΄κ²°
[C++ ] next_permutation
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool check(char ine, int dis, int cond) {
if (ine == '=') {
return dis == cond;
} else if (ine == '>') {
return dis > cond;
} else {
return dis < cond;
}
}
int solution(int n, vector<string> data) {
int answer = 0;
string friends = "ACFJMNRT";
do {
for (string d: data) {
char f1 = d[0], f2 = d[2];
n = d[4] - '0';
int dist = friends.find(f1) - friends.find(f2);
if (!check(d[3], abs(dist)-1, n)) goto next;
}
answer++;
next: {}
} while (next_permutation(friends.begin(), friends.end()));
return answer;
}
int main() {
int result = solution(2, {"N~F=0", "R~T>2"});
cout << "result : " << result << endl;
return 0;
}
next_permutation μ μ¬μ©ν΄λ³Ό μ μμλ€.
ν΅κ³Ό (406.76ms, 4.26MB)
[C++ ] DFS - Permutation
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#define FRIEND 8
using namespace std;
bool visited[FRIEND];
vector<char> selected;
string friends;
int answer;
bool check(char ine, int dis, int cond) {
if (ine == '=') {
return dis == cond;
} else if (ine == '>') {
return dis > cond;
} else {
return dis < cond;
}
}
bool isValid(vector<string> data, string friends) {
for (string d: data) {
char f1 = d[0], f2 = d[2];
int n = d[4]-'0';
int dist = friends.find(f1) - friends.find(f2);
if (!check(d[3], abs(dist)-1, n)) return false;
}
return true;
}
void dfs(vector<string> data, int cnt) {
if (cnt == FRIEND) {
string sel = "";
for (char s: selected) sel += s;
if (isValid(data, sel)) answer++;
return;
}
for (int i=0; i < FRIEND; i++) {
if (visited[i]) continue;
visited[i]=true;
selected.push_back(friends[i]);
dfs(data, cnt+1);
selected.pop_back();
visited[i]=false;
}
}
int solution(int n, vector<string> data) {
answer = 0;
friends = "ACFJMNRT";
dfs(data, 0);
return answer;
}
DFSλ‘ μμ΄μ μ‘°ννλ©° 체ν¬ν μλ μλ€.
κ·Όλ° μ±λ₯μ next_permutationμ΄ λμ¬λ€
ν΅κ³Ό (9266.66ms, 4.32MB)
'ETC > Algorithm' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
programmers, λ¨μμΉ΄λ©λΌ (0) | 2021.12.03 |
---|---|
Programmers, μ¬ μ°κ²°νκΈ° (2) | 2021.12.02 |
Programmers, μ§ν νΈμ§ (0) | 2021.11.30 |
Programmers, κΈ°μ§κ΅ μ€μΉ (0) | 2021.11.29 |
Programmers, λ°°λ¬ (0) | 2021.11.29 |
Backend Software Engineer
Gyeongsun Park