목록개발/algorithm (175)
https://www.acmicpc.net/problem/14382 문제 해결 방식 입력값 x가 존재한다고 할 때, x * i (이때 i는 1부터 계속 증가)를 구해나가며, 이 해당 값을 문자값으로 형변환하고 분할하여 set에 추가하는 방식으로 구현했다. 여기서 set은 중복된 원소를 제거하기 때문에, set의 크기가 10인 경우는 곧 0 ~ 9까지의 원소가 모두 등장한 상황이 된다. 이때는 반복문을 중단시켜 가장 마지막에 호출된 x * i 를 정답으로 출력했다. 입력값 x가 0인 경우는 어떤 수를 계속 곱해도 0이라 1 ~ 9까지의 원소가 등장할 수 없기 때문에, 바로 문제에서 제시된 'INSOMNIA'를 출력하면 된다. 전체 소스 코드 const fs = require("fs"); const inpu..
https://www.acmicpc.net/problem/22252 문제 해결 방식 고릴라(상인)의 이름이 모두 영문으로 주어지고, 각 상인에 따라 가진 정보들을 구분할 수 있어야 하기 때문에, 이름에 따라 해싱하는 과정을 먼저 거쳤다. 이후에는 해당 상인이 정보를 얻는 것인지 혹은 호석이가 정보를 구매하는 것인지에 따라 나누어, 정보를 얻는 경우에는 해당 상인의 해싱값에 맞게 최대 힙에 데이터를 적재했다. (호석이는 기본적으로 정보를 구매할 때, 정보의 크기가 큰 순으로 구매하기 때문에 구매 과정에서 이를 효율적으로 하기 위해서는 최대힙으로 구현해야 했다. 이때 node.js는 최대 힙 지원이 되지 않아 구글에서 타인이 구현한 최대 힙 소스 코드를 가져와썼다.) 그리고 만약 정보를 구매하는 경우에는 해..
https://www.acmicpc.net/problem/15702 문제는 각 문제의 배점과 각 사람들의 결과가 주어졌을 때, 가장 높은 점수를 획득한 사람과 그 점수를 구하는 문제다. 문제 해결 방식 각 사람에 따라 획득한 점수를 구한 뒤 만약 해당 점수가 최댓값을 넘는다면, 최댓값과 현재 가장 높은 점수인 수험번호를 갱신하고 해당 점수와 최댓값이 같다면 해당 사람의 수험 번호만 갱신했다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); function solution(dat..
https://www.acmicpc.net/problem/1895 문제 해결 방식 문제에서 주어진 N * M 크기의 이미지를 모두 3 * 3의 크기로 분할한 뒤, 해당 구간에 포함된 모든 원소를 정렬하여 중앙값을 구하고 해당 중앙값이 T보다 크거나 같다면 결괏값에 추가하는 방식으로 로직을 구현하였다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); function solution(data) { const T = +data.pop(); const [[N, M], ...arr] =..
https://www.acmicpc.net/problem/17390 문제에서는 N개의 질문, Q개의 테스트 케이스 갯수, 원소가 숫자로 이루어진 집합, 그리고 합을 구하기 원하는 시작점과 끝점이 주어진다. 문제 접근 방식 문제에서 주어진 내용처럼, 먼저 숫자들이 원소로 주어진 집합을 정렬한 후 각기 테스트케이스에 맞는 합을 구해주면 된다. 다만 이때 테스트케이스가 주어질 때마다 합을 구하기 위해 새로 연산하는 것보다, 각 인덱스까지의 누적값을 해쉬 테이블에 저장한 뒤 활용해주는 방식으로 문제를 해결하는 것이 보다 시간을 절약할 수 있다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux"..
https://www.acmicpc.net/problem/20115 문제 풀이 방식 에너지 드링크의 양을 최대로 하기 위해선 버리는 음료의 양을 최소화하여야 하기 때문에, 양에 따라 오름차순으로 정렬한 뒤, 가장 양이 많은 음료에 합치는 방식으로 구현했다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); function solution(data) { const N = +data[0]; const arr = data[1] .split(" ") .map(Number) .sort((..
https://www.acmicpc.net/problem/1326 해당 문제는 BFS 알고리즘으로 해결할 수 있는 문제다. a가 꼭 b보다 작다는 조건이 없기 때문에, 양쪽 방향으로 모두 이동이 가능하다는 점을 주의하면 된다. 다만 먼저 방문처리를 하지 않으면 queue에 삽입되는 원소가 많아 시간이 오래 걸릴 수 있으므로 queue 삽입 전 방문 처리를 하는 방식으로 처리하는 것이 좋아보여 아래와 같이 로직을 작성했다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); func..
https://www.acmicpc.net/problem/4889 문제 해결 방식 일반적인 스택 문제를 응용하여 해결했다. 먼저 스택에 '{}'이 삽입될 경우, 이는 문자열이 안정된 경우이므로 우선 삭제하여 스택에 쌓이는 원소를 최소화하였다. 이후 스택에 남은 원소들을 변화시키되, 괄호를 변환시키는 횟수를 최소화하여야 하는데, 이때는 스택에 쌓인 원소를 두개씩 짝을지어 삭제시키고 때마다 변환시키는 횟수에 추가했다. 예를 들어, '}{'로 두 원소가 다른 경우는 올바른 문자열로 만들기 위해서 두 원소를 모두 변화시켜야 하므로 2회를 변환 횟수에 추가하고 '}}' 또는 '{{'와 같이 두 원소가 모두 같은 경우는 둘 중 하나만 바꾸어도 올바른 문자열이 되기 때문에 1회 연산을 변환 횟수에 추가했다. 전체 소..