[인프런 javascript] 한장에 핵심 정리📝

김예지·2021년 11월 3일
0

[알고리즘] 개념

목록 보기
12/13

1-4) 1부터 N까지의 합 출력하기

function solution(n) {
    let arr=Array.from({length:n}, (v, i)=>i+1);
    console.log(arr.reduce((acc, v)=>acc+v)); 
}
solution(10)

단순히 for문을 사용해서 출력하는 것이 아닌, reduce메소드를 활용해서 풀 수 있는 문제이다.
또한, Array.from({length:n}, (v, i)=>i+1)을 통해 n=5가 입력되었을 때 [1, 2, 3, 4, 5] 유사배열이 생성된다.

1-7) 10부제

  • x(ex. 12)에서 일의 자리 구하기 : x%10

1-8) 일곱난쟁이

  • 거짓 난쟁이 2명 삭제(splice 메소드): 삭제를 할 때, 만약 앞의 인덱스를 뒤의 인덱스보다 먼저 삭제하게 되면 뒤의 인덱스 원소가 앞당겨지기 때문에, j를 삭제할 때 엉뚱한 것이 삭제된다. 이를 해결하기 위해, 뒤에 있는 인덱스인 j를 i보다 먼저 삭제해준다.
  arr.splice(j, 1); 
  arr.splice(i, 1);
  • 배열은 얕은복사를 함으로써, 하나를 바꾸면 같이 바뀐다.(let tmp=arr를 하면 arr가 바뀌면 tmp가, tmp가바뀌면 arr가 바뀐다. 같은 곳을 가리키고있기때문!) 따라서, slice()를 통해 이를 해결할 수 있다.

1-9) A를 #으로

  • s.replace(/A/g, '#')을 하면, s문자열에서 A를 모두 찾아서 #으로 바꾼다.
  • s.replace(/A/, '#')는 g이 없기 때문에, 그냥 s.replace(A, '#')과 같이 첫번째로 발견되는 A만 #으로 대체한다.

1-10) 문자 찾기

function solution(s, t) {
    return str.split('').filter(v=>v===t).length;
}
let str="COMPUTERPROGRAMMING";
console.log(solution(str, 'R'));

str에서 특정 문자 R을 찾는 방식이다. for문을 통해 풀 수도 있지만, 배열로 변환 후 filter해서 푸는 방법도 있다.

1-11) 대문자 찾기

  • 방법1
function solution(s) {
    return s.match(/[A-Z]/g).length;
}
let str="KoreaTimeGood";
console.log(solution(str));

  • str에서 대문자의 갯수를 구해보자.

  • match메소드는 문자열에서 정규식을 만족하는 것을 리턴한다. 여기서 s.match(/[A-Z]/g)은 ['K', 'T', 'G']를 리턴한다.

  • 방법2

function solution(s){         
  let answer=0; //카운팅
  for(let x of s){
    if(x===x.toUpperCase()) answer++; 
  }
  return answer;
}
  • x.toUpperCase()는 x=x.toUpperCase()와 같이 작성해야 원본까지 바뀐다. (문자열은 깊은 복사라서 독립적으로 움직임)
  • 아스키 코드로 바꾸는 방식도 존재!

1-16) 중복문자제거

'중복 제거'라는 타이틀에서 Set객체를 생각해서, 코드 1과 2는 Set객체를 통한 풀이이다.

  • 코드1
function solution(s) {
    let answer=new Set();
    for(let x of s){
        answer.add(x);
    }
    return [...answer].join('');
}
console.log(solution("ksekkset"));
  • 코드2
function solution(s) {
    s=s.split('');
    return [...new Set(s)].join('');
}
console.log(solution("ksekkset"));
  • new Set(배열)의 형태를 통해 배열에서 중복되는 것을 제거할 수 있다. 하지만 객체 형태로 리턴되기 때문에, 배열형태로 보고싶다면 [...new Set(배열)] 과 같이 작성해줘야한다.
  • 링크 참고
  • 코드3
