페블_
반짝이는 시냅스
페블_
전체 방문자
오늘
어제
  • 전체글 보기 (96)
    • QA (0)
    • 프로젝트 회고 (4)
    • 프로젝트 과정 기록 (12)
    • UI 구현 연구일지 (8)
    • Front-end (31)
      • Javascript (7)
      • CSS (10)
      • React (5)
      • Typescript (3)
      • Nextjs (3)
      • 스타일링 라이브러리 (3)
    • Back-end (0)
      • Express (0)
      • DB (0)
    • CS (0)
      • 자료구조 & 알고리즘 (0)
    • CI&CD (1)
    • 툴 사용법 (4)
      • Git (1)
      • Library&패키지 (2)
      • 기타 개발관련 (1)
    • 알고리즘 이론 & 풀이 (36)
      • 백준(BOJ) (14)
      • 프로그래머스 (22)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 선형대수학
  • 생각
  • eslint
  • 알고리즘
  • Python
  • 백준
  • 토이프로젝트
  • 개발블로그_시작
  • chartjs
  • emotion
  • 파이썬
  • storybook
  • TypeScript
  • 시리즈_표지
  • UI 컴포넌트
  • 캐러셀
  • JS
  • react

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
페블_

반짝이는 시냅스

알고리즘 이론 & 풀이/프로그래머스

프로그래머스 Lv.2 | (완전탐색) 소수찾기 js

2023. 8. 8. 19:54

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=javascript

 

 

풀이

DFS 방식으로 재귀함수를 이용해 풀음. 다만 반복문에서 같은 수를 선택하지 않기 위해 visited를 두고 관리해 백트래킹함

  • 조합을 구하다보면 중복되는 조합이 생길텐데 어떻게 해결하냐 -> 조합한 결과를 Set()에 add한다.
  • '11'과 '011' 처럼 앞에 0이 붙을텐데 어떻게 처리할거냐 -> Number('011')을 하면 숫자 11로 변한다.
  • 소수 판별은 아예 isPrime()이라는 함수를 만들어 true/false를 반환하게 한다.
  1. 모든 가능한 조합을 만들어봐야 한다. 본인을 제외한 문자열을 점층적으로 더하도록 재귀함수를 짠다.
  2. 맨 처음 함수에 진입할 때는 빈문자열이므로 그 경우를 제외하고 set에 추가하기 위해 length>0일 때만 수행
  3. 이미 사용한 문자열인지는 visited[i]를 이용해 관리한다. 재귀함수에서 빠져나오면서 방문 여부를 해제하도록 재귀함수 호출 다음 줄에 visited[i] = false를 배치해 해지한다.
function solution(numbers) {
    function combination(currNum) {
        if(currNum.length > 0) {
            result.add(Number(currNum));
        }
        for(let i = 0; i < numbers.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                combination(currNum + numbers[i]);
                visited[i] = false;
            }
        }
    }
    
    const result = new Set();
    const visited = new Array(numbers.length).fill(false);
    
    combination('');
    return Array.from(result).filter(isPrime).length;
}

function isPrime(num) {
    if(num < 2) return false;
    for(let i = 2; i * i <= num; i++) {
        if(num % i === 0) return false;
    }
    return true;
}

 

combination('')를 호출했을 때 벌어지는 일 - numbers가 '1234'인 경우

  1. combination('') 호출 시 if문 건너뛰고 for i=0으로 인해 visitied[0]이 방문되었다고 바뀌고, combination('' + '1') 호출
  2. result에 1이 추가됨. for 0부터 검사해보니 visited[0] = true라 visited[1]을 true로 바꾸고 combination('12') 호출
  3. 반복하다가 combination('1234') 호출하면 result는 [1, 12, 123, 1234]가 됨. visited가 모두 true여서 for문 돌아도 아무 일이 일어나지 않음. stack에서 재귀함수 pop되면서 차례대로 combination() 호출문 뒤에 있던 visited[i] = false로 인해 모두 false로 초기화
  4. stack이 모두 pop 되어 최초에 combination('')을 호출했을 때의 for문 중 i=1을 할 차례가 왔음. 그래서 2부터 다시 조합 시작. 이 과정을 거치면 result는 [1, 12, 123, 1234, 2, 21, 213, 2134]가 됨.
  5. combination('')의 for문 모두 돌아서 1, 2, 3, 4로 시작하는 모든 조합을 만들게 되었음

'알고리즘 이론 & 풀이 > 프로그래머스' 카테고리의 다른 글

프로그래머스 Lv.2 | (DFS) 타겟 넘버 js  (0) 2023.08.09
프로그래머스 Lv.1 | (완전탐색) 모의고사 js  (0) 2023.08.09
프로그래머스 Lv.1 | 전화번호 목록 js  (0) 2023.08.08
프로그래머스 Lv.1 | 완주하지 못한 선수 js  (0) 2023.08.08
프로그래머스 Lv.1 | 폰켓몬 js  (0) 2023.08.08
    '알고리즘 이론 & 풀이/프로그래머스' 카테고리의 다른 글
    • 프로그래머스 Lv.2 | (DFS) 타겟 넘버 js
    • 프로그래머스 Lv.1 | (완전탐색) 모의고사 js
    • 프로그래머스 Lv.1 | 전화번호 목록 js
    • 프로그래머스 Lv.1 | 완주하지 못한 선수 js
    페블_
    페블_

    티스토리툴바