본문 바로가기

Algorithm54

[큐] 공주 구하기 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 괴물에게 잡힌 이웃나라의 공주를 구하기 위해 N명의 왕자가 나섰다. 공주를 구할 단 한 명의 왕자를 고르기 위해 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 고르기로 했다. 왕은 왕자들을 1부터 N까지 순서를 매겼다. 그리고 1번 왕자부터 시계방향으로 돌아가며 동그랗게 앉게 한 후 1부터 번호를 외치게 했다. 한 왕자가 특정한 숫자 K를 외치면 그 왕자는 공주를 구하러 가는 데서 제외되고 원 밖으로 나온다. 그리고 다음 왕자부터 다시 1부터 시작해 번호를 외친다. 이렇게 해서 마지막에 남은 왕자가 공주를 구하러 갈 수 있다. 예를 들어 8명의 왕자가 있고 3을 외친 왕자가 제외된다고 하면 제외되는 순서는 3, 6, 1, 5, .. 2022. 1. 3.
[스택] 쇠막대기 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다. 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이.. 2021. 12. 26.
[스택] 후위식 연산 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 후위 연산식이 주어지면 연산한 결과를 출력한다. 만약 3 * ( 5 + 2 ) - 9 를 후위 연산식으로 표현하면 3 5 2 + * 9 - 로 표현되며 그 결과는 12이다. 👉 입력 첫 번째 줄에 후위 연산식이 주어진다. 이때 연산식의 길이는 50을 넘지 않으며 1 ~ 9의 숫자와 +, -, *, / 의 네 가지 연산자로만 이루어진다. 👈 출력 연산한 결과를 출력한다. 💡 사용된 개념 후위식 연산(postfix) 피연산자가 먼저 쓰이고 그 뒤로 연산자가 나오는 형태이다. 예를 들어 5 + 2를 후위표기식으로 바꾼다면 5 2 +이다. 후위 표기식을 계산하는 방법은 다음과 같다. 3 5 2 + * 9 - 첫 번째 연산자 + 의 앞에 있는.. 2021. 12. 26.
[스택] 괄호 문자 제거 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 입력된 문자열에서 소괄호 사이에 존재하는 모든 문자를 제거하고 남은 문자만 출력한다. 만약 입력된 문자열이 (AB(C)D)E(F)라면 출력은 E가 된다. 👉 입력 첫 번째 줄에 길이가 100을 넘지 않는 문자열이 입력된다. 👈 출력 괄호 사이의 모든 문자를 지우고 남은 문자들을 출력한다. 📝 풀이 function solution(s) { let answer; let stack = []; for (const i of s) { if (i === ")") { while (stack.pop() !== "("); } else stack.push(i) } answer = stack.join('') return answer; } let str =.. 2021. 12. 20.
[스택] 올바른 괄호 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 괄호로 구성된 문자열이 입력으로 주어질 때, 이들이 올바른 괄호이면 "YES", 아니면 "NO"를 출력한다. (())()(())의 경우 올바른 괄호이나 (()()의 경우에는 올바른 괄호가 아니다. 👉 입력 첫 번째 줄에 괄호로 구성된 문자열이 주어진다. 문자열의 최대 길이는 30이다. 👈 출력 "YES" 혹은 "NO"를 출력한다. 💡 사용된 개념 Stack(스택) 특수한 목적을 가지는 자료구조로 순서가 있는 entry들의 자료구조이다. Stack은 LIFO(Last-In, First-Out)의 구조로 저장된 data를 꺼낼 때 가장 최근에 들어간 data부터 꺼내진다. Stack에 넣는 작업을 push, 꺼내는 작업을 pop이라고 하.. 2021. 12. 20.
[투포인터/해시/슬라이딩윈도우] 모든 아나그램 찾기 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 아나그램이란 두 문자열이 알파벳의 나열 순서는 다르지만 그 구성이 일치한 두 문자열을 말한다. 긴 문자열 A와 짧은 문자열 B가 주어진다. A 문자열에서 B 문자열과 아나그램이 되는 A의 부분 문자열 개수를 구해 출력한다. 아나그램 판별 시 대소문자가 구분되며 부분 문자열은 연속된 문자열이다. 👉 입력 첫 번째 줄에 A 문자열이 입력된다. 두 번째 줄에 B 문자열이 입력된다. 이때 A 문자열의 길이는 10,000을 넘지 않으며 B 문자열은 A 문자열보다 길이가 작거나 같다. 👈 출력 A의 연속 부분 문자열이 B 문자열과 아나그램이 되는 개수를 출력한다. 📝 풀이 function compare(map, t) { for (const x .. 2021. 12. 20.
[프로그래머스] 크레인 인형뽑기 게임 문제 링크 >> https://programmers.co.kr/learn/courses/30/lessons/64061 📋 문제 게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. "죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다. 게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다.) 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로.. 2021. 12. 19.
[프로그래머스] 오픈채팅방 문제 링크 >> https://programmers.co.kr/learn/courses/30/lessons/42888 📋 문제 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. "[닉네임]님이 들어왔습니다." 채팅방에서 누군가 나가면 다음 메시지가 출력된다. "[닉네임]님이 나갔습니다." 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다. 채팅방에서 닉네임을.. 2021. 12. 19.
[해시] 아나그램 자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다. 📋 문제 아나그램이란 두 문자열이 알파벳의 나열 순서는 다르지만 구성이 일치한 것을 말한다. 예를 들면 AbaAeCe와 baeeACA는 알파벳의 나열 순서는 다르지만 알파벳의 구성은 다음과 같다. AbaAeCe => A(2) a(1) b(1) C(1) e(2) baeeACA => A(2) a(1) b(1) C(1) e(2) 두 문자열의 알파벳과 그 알파벳의 개수가 모두 일치하므로 둘 중 한 문자열을 재배치하면 나머지 하나의 문자열을 만들 수 있다. 길이가 같은 두 개의 문자열이 주어지면 두 문자열이 아나그램인지 판별하여 그 결과를 출력한다. 이때 두 문자열의 대소문자는 구분된다. 👉 입력 첫 번째 줄에 첫 번째 문자열이 입력된다. 두 번째 줄.. 2021. 12. 17.

티스토리툴바