KT 에이블 스쿨 (못풀어서 아쉬운 문제..)
저번주에 KT 에이블스쿨에서 시행한 코딩테스트를 봤다. 총 3문제였다.
1번은 반복문을 통해 구현하면 됐고 2번은 잘모르겠었다.
3번을 마주하니 필자가 요즘 가장 열심히 해온 DFS,BFS의 문제로 보였다.
자세히 기억은 안날뿐더러 문제를 유출하면 안되기 때문에 자세한 문제는 포스팅할 수 없지만 대략적으로 최소가 되는 방법의 수를 찾는 문제였다 !!
너무 자신감있게 시도했지만 이상한 부분에서 나의 약점을 찾을 수 있었다.
재귀를 잘 다룰수있다 생각했는데 막상 긴장되는 환경에서는 제대로 다루지 못했다..
아무래도 재귀에 대한 이해가 부족하다고 판단해서 문제풀이에 필요했던 조합을 재귀로 나타내는 코드를 다시한번 정리해봐야겠다.
조합문제
대략적으로 배열 ["ABC","CFF","GDH","HHQ"]이 있을 때 각 배열의 원소가 다른 배열에 없는 가장 작은 단위를 구하면 됐던 거 같다.
ABC 기준에서는 A, B, C가 가능하다. CFF에서는 F가 가능하다.
이런 식으로 가장 작은 단위인데 다른 배열과 겹치지 않는 최소의 단위를 구하면 되는데 최소 2개 부터였다.
흠 그럼 그냥 재귀를 사용해서 AB, BC 확인 CF, FF 확인 GD, GH, DH를 확인할 수 있으면 됐다.
근데 참 이게 안풀렸다. 자꾸 모든 경우가 확인되고 내가 원하는 경우는 겹치지 않고 앞에서 뒤로의 경우만 계산하고 싶었다.(조합하고싶었다.)
그럼 어떻게 구현하면 될까?
function solution(operations) {
const arr ="ABCDEFG"
const dfs=(sum,index,visited)=>{
if(sum.length===2){
return;
}
for(let i = 0 ; i <arr.length; i++){
if(!visited[i]&&index<i){
visited[i]=true
dfs(sum+arr[i],index,visited)
}
}
}
for(let i = 0 ; i<arr.length; i++){
const visited = Array.from({length:arr.length},()=>false)
dfs(arr[i],i,visited)
}
}이렇게 하면된다.. 분명 이렇게접근했는데 왜 안됐을까
반복문이 조금 더 복잡하긴했지만 결국 관통하는 로직은 위 코드인데 시험볼때는 참 떠오르지 않았다. 그래서 이번에 제대로 순서를 적용해보겠다.
자, 먼저 dfs의 인자를 sum, index, visited로 결정한 이유는 ?
sum 은 재귀를 통해 계속 더해줘야한다. 그리고 index는 ?? 앞의 인덱스보다 큰 인덱스만 더해줄 수 있게 하기위해 필요하다. visited는?? for문을 사용해서 dfs를 실행해줄것이기 때문에 실행할 때 마다 visited의 reset이 필요해서 매개변수로 넣어서 함수를 만들었다.
위 코드의 결과는
A
AB
AC
AD
AE
AF
AG
B
BC
....
로 원하는 결과가 나온다.
visited[i]의 true를 해주고 탈출하는 visited[i]=false를 해주지 않았기 때문에 dfs는 뒤로 돌아오지 않는다. 즉 index는 전진만한다.
그리고 visited의 방문은 매번 reset되기때문에 다시 B로 시작하면 그 이후의 경우만 더해준다.
그렇다면 다음과 같은 문제가 있다면 어떻게 풀수있을까
예시문제 ❗️
배열 ["HINICE","TOMEET","YOU","IWANT","TOSEE","HIM"]
이라는 배열이 있을때 위 단어중 2개 이상의 최소한의 스트링으로 나눌때 다른 단어에는 없는 새로운 문자일 경우 그 최소한의 문자 길이를 return 해라
라는 문제가 있다면 HINICE에 경우 HI는 있고 IN은 다른 배열에 존재하지 않는다. 그렇기에 IN인 2가 최소의 길이로 정답이 되어 배열에 저장된다.
코드로 해결해보자
function solution(operations) {
const arr =["HINICE","TOMEET","YOU","IWANT","TOSEE","HIM"]
const check = (arr,target)=>{
let count = 0
for(let i = 0 ; i <arr.length; i++){
if(arr[i].includes(target)){
count++
}
if(count>=2){
return false
}
}
return true
}
// arr의 원소에 target이 하나라도 포함되면 false
// arr의 원소에 target이 하나도 포함되지 않으면 true
let answer= "123123123"
const dfs=(sum,targetString,index,visited)=>{
if(sum.length>=2 && check(arr,sum)){
if(sum.length < answer.length){
answer = sum
}
return
}
if(sum.length===6){
return
}
for(let i = 0; i< targetString.length; i++){
if(!visited[i]&&index<i){
visited[i]=true
dfs(sum+targetString[i],targetString,index,visited)
}
}
}
let answers = []
for(let i = 0 ; i < arr.length; i++){
for(let j = 0;j<arr[i].length;j++){
const visited = Array.from({length:arr[i].length},()=>false)
const targetString = arr[i]
dfs(arr[i][j],targetString,j,visited)
}
answers.push(answer)
answer="123123123"
}
console.log(answers)
}
기본적으로 배열안에 string이 있기때문에 이를 자르려면 이중배열에서 Dfs를 사용해주어야하는데 실제 문제에서는 for문 1개로 위 dfs를 실행하려해서 문제가 통과되지 않았던 거 같다. 실력부족이다.
또, for문에서 visited의 범위는 j인지 i인지를 신경써야하고
index를인자로받아서 여기 인덱스부터 이 후 인덱스만 더하는 경우는 좋은 발상같다. 또, visited를 인자로받아 반복문을 순회할때마다 리셋이 되는 것도 좋은거 같다.
visited(방문처리)를 잘 다뤄야 원하는 결과를 도출 할 수 있는 거 같다.
앞으로 이러한 문제가 나오면 방문처리, 순회조건, 탈출조건 등을 잘 구분해야겠다!
비록 시험에선 풀지못했지만 앞으로 비슷한 문제가 나오면 풀 수 있을 거 같다!
