최대한 코테 공부를 꾸준히 하려고 했으나 연말연초에 짧게 인턴을 하면서 또 코테에 소올해졌다.
파이썬으로 알고리즘에 대한 기초를 다지고 자바스크립트로 전향한지는 좀 됬다.
요즘 공채시즌과 더불어 잡힌 코테가 몇 개 있어서 다시 꾸준히 코테를 공부해보고자.. 오늘 푼 문제를 간단하게 포스팅해보려고 한다.
오늘 풀었던 문제는 프로그래머스에 [의상]이라는 문제이다.
코딩테스트 연습 탭에 들어가서 알고리즘별로 대표적인 예제들을 풀어보는걸 먼저 하고 있다.
이 문제는 이전에 파이썬으로 풀었던 문제지만 의외로 같은 문제도 js로 풀려고 하면 어렵다..!!🥲
그럼 풀이 시작해봅시😶
💡 해시
요즘은 문제를 풀면서 최대한 카테고리에 맞는 알고리즘을 사용하려고 노력 중이다.
오늘은 해시에 대해서 알아보고 문제 풀이로 넘어가보려 한다.
그래서 Hash가 뭔데?
❗️잠깐❗️ 해시테이블에 대해서도 알아보자!
해시 테이블은 key와 value가 쌍을 이루는 형태로 데이터가 저장되어 있는 자료구조를 말한다.
Example👇
이름: 홍길동
직업: 개발자
나이: 25
이런식으로 위의 예시에서 이름, 직업, 나이가 key에 해당하고 홍길동, 개발자, 25가 value에 해당한다.
그냥 이렇게 보면 우리가 자주 쓰는 배열을 떠올리기 쉽다.
배열과의 차이점은 key값이 배열은 index만 지칭하지만, 해시 테이블은 문자열 숫자 모두 key값으로 쓰일 수 있다!
이제 진짜 Hash가 뭔지 보자
해시는 hash function이라는 말 그대로 해시 함수를 이용해 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
이 해시 함수가 우리가 방금 위에서 살펴본 해시 테이블 자료구조에 사용되는 것이다.
해시 함수는 큰 파일에서 중복되는 기록을 찾을 수 있어 빠른 데이터 검색에 유리하다.
key값을 안다면, 이 key값이 인덱스의 역할을 하면서 그에 대응되는 value를 바로 찾을 수 있기 때문에 속도가 빠르고 평균 시간 복잡도가 O(1)에 수렴한다.
예시로 보면 이해가 더 쉽다!
// Example
const person = {};
person['firstname'] = "홍";
person['lastname'] = '길동';예시를 보면 알겠지만 우리가 많이 봐왔던 객체로 구현할 수 있고, 객체도 해시 테이블의 일종인 것이다.
💡 문제 해결
(문제 설명과 예제는 위의 링크를 참고해주세요🥹)
⚒️ point
내가 생각한 문제 풀이 프로세스는 다음과 같다.
headgear,eyewear등 카테고리별로 의상의 종류를 분류해야 한다.- 조합할 수 있는 수를 구하는 것이므로 어떤 걸 입는지는 중요하지 않다.
- 카테고리별로 의상의 개수를 카운트해서 조합으로 계산하면 된다.
- 주의: 카테고리별로 하나만 착용할 수 있다/아무것도 착용하지 않는 경우는 카운트하지 않는다
function solution(clothes) {
let answer = 1;
const obj = {};
clothes.map(c => {
// (ex)headgear라고 했을 때, 이 key가 obj내에 있을 경우
if(obj[c[1]]){
return obj[c[1]]+=1;
}else{
// 없는 카테고리면 새로 생성
return obj[c[1]] = 1;
}
})
// 여기까지 하면 각 카테고리별로 의상의 종류가 몇 개인지 카운트됨
// 의상의 종류의 수를 계산에 사용하므로 값만 추출
const value = Object.values(obj);
// 해당 의상을 안입는 경우를 생각해서 +1을 해서 모두 곱함
for(let i = 0; i < value.length; i++){
answer *= value[i]+1;
}
// 아무것도 안입는 경우를 제외해야 하므로 -1
return answer-1;
}value[i]+1 부분에 대해 부가적인 설명을 해보자면, 예를 들어, 모자가 a, b 두 개가 있을 때 3가지의 경우가 존재한다.
- a를 착용
- b를 착용
- 모자를 착용하지 않음
따라서obj에 저장된 내역은headgear: 2이지만 실제로 3개의 경우의 수가 존재하므로 +1을 해주는 것이다.
이후 의상 카테고리가 headgear, eyewear 두 종류일 때, 둘 다 안입는 경우도 카운트 될 것이다.
하지만 이 경우는 제외해야 하므로 마지막에 값을 리턴할 때 -1을 해줘야 한다.
이렇게 문제 풀이 끝!
오랜만에 코테 푸니 머리가 굳어버린 기분이었다,,, 진짜 하루에 한 문제씩은 꼭 풀어야겠다.
앞으로 다시 1일 1코테 도전-!
