[CodeKata] 코딩테스트 : 5.7(금), 문제풀이

🥋 문제1. 두 좌표 안에 속한 좌표들의 개수 구하기

location 좌표들의 배열([x,y]), s와 e 2개의 기준좌표가 매개변수로 주어진다.

이, s와 e 2개의 좌표로 인해 생기는 사각형 내에 속하는 좌표들의 개수를 반환하는 함수를 만드는 문제다.

(예시 : s [1, 4], e [4, 1] 내에 속하는 location [[0,3], [1,1], [1,5], [2,2], [3,3], [4,0]] 은 3개이다.)

 

 

🧮 풀이

function solution1(location, s, e) {
  const rangeX = [s[0],e[0]].sort((a,b) => a-b);
  const rangeY = [s[1],e[1]].sort((a,b) => a-b);
  let count = 0;
  
  location.forEach(pos => {
    const [x,y] = pos;
    if (x >= rangeX[0] && x <= rangeX[1] && y >= rangeY[0] && y <= rangeY[1]) count++;  
  })
  
  return count;
}

solution1([[0,3], [1,1], [1,5], [2,2], [3,3], [4,0]], [1,4], [4,1]);  // 3

1. 먼저, s와 e 두 좌표를 통해 사각형의 범위를 구한다. rangeX, rangeY 각각에 [시작, 끝] 형태로 sort를 통해 재정렬한다.
2. count는 우리가 반환할 정답이자, location을 순회하면서 범위에 속할때 개수를 누적할 변수이다.
3. location을 forEach()로 순회한다. 각 요소의 [x, y] 좌표를 받아온 뒤, 이것이 rangeX, rangeY 내에 포함된다면 count를 1 올린다.

---

🥋 문제2. 지그재그 2차원 배열에서 좌표의 값을 구하기

n * n의 2차원 배열이 생성되며, 내부 요소는 1부터 n제곱까지 채워진다.

각 요소는 0,0 -> 0,1 -> 1,0 -> 2,0 -> 1,1 -> 0,2 ... 순으로 지그재그로 채워진다.

이 때, (r,c) 좌표에 해당하는 값을 구하는 문제이다.

(예시 : n이 5인 경우, 1부터 25까지 지그재그로 채워진다. 이 때, r(3행), c(2열)에 해당하는 요소는 9가 된다.)

 

🧮 풀이

function solution(n, r, c) {
  r = r-1;
  c = c-1;
  const isOverHalf = r+c >= n;
  const line = isOverHalf ? n-r-1+n-c-1 : r+c;
  const lineNums = Array.from({ length: line+1 }, (_,i) => { return 1+ line * (line+1) / 2 + i })
  const idx = r+c % 2 === 0 ? c : r;
  
  return isOverHalf ? Math.pow(n,2) + 1 - lineNums[n-idx-1] : lineNums[idx]; 
}

solution(5,3,2)    // 9
solution(6,5,4)    // 29

1. 먼저, 우리는 Javascript 인덱스 패턴을 사용할 것이다. 그러므로, r과 c를 우선 1씩 차감해준다.
2. isOverHalf는 n * n 배열을 우상단 -> 좌하단으로 절반 잘랐을 때, 이 기준선을 넘는지 여부이다. 이 전까지는 규칙성으로 값이 바로 나오지만, 후에서는 n * n에서 값을 빼주는 형식으로 값을 구해야 한다. (대각선 기준으로 대칭형태를 취한다고 이해하면 된다.)
3. line은 (r,c) 좌표가 몇 번째 지그재그 선에 포함되어있는지의 인덱스이다. isOverHalf 경우엔 이와 대각선 대칭되는 라인을 구한다.
4. lineNums는 해당 지그재그 선에 포함되는 값들을 배열로 가져온다. 길이는 line + 1, 시작값(1부터 line까지 합 + 1)부터 1씩 증가.
5. idx는 lineNums에서 우리가 찾는 값의 위치다. 인덱스보단 접근방향으로 이해해보자. (line이 짝수면 열좌표, 홀수면 행좌표로 접근)
6. 이 인덱스를 통해 lineNums의 해당값을 찾으면 된다. 단, isOverHalf 인 경우 이 값을 n제곱 + 1에서 빼주면 된다.

---

🥋 문제3. 가장 긴 펠린드롬(좌우대칭 문자열) 찾기

s 문자열이 주어진다. 해당 문자를 잘랐을 때, 그 문자가 펠린드롬(좌우대칭) 이라면, 문자의 가장 큰 길이값을 반환한다.

(예시 : 'abacde'는 길이가 6이나 좌우대칭이 아니다. 하지만, 'aba'는 좌우대칭이므로 길이값 3을 반환한다.)

 

🧮 풀이

function palindrome(s) {
  for (let i = 0 ; i < Math.floor(s.length/2) ; i++) {
    if (s[i] !== s[s.length-i-1]) return false;
  }
  return true;
}

function solution3(s) {
  for (let l = s.length ; l > 0 ; l--) {
    for (let i = 0 ; i <= s.length - l ; i++) {
      if (palindrome(s.substr(i,l))) return l;
    }
  }
}

solution3('abcdcba')  // 7
solution3('abacde')	// 3

1. palindrome() 이라는 펠린드롬 검증 함수를 별도로 만들었다. s를 양쪽 끝부터 탐색하면서, 값이 다른 경우 false를 반환한다.
2. 양쪽부터 모든 값이 같다면 펠린드롬이므로 true를 반환한다. 이 방법이 split() + reverse() + join() 보다 효율성이 높게 나왔다.
3. s를 substr()로 자르면서 펠린드롬을 검증한다. 이중순회를 거치는데, l은 자를 길이(두 번째 인자), i는 시작 위치(첫 번째 인자) 이다.
4. l은 자를 길이로 s.length부터 1씩 감소한다. 처음에는 전체 문자열을 봐야하기 때문이며, l이 1이면 한글자이므로 종료될 것이다.
5. i는 시작점으로 0부터 s.length-l (l길이로 자를 수 있는 마지막 시작점) 까지 순회한다. 
6. 이렇게 자른 문자가 palindrome() 을 통해 참으로 판명되면, 문자열 길이인 l을 반환하면 된다.

---

🧐 리뷰

2시간 주어진 문제였기에 쉬울거으로 기대했으나 생각보다 어려웠다.

특히, 2번의 경우엔 앞부분의 규칙성을 응용해 뒷부분을 찾아야하는 점이 생각보다 쉽게 떠오르지 않았다.

3번의 경우엔 배열 메서드 -> 절반 순회를 통해 Big-O 효율성을 향상시켰으며, 앞으로도 배열 메서드 사용시 경각심을 가져야겠다.