https://school.programmers.co.kr/learn/courses/30/lessons/1835?language=cpp
[A, C, F, J, M, N, R, T] 8개의 알파벳을 나열하는 것을 베이스로 한다.
입력으로 있는 data의 모든 조건에 부합하여 나열할 수 있는
경우의 수가 총 몇 가지가 나오는지 구하는 문제
문제 핵심 및 풀이
해당 문제 풀이의 핵심은 조건의 개수 n이 최대 100개까지라는 점.
그리고 8개의 알파벳을 나열할 때 나올 수 있는 모든 경우의 수는
8! = 40320밖에 되지 않는다는 점이다.
그래서 일단 나올 수 있는 경우의 수는 백트래킹을 구하는 것이 적절하다.
그렇게 줄을 다 세우면, 그다음부터 data에 따라 필터링을 해주면 된다.
필터링 방법은 간단하다.
N~F이라면 N과 F가 해당 나열에서는 몇 번째 인덱스에 있는지를 체크하면 된다.
결국 핵심은 백트래킹으로 나올 수 있는 경우의 수를 구한 후,
data 조건에 따라 필터링을 하는 것이다.
data 조건에 따른 필터링을 위해서,
문자열로 들어온 data를 조건으로 바꾸는 것이 필요하다.
다행히도 data 입력은 무조건 다섯 글자로 구성되어 있다.
마찬가지로 첫 번째, 세 번째 인덱스가 알파벳이고,
네 번째 인덱스가 연산자, 그리고 마지막 인덱스는 무조건 숫자다.
그래서 그냥 문자열 추출만 해서
switch case로 연산자에 따라 구분만 해줬다.
실수하기 쉬운 점
예제 케이스도 다 통과하고,
로직도 아무리 봐도 맞는 것 같은데 제출만 하면 틀렸다고 뜬다.
이게 보니까 C++ 제출할 때는 주석으로
"전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해 주세요"
가 있는데 Java로 풀 때는 해당 주석이 없더라.
그래서 이 문제에서는 전역변수로 사용하는 변수들은
Solution 쪽에서 초기화를 진행해줘야 한다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <cmath>
using namespace std;
string str = ""; // 해당 백트래킹일 때, 완성된 일렬 줄
string order = "ACFJMNRT";
int answer = 0; // 정답
bool visited[8]; // 방문 체크 배열
// 해당 줄로 세웠을 때 word의 조건으로 가능한지를 체크
bool isPossible(string word){
int p1 = word[0];
int p2 = word[2];
int op = word[3];
int num = word[4]-'0';
int idx1 = str.find(p1);
int idx2 = str.find(p2);
// 연산자에 따라 식을 다르게 함
switch(op){
case '=':
if(abs(idx1-idx2)-1 == num) return true;
break;
case '>':
if(abs(idx1-idx2)-1 > num) return true;
break;
case '<':
if(abs(idx1-idx2)-1 < num) return true;
break;
}
return false;
}
// 가능한 모든 경우의 수를 구하는 백트래킹
void backTracking(int cnt, vector<string> data){
// 8명 줄을 다 세우면 그때부터 data에 따라 판단 시작
if(cnt >= 8){
for(auto it : data){
if(!isPossible(it)) return;
}
answer++;
return;
}
// 백트래킹
for(int i = 0; i < 8; i++){
if(visited[i]) continue; // 이미 방문했던 곳은 방문하지 않음
visited[i] = true;
str.push_back(order[i]);
backTracking(cnt+1,data);
visited[i] = false;
str.pop_back();
}
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
answer = 0; // 전역변수이므로 초기화 필수
for(int i = 0; i < 8; i++) visited[i] = false; // 전역변수이므로 초기화 필수
str = ""; // 전역변수이므로 초기화 필수
backTracking(0,data);
return answer;
}↑
Java 구현 코드
↓
import java.util.*;
class Solution{
static List<Character> order = Arrays.asList('A', 'C', 'F', 'J', 'M', 'N', 'R', 'T');
static List<Character> list = new ArrayList<>(); // 해당 백트래킹일때의 완성된 줄
static boolean[] visited = new boolean[8]; // 방문 체크 배열
static int answer = 0; // 정답
// 백트래킹함수
public void backTracking(int cnt,String[] data) {
// 8명 줄을 다 세웠다면 그때부터 data에 따라 판단 시작
if (cnt >= 8) {
for(String word : data){
// 조건 하나라도 불일치시 실패로 간주
if(!getList(word)) return;
}
answer++;
return;
}
// 백트래킹
for (int i = 0; i < 8; i++) {
if (visited[i]) continue;
visited[i] = true;
list.add(order.get(i));
backTracking(cnt+1,data);
visited[i] = false;
list.remove(order.get(i));
}
}
// 해당 list로 완성된줄, 조건 word일 때 부합하는가?
public boolean getList(String word){
char p1 = word.charAt(0);
char p2 = word.charAt(2);
char op = word.charAt(3);
int num = word.charAt(4) - '0';
int idx1 = list.indexOf(p1);
int idx2 = list.indexOf(p2);
// 연산자에 따라 스위치문 작성
switch (op){
case '=' :
if(Math.abs(idx1-idx2)-1 == num) return true;
break;
case '>' :
if(Math.abs(idx1-idx2)-1 > num) return true;
break;
case '<' :
if(Math.abs(idx1-idx2)-1 < num) return true;
break;
}
return false;
}
public int solution(int n, String[] data) {
answer = 0; // 전역변수 초기화
list.clear(); // 전역변수 초기화
Arrays.fill(visited,false); // 전역변수 초기화
backTracking(0,data);
return answer;
}
}↑
시행착오
백트래킹을 통해 모든 경우의 수를 구하는 것까지는 똑같이 했다.
하지만 나는 조건을 따로 빼서 조건을 순회하면서
불일치하는 리스트들을 빼는 방식으로 했는데,
이러한 방식은 시간초과가 나더라.
그리고 java에서는 전역변수를 정의할 경우 초기화하란 말이 없어서,
계속해서 틀렸습니다가 떴다.
level 2 문제라고는 하는데 아무리 봐도 아닌 것 같은데..
생활비..