[CodeKata] getPrefix, romanToNum, moreThanHalf

OROSY·2021년 8월 29일
4

Algorithms

목록 보기
37/38
post-thumbnail

👨‍💻 CodeKata

이번주 동안에도 코드카타를 진행했습니다. 이번에는 새로운 짝님인 영호님과 하게 되었는데, 서로 알고리즘에 익숙하지 않아서 참으로 쉽지 않은 한 주였습니다.

특히, 알고리즘의 경우에는 집중해서 풀어야하는데 다른 사람들이 먼저 풀고, 크게 웃으며 좋아하는 모습을 보면서 다시 집중하기가 쉽지가 않았습니다.

그러한 감정들에 무던해지고 나는 나만의 길을 간다라고 생각해야하는데 어디 맘이 맘처럼 쉽게 되던가요. 그래서 결국, 이번주 문제 5개는 모두 풀지 못했습니다.

알고리즘에 자신감이 많이 떨어진 한 주였답니다. 그래도 오늘 다시 조용한 환경에서 새롭게 문제를 접하니 다시 문제가 잘 보이고 직접 문제를 풀게 되기도 하였습니다.

결론은 남의 일에 일희일비를 하지 말아야겠다는 다짐을 또 하게 되는 날이었습니다. 5개 중 3개를 풀어냈고 나머지 2개는 자기 전까지 한 번 도전해보겠습니다🙋‍♂️

📖 getPrefix

문제

strs은 단어가 담긴 배열입니다. 공통된 시작 단어(prefix)를 반환해주세요.

예를 들어 strs = ['start', 'stair', 'step'] return은 'st'
strs = ['start', 'wework', 'today'] return은 ''

풀이 (1)

