Problem Solved

[BOJ][Java] 2579번 - 계단 오르기

문제 백준 2579번 문제: 계단 오르기 문제 설명 i번째 계단에 오를 때, 몇 개의 연속한 계단을 올랐는지를 고려하여 부분문제를 정의해봅시다. 성공 코드 import java.util.Scanner; import java.util.stream.IntStream; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int score[] = new int[n+1]; int accu_score[] = new int[n+1]; IntStream.range(1, n+1).forEach(x -> { score[x] = sc.nextInt(); }); s..

[BOJ][Java] 1931번 - 회의실배정

문제 백준 1931번 문제: 회의실배정 문제 설명 가능한 한 많은 구간을 선택하는 문제 일단 그리디 알고리즘은 정해진 기준에서 현재의 가장 최상의 값을 찾아나가는 알고리즘이다. 그럼 회의실배정 문제에서 최상의 값을 찾을 수 있는 기준은 어떻게 잡을 수 있을까? 회의가 끝나는 시간을 최대한 작은 수부터 골라야 한다. 회의 끝나는 시간이 같다면 회의 시작 시간이 작은 수부터 골라야 한다. 성공 코드 import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in..

[BOJ][Java] 11047번 - 동전0

문제 백준 11047번 문제: 동전0 문제 설명 동전의 조건이 특별해서 동적 프로그래밍보다 빠르게 답을 찾을 수 있는 문제 동전의 최소 개수를 찾기 위해서는 큰 수부터 교환될 수 있는지 찾아야 한다. 그래서 입력을 받을 때 n-1번째 인덱스부터 저장시킬 수 있도록 했다. 그래서 50000부터 1까지 루프될 수 있도록 했다. 성공 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int coins[] = new int[n]; for (int i = n-1..

[프로그래머스][Javascript] 문자열 압축

문제 [프로그래머스][Javascript] 문자열 압축 문제 설명 가장 압축이 작게 된 길이 찾기 처음에 너무 복잡하게 나누고 배열에 계속 저장하는 식으로 하다가 계속 값이 제대로 배열에 저장이 안되는 문제가 생겨 테스트케이스를 모두 다 통과하지 못하는 문제가 생겼다. 블로그를 참고해 조금 간단하게 수정했더니 바로 작동하는 코드가 되었다. 참고 블로그 : [javascript] 프로그래머스/문자열 압축 문제.. 문자열을 n의 길이씩 자르는 것도 배열에 저장하는 makeSplit이라는 함수가 있었는데, 배열로 저장하는 과정을 삭제하는 대신 currWord와 nextWord에 자른 값을 그때그때 저장하며 바로 비교할 수 있도록 바꿨다. 그리고 처음에는 count를 저장하는 배열과 중복되지 않은 문자열을 따로..

[LeetCode][Javascript] Easy - Reverse Integer

문제 [LeetCode][Javascript] Easy - Reverse Integer 문제 설명 숫자를 뒤집어서 출력하는 문제. 주의할 점 음수일 경우에는 음수는 유지한 채 숫자만 reverse되어야 한다. reverse했을 때 제일 앞자리가 0이면 0은 생략되어 출력된다. 즉, 타입이 number여야 한다. 결과값 양음수 모두 2의 31승을 넘어가면 0을 출력하게 해야 한다. 문제 자체는 쉬운데 문제를 안읽어서 헤맸다... reverse는 내장함수를 이용해 배열로 바꾸고 reverse한 뒤 다시 합쳐 숫자형으로 바꿔 주면 된다. 성공 코드 const reverse = x => { const MAX_NUMBER = Math.pow(2, 31); const abs_number = Math.abs(x); ..

[프로그래머스][Javascript] 완주하지 못한 선수

문제 프로그래머스 해시 문제 - 완주하지 못한 선수 문제 설명 참가한 선수 : n+1명 완주한 선수 : n명 1. 정렬하기 너무 어렵게 생각해서 휘황찬란한 코드가 되어버린 문제. 하지만 단순 for문이나 foreach문을 쓰게 된다면 시간초과로 효율성 검사를 실패하게 된다. 그래서 생각을 하다가 정렬을 해서 값이 다르면 완주하지 못한 선수가 나오겠다는 생각을 했다. 그런데 시간복잡도 생각을 너무 많이 했더니 정렬을 퀵소트로 했다. 퀵소트 평균 Big o가 O(nlogn) 정도이니 빨라질거라 생각을 했는데, 생각해보니 반복하며 배열 값을 비교할 때는 최악의 경우 O(n)의 복잡도가 나오게 된다. 퀵소트를 쓰나 그냥 소트를 쓰나 최종 복잡도 차이는 없었던 것이다. 참고로 퀵소트는 하나의 리스트를 피벗(piv..