function solution(s) {
    let answer='';
    for(let i=0; i<s.length; i++){
        if(s.indexOf(s[i])===i) answer+=s[i];
    }
    return answer;
}
console.log(solution("ksekkset"));
  • s.indexOf('k')=0 : (s="ksekkset"이라고 가정)'k'문자가 '처음'으로 발견되는 인덱스를 리턴한다.
  • s.indexOf('k', 1)=3: 1번째 인덱스이후 'k'문자가 있는 인덱스
  • s.indexOf(문자)=-1이면, 문자를 문자열에서 발견하지 못한 경우이다. 즉 문자가 문자열에 없을 때 -1을 리턴한다.

1-17) 중복단어제거

  • 코드1
function solution(s) {
    return s.filter((v, i) => s.indexOf(v)===i);
}
let str=["good", "time", "good", "time", "student"];
console.log(solution(str));
  • 코드2
function solution(s) {
    return [...new Set(str)];
}
let str=["good", "time", "good", "time", "student"];
console.log(solution(str));

2-7) 봉우리(네방향 탐색 문제)

3-2) 유효한 팰린드롬

  • replace(/[^a-z]/g, ''): 소문자가 아닌것을 모두 찾아서 ''로 대체하라(정규표현식 사용)

3-3) 숫자만 추출

  • parseInt(String, radix): String문자열을 radix(2-36)진법으로 변환한다. 만약 radix가 없을 때, String이 0으로 시작한다면 radix는 8진이거나 10진이다.
    만약, string자리에 문자열이 아닌 것이 들어온다면 자동으로 변환된다.
    parseInt(x), Math.floor(x): x의 소수점을 삭제한다. 즉, 몫만 나타내야할 때 반드시 사용해준다.
  • 코드 (결과: 208)
function solution(str){  
    str=str.replace(/[^0-9]/g, '');
    return parseInt(str, 10);
}
let str="g0en2T0s8eSoft";
console.log(solution(str));

3-4) 가장 짧은 문자거리

3-5) 문자열 압축

  • 빈문자열 만들어주지 않아도, 마지막은 undefined와 비교하며 다르다는 것을 판단할 수 있다. 
    console.log(s[s.length]); //undefined
    console.log(s[s.length-1]); //E
    console.log(s[s.length]===s[s.length-1]); //false

4-2) 뒤집은 소수

    console.log(parseInt('030')); //30
    console.log(Number('030')); //30

parseInt, Number를 통해 문자를 숫자로 변환할 때, 앞의 0은 자동 삭제된다.

4-4) 졸업 선물

arr=arr.sort((a, b)=> (a[0]+a[1])-(b[0]+b[1])); 
//[ [ 2, 2 ], [ 4, 3 ], [ 4, 5 ], [ 6, 6 ], [ 10, 3 ] ]

4-5) K번째 큰수

5-1) 두 배열 합치기(투포인터)

5-2) 공통원소 구하기(투포인터)

5-4) 연속 부분수열

5-5) 최대 매출(슬라이딩 윈도우)

5-6) 학급 회장(해쉬)

  • 해쉬에서 for문 쓸 때
	for(let [key, val] of map){
      ...
    }
  • 해쉬에서 sort()를 통해 정렬하고 싶을 때
    문자 정렬은 [...map].sort();와 같이,
    숫자 정렬은 [...map].sort((a, b)=>b[1]-a[1])와 같이 쓰면 된다. (여기서는 value를 내림차순 정렬한다)

5-7) 모든 아나그램 찾기(해시, 투포인터, 슬라이딩 윈도우)

6-2) 괄호 문자 제거

  • while문을 이렇게 사용할 수도 있다!
if(x===')'){
	while(stack.pop()!=='('); 
}

6-4) 후위식 연산

  • 조건문은 중첩이 가능하다!(당연!)
  • 헷갈리는 개념
    console.log('3'+'5'); //'35'
    console.log(typeof('3'+'5')); //string
    console.log(!isNaN('3')); //'3'이 숫자면 true (true)

6-5) 쇠막대기

6-7) 교육과정 설계