1
2
3
4
5
6
7
8
9
10
11
12
13
function getPrefix(strs) {
  if (!strs.lengthreturn '';
  
  for (let i = 0; i < strs[0].length; i++) {
    for (let str of strs) {
      if (str[i] !== strs[0][i]) {
        return str.slice(0, i);
      }
      console.log(strs);
    }
  }
  return strs[0];
}
cs

이번 문제는 혼자 풀이를 하지 못해서 결국 답안을 보게 되었습니다. 반복문 중첩의 경우, 코드를 보면서 이해하기가 쉽지 않은 편이라 간결해서 좋은 코드인줄 알았는데 아니었습니다.

왜냐하면, 제가 아무리 머리를 돌려봐도 이해할 수 없기 때문이었죠. 물론, 간단한 코드로 보이지만 실제로 제 실력으로는 생각해도 어떻게 답이 나오는지 도저히 알 수가 없습니다.

그래서 알고리즘의 이해력이 낮은 저에게는 좋은 코드가 될 수 없기 때문에 다른 코드를 찾아보게 되었습니다.

풀이 (2)

1
2
3
4
5
6
7
8
9
10
11
12
let getPrefix = function(strs) {
  if (strs.length === 0return '';
  let r = '';
 
  for (let i = 0; i < strs[0].length; i++) {
    for (let j = 1; j < strs.length; j++) {
      if (strs[0][i] !== strs[j][i]) return r;
    }
    r += strs[0][i];
  }
  return r;
};
cs

먼저, early return 을 사용하여 중괄호의 중첩을 줄일 수 있는 코드입니다. 이또한 반복문 중첩이지만, 위의 것보다 훨씬 이해가 쉬웠습니다.

단어들이 같으면 새로운 변수에 넣어주고 서로 다르면 바로 멈추고 해당 변수를 리턴해주는 간단한 로직이지만 깔끔한 코드였습니다. 반복문 중첩의 경우, 어떤 것이 먼저 반복되어야하느냐의 순서가 중요한 것 같습니다.

이번 코드는 확실히 불필요한 중복을 피하는 좋은 코드라 생각합니다. 여러 번 반복해서 익숙해져야겠네요.

📖 romanToNum

문제

로마자에서 숫자로 바꾸기
1~3999 사이의 로마자 s를 인자로 주면 그에 해당하는 숫자를 반환해주세요.
로마 숫자를 숫자로 표기하면 다음과 같습니다.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

로마자를 숫자로 읽는 방법은 로마자를 왼쪽부터 차례대로 더하면 됩니다.
III = 3, XII = 12, XXVII = 27입니다.

그런데 4를 표현할 때는 IIII가 아니라 IV 입니다. 뒤의 숫자에서 앞의 숫자를 빼주면 됩니다. 9는 IX입니다.

I는 V와 X앞에 와서 4, 9
X는 L, C앞에 와서 40, 90
C는 D, M앞에 와서 400, 900

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function romanToNum(s) {
  let num = 0;
  const romanSymbol = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000
  }
 
  for (let i = 0; i < s.length; i++) {
    if (Object.keys(romanSymbol).includes(s[i])) {
      num += romanSymbol[s[i]]
    }
    }
  if (s.includes('IV'|| s.includes('IX')) {
    num -= 2;
  }
   if (s.includes('XL'|| s.includes('XC')) {
    num -= 20;
  }
  if (s.includes('CD'|| s.includes('XC')) {
    num -= 200
  }
  return num;
}
cs

처음에는 숫자를 로마자로 바꾸는 것으로 생각해서 매우 쉽게 생각했는데, 반대의 경우였습니다. 객체로 넣어서 풀이하겠다는 생각은 했는데 점점 먼저 푸시는 분이 늘어나면서 집중을 못했던 케이스입니다.

사실, 위의 로직은 어려운 것은 아니지만 빌런이 있습니다. 바로 IV, VI, XL, XC 이런 아이들이 문제가 됩니다. 그런데 이 부분은 백엔드의 희망, 준영님께서 위와 같은 방식으로 푸셨다는 이야기를 듣고 오늘 풀이에 적용을 했더니 매우 깔끔하게 풀렸습니다.

IV, VI, XL, XC 이런 아이들을 굳이 객체에 넣지 않고 차이나는 수만큼 빼게 되면 숫자로 변환할 수 있는 알고리즘 문제였습니다.

📖 moreThanHalf

문제

숫자로 이루어진 배열인 nums를 인자로 전달합니다.
숫자 중에서 과반수(majority, more than a half)가 넘은 숫자를 반환해주세요.

예를 들어,

nums = [3,2,3]
return 3

nums = [2,2,1,1,1,2,2]
return 2

가정

nums 배열의 길이는 무조건 2개 이상

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function moreThanHalf(nums) {
  const obj = new Object();
  const halfNum = Math.ceil(nums.length / 2)
  const keys = Object.keys(obj);
 
  for (let num of nums) {
    obj[num] = (obj[num] || 0+ 1;
  }  
  
  for (let key of keys) {
    if (obj[key] >= halfNum) {
      return Number(key);
    }
  }
}
cs

이번 문제도 과반수를 구하고 각각의 배열의 값을 객체로 넣는 것까지는 무리없이 진행하였습니다. 다만, 저 마지막 3줄을 생각하지 못해서 풀어내지 못했던 알고리즘 문제입니다.

계속 value 값만 추출해내려고 생각을 하다보니 쉽게 접근할 수 있는 obj[key]를 전혀 생각해내지 못했습니다.

✍️ CodeKata 풀이 계획

알고리즘을 풀다보면, 1시간이라는 정해진 시간과 주변 분들이 다 풀어나가는 모습을 보면서 마음이 조급해지게 됩니다. 그러다보면, 당연히 시야도 좁아지고 한 생각에 매몰되어 알고있으면서도 풀지 못하게 되는 경우가 생기게 되는 것 같습니다.

이제부터 코드카타는 잠시 방에서 나와서 조용한 곳에서 혼자 풀어보다가 이후 짝분과 이야기를 해보며, 풀이를 해나가는 방식으로 진행해야할 것 같습니다.

다시 한번, 마음을 가다듬고 다음 주부터 코드카타도 또 열심히 달려가보도록 하겠습니다.🏃‍♂️🏃‍♂️

profile
Life is a matter of a direction not a speed.

0개의 댓글