첫 25분의 고민 과정
3개의 모듈로 분해하기
문제를 읽고 가장 먼저 떠올린 것은 순열이었다. 조건을 파싱 해서 조건에 맞게 인원들을 배치시키고 순열의 결과를 얻어내고자 했다. 예를들어 라이언와 어피치의 거리가 0이라면 라이언와 어피치를 하나로 묶고 나머지 인원들을 배치시키는 방식으로 순열의 경우의 수를 구하는 것이다.
하지만 n개의 원소로 주어지는 data는 무려 100개까지도 주어질 수 있다.
이 모든 것을 파싱해서 캐릭터들을 묶어내는 것?은 불가하다고 판단했다. [ data로 주어질 수 있는 경우의 수는 어마무시하다. 조건 3개, 숫자 간격 0~6, 케릭터 2개를 뽑는 조합... ]
다행히도 친구들의 수는 8개로 고정적이다. 완전 탐색으로 순열을 고려하면 8!로 40320의 경우의 수가 존재한다.
이 정도면 연산으로 충분히 커버할 수 있는 수다.
1. 완전탐색으로 순열의 경우의수 만들어내기
2. 조건 파싱 하기
로 이 문제를 해결해볼 수 있을 것 같았다.
접근해야 할 알고리즘 기술 선택하기
그래서 완전 탐색을 알고리즘 기법으로 택했다. 그리고 매 경우의 수마다 조건들을 파싱 하기로 했다.
그런데 나는 완전 탐색을 위한 순열을 마련하는 방법을 몰랐다. 빠르게 구글링을 했고 다음의 알고리즘을 찾아냈다.
[재귀 방식이다.]
static String friends = "ACFJMNRT";
static final int FRIENDS_NUM = friends.length();
static boolean[] visited = new boolean[FRIENDS_NUM];
static int[] friends_position = new int[FRIENDS_NUM];
public static void dfs(int idx){
if(idx == FRIENDS_NUM){
if(check()) answer++;
}
else{
for(int i=0; i < FRIENDS_NUM; i++){
if(!visited[i]){
visited[i] = true;
friends_position[idx] = i;
dfs(idx + 1);
visited[i] = false;
}
}
}
}visited 배열을 두어서 방문한 적이 있는 곳은 들리지 않는 방식으로 순열을 만들어내는 알고리즘이다.
FRIENDS_NUM = 8이라고 보면 된다.
friends = "ABC"라고 하면 ABC, ACB, BAC, BCA, CAB, CBA 이런 식의 순열이 만들어진다고 보면 되는데
문자열을 만드는 것은 연산에 있어서 비효율적이기에 friends_position을 두어 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1],
[3, 1, 2], [3, 2, 1] 방식으로 문자열의 index를 저장하는 것으로 두기로 했다.
그리고 idx가 8에 이르면 거기서 condition을 체크해보기로 했다.
필요한 자료구조 고민해보기.
friends 문자열을 두고 파싱 하면서 조건부를 검색해야 하는 문자열 배열의 conditions을 두었다.
static String[] conditions;
static String friends = "ACFJMNRT";
// main 문에서
conditions = data; // 들어온 데이터를 받아서 공유하게한다.
이후 조건부를 파싱 하는 부분을 짜내려 갔다.
public static boolean check(){
int f1, f2, range;
char op;
for(String condition : conditions){
f1 = friends_position[friends.indexOf(condition.charAt(0))];
f2 = friends_position[friends.indexOf(condition.charAt(2))];
op = condition.charAt(3);
range = Character.getNumericValue(condition.charAt(4)) + 1;
if(op == '='){ if(Math.abs(f1-f2)!=range) return false;}
else if(op == '>'){ if(Math.abs(f1-f2) <= range) return false;}
else {if(Math.abs(f1-f2) >= range) return false;}
}
return true;
}
op 처리 부분이 조금 까다로웠다. 조건에 하나라도 매칭이 안 되는 경우는 조건에 만족하지 않으므로 return false를 반환해야 했다. [ 처음에 조건을 만족하면 그냥 바로 return true로 처리해서... 기댓값이 다르게 나왔다. ]
25분의 뇌 컴파일 이후 첫 풀이 25분 & 막혔던 부분
완전 탐색을 해결하고 나서 조건의 문자들을 파싱 하는 부분이 조금 까다로웠다.
문자열 파싱에서 charAt() 메서드는 해당 index에 있는 문자를 반환하는데 숫자의 경우도 char로 처리된 숫자를 반환하기 때문이다. 이 부분을 그냥 숫자로 생각하고 처리해서 원하던 결과를 얻지 못했다.
몇몇 개의 출력문을 통해 이 부분에서 문제가 있다는 것을 발견했고 Character.getNumericValue() 메서드로 숫자를 추출하게 했다. 또한 거리라는 게 기본적으로 index 차이에서 1을 낮춰야 한다.
거리가 = 0이라는 것은 문자열에서 index 차이가 1만큼 차이가 날 수 있음을 의미한다. 고로 range 파트에 1을 추가해서 처리했다. 이후 Math.abs()를 통해 절댓값을 확인하는 방식으로 진행했다.
public static boolean check(){
int f1, f2, range;
char op;
for(String condition : conditions){
f1 = friends_position[friends.indexOf(condition.charAt(0))];
f2 = friends_position[friends.indexOf(condition.charAt(2))];
op = condition.charAt(3);
range = Character.getNumericValue(condition.charAt(4)) + 1;
if(op == '='){
if(Math.abs(f1 - f2) != range) return false;
} else if(op == '>') {
if(Math.abs(f1-f2) <= range) return false;
} else {
if(Math.abs(f1-f2) >= range) return false;
}
}
return true;
}전체 코드
class Solution {
static String[] conditions;
static String friends = "ACFJMNRT";
static final int FRIENDS_NUM = friends.length();
static boolean[] visited = new boolean[FRIENDS_NUM];
static int[] friends_position = new int[FRIENDS_NUM];
static int answer;
public int solution(int n, String[] data) {
answer = 0;
conditions = data;
dfs(0);
return answer;
}
public static void dfs(int idx){
if(idx == FRIENDS_NUM){
if(check()) answer++;
}
else{
for(int i=0; i < 8; i++){
if(!visited[i]){
visited[i] = true;
friends_position[idx] = i;
dfs(idx + 1);
visited[i] = false;
}
}
}
}
public static boolean check(){
int f1, f2, range;
char op;
for(String condition : conditions){
f1 = friends_position[friends.indexOf(condition.charAt(0))];
f2 = friends_position[friends.indexOf(condition.charAt(2))];
op = condition.charAt(3);
range = Character.getNumericValue(condition.charAt(4)) + 1;
if(op == '='){
if(Math.abs(f1 - f2) != range) return false;
} else if(op == '>') {
if(Math.abs(f1-f2) <= range) return false;
} else {
if(Math.abs(f1-f2) >= range) return false;
}
}
return true;
}
}이유는 모르겠으나 static int answer = 0; 을 넣고 시작하면 제출 시 오답으로 처리된다.
solution 파트에서 0으로 대입하고 시작해야 문제없이 정답으로 처리된다.
후기
손 코딩 뇌 컴파일은 눈 디버깅은 나는 프로그래머스(팟캐스트)의 하광성 님이 이전에 진행했던 모임이다.
프로그래밍을 할 때 가장 많은 시간과 노력이 드는 부분은 의외로 "디버깅"이다. 어디가 잘못되었는지를 파악해야 하는데 복잡하게 얽힌 프로그램을 이해하기란 상당히 까다롭기 때문이다.
그런 의미에서 하광성 님은 무작정 코드로 향하는 것보다 먼저 손으로 코딩해보고, 그리고 뇌로 컴파일해보고, 다른 이들의 눈을 통해 오류가 없는지 디버깅해보는 시간을 가지는 모임을 가진 것 같다.
이 좋은 아이디어를 채용해서 나는 알고리즘 풀이에 25분간 손 코딩, 뇌 컴파일을 적용해보기로 했다. [ 타인들의 눈 디버깅을 얻기 못해서 눈 디버깅은 빼기로 했다. ]
이번 문제는 첫 시도인데, 꽤나 좋은 시간이 되었다.
이전에 문제를 풀던 것과 다른 점은 다음과 같다.
1. 도메인 로직에 좀 더 집중해보게 된다. 이번 문제의 경우 조건이 1~100개까지 주어졌다. 이전에 나라면 이 조건들을 파싱 해보는 것부터 시작했을 것이다. 손 코딩 과정을 통해 이 조건들을 파싱 해서 순열을 만드는 것은 불가능하다는 것을 알게 되었고 빠르게 다른 경로를 파악해보게 되었다.
2. 문제를 여러 부분으로 나눠보게끔 생각하게 해 주었다.
문제를 보며 10분이 지난 시점에 "완전 탐색"으로 풀기로 결정했다. 그리고 기타 정보들을 담을 컨테이너로는 문자열 배열과 문자열이면 충분하다는 판단을 내리게 되었다.
알고리즘 기법 + 자료구조를 택했으면 손 코딩 파트는 끝난 것이다.
이후 도메인 로직은 디버깅 과정을 거치면서 시행착오를 거쳐야 한다.
그렇게 이 문제를 푸는데 대략 1시간 정도 걸렸다.
앞으로의 목표는 20분간 문제의 유형을 파악하고, 알고리즘 기법을 택하고 자료구조를 택하는 시간을 가져보는 것이다.
그리고 2~3개의 메서드로 나눈 후 주석을 통해 대략적인 목표를 작성하고 코딩해보기로 했다.
문제 분류
- 완전 탐색(순열), 도메인 조건 처리
필요한 예상 시간
문제를 읽고, 도메인 로직을 처리하는데 빠르게 문제를 파악했다면 30분 정도 걸리지 않을까 한다.
나의 경우는 대략 1시간 정도 걸린 문제였다.
개인적인 난이도
프로그래머스 Level 2에 올라온 카카오 문제들 대부분이 이러한 난이도를 가진 것 같다.
내 기준 난이도가 꽤나 높은 편에 속한다... 익숙해져야지 ㅠㅠㅠ...
'취업준비 > 알고리즘 문제 반추' 카테고리의 다른 글
| 프로그래머스 사이트 문제 정리하기. [20210928시작][최신 갱신: 20210930] (0) | 2021.09.28 |
|---|---|
| 2021 카카오 블라인드 채용 메뉴 리뉴얼 [프로그래머스][Level2] [자바] (0) | 2021.09.26 |
| 2019 카카오 개발자 겨울 인턴십 - 튜플- [프로그래머스][Level2] (0) | 2021.09.10 |
| 프로그래머스 Level2 프린터. [상당히 애먹은 문제..] [ 나만의 풀이 ] (0) | 2021.09.09 |
| 프로그래머스 - 소수 만들기 (0) | 2021.08.18 |