7-6) 장난꾸러기 현수

  • arr를 복사할 때 주의하기! arr는 얕은 복사를 하기 때문에, 독립적으로 사용하고 싶다면 반드시! slice()로 깊은 복사를 해줘야한다. 
function solution(arr) {
    let answer=[];
    const tmp=arr.slice().sort((a, b)=>a-b); //반드시 sort와 같은 메소드 쓰기 전에 arr.slice()해줄 것
    console.log(tmp); //[1, 2, 3, 4, 5]
    console.log(arr); //[1, 4, 3, 2, 5]
}   
let arr=[1, 4, 3, 2, 5];
console.log(solution(arr));

7-7) 좌표 정렬

  • a[0]===b[0]일 때, a[1]-b[1]로 정렬하고, 같지 않을 때는 a[0]-b[0]으로 정렬
    arr.sort((a, b)=>{
        if(a[0]===b[0]) return a[1]-b[1];
        else return a[0]-b[0]
    });

7-9) 결혼식

  • sort에서 문자정렬을 조절 하고 싶을 때 
   map.sort((a, b)=>{
        if(a[0]===b[0]) return a[1].charCodeAt()-b[1].charCodeAt(); //a[1], b[1] 오름차순 정렬 
        else return a[0]-b[0];
   });

8) DFS, BFS

  • DFS: 스택프레임, 재귀함수 사용, 깊이우선탐색
  • BFS: 큐

8-4) 부분집합 구하기(DFS)

8-5) 합이 같은 부분집합(DFS)

8-6) 바둑이 승차(DFS)

  • 결국 이것도 부분집합! 부분집합에서 dfs 사용할 수 있음을 기억하기!
  • 코드
    https://velog.io/@rladpwl0512/8-6-%EB%B0%94%EB%91%91%EC%9D%B4-%EC%8A%B9%EC%B0%A8DFS
  • DFS내에서 return 한다고 해서 스택의 모든 dfs가 종료되는게 아니라는 것을 잘 기억하자! (8-5도 마찬가지로, 'flag=1일때 종료해라'고 할때, 모든 스택이 한번에 종료되는 것이 아닌, 하나씩 pop되고, 검증 후 종료된다.)
  • 중간에 sum이 더 커지는 경우를 가장 앞에서 검증해서, 바로 return 해주기!(해당 DFS 종료)

8-7) 최대점수 구하기(DFS)

8-8) 중복순열 구하기

8-9) 동전 교환(DFS)

  • DFS로 풀지 않았을 때, 그리디를 사용해서 큰 거스름돈 먼저 소거하는 방식으로 진행한다. 
function solution(m, arr) {
    let answer=0;
    arr.sort((a, b)=>b-a); //내림차순 정렬 
    let i=0; 
    while(m!==0){
        answer+=parseInt(m/arr[i]);
        m-=(arr[i]*parseInt(m/arr[i]));
        i++;
    }
    return answer;
}   
let arr=[1, 2, 5];
console.log(solution(18, arr));

8-10) 순열 구하기

8-11) 팩토리얼

8-13) 수열 추측하기(순열, 조합의 경우수 응용)

https://velog.io/@rladpwl0512/8-13-%EC%88%98%EC%97%B4-%EC%B6%94%EC%B8%A1%ED%95%98%EA%B8%B0%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9%EC%9D%98-%EA%B2%BD%EC%9A%B0%EC%88%98-%EC%9D%91%EC%9A%A9

8-15) 수들의 조합

9-2) 경로 탐색(인접 행렬)

9-3) 경로 탐색(인접 리스트)

9-4) 미로탐색(DFS)

9-5) 이진트리 넓이우선탐색 (BFS)

9-7) 섬나라 아일랜드(DFS, BFS)

profile
김예지
내가 짱이다 😎 매일 조금씩 성장하기🌱
이전 포스트

[프로그래머스 고득점 KIT] 한장에 핵심 정리📝

다음 포스트

[프로그래머스 level2] 한장에 핵심 정리📝

0개의 댓글