분류 전체보기

[프로그래머스][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..

[BOJ][Java] 1932번 - 정수 삼각형

문제 백준 1932번 문제: 정수 삼각형 문제 설명 각 층의 모든 칸마다 최댓값을 저장하면서 동적 계획법으로 푸는 문제 최대값을 찾기 위해서는 이전 열에서 최대값을 더해 나가야 한다. 문제의 예제로 이해를 해보자 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5맨 위의 수인 7은 제일 상단에 위치해 3과 8에 각각 7을 더해주면 된다. 그럼 10과 15가 되어 밑의 수들에게 선택을 받게 된다. 하지만 셋째줄의 맨 처음에 있는 8과 0은 선택의 여지가 없이 위의 수를 더해야 한다. 1은 10과 15 중 큰 수인 15를 선택할 수 있다. 이를 이용하여 큰 수를 축적해 나갈 수 있다. 아래 축적된 수를 보자. 7 10 15 18 16 15 20 25 20 19 24 30 27 26 24가장 밑에 줄에 가장..

[BOJ][Java] 1149번 - RGB거리

문제 백준 1149번 문제: RGB거리 문제 설명 i번째 집을 각각의 색으로 칠할 때, 1~i번째 집을 모두 칠하는 최소 비용으로 부분문제를 정의해봅시다. 설명 추가 예정 성공 코드 import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner s = new Scanner(System.in); int n = s.nextInt(); int[][] rgb = new int[3][n+1]; for (int i = 0; i < n; i++){ rgb[0][i] = s.nextInt(); rgb[1][i] = s.nextInt(); rgb[2][i] = s.nextInt(); } for (int i = 1; i..

[BOJ][Java] 9461번 - 파도반 수열

문제 백준 9461번 문제 : 파도반 수열 문제 설명 피보나치 수와 비슷한 규칙을 찾아 동적 계획법으로 푸는 문제 파도반 수열은 n에서 두번째 수와 세번째 수를 더하면 n의 값이 나오는 문제이다. 재귀로 풀면 시간 초과로 틀린다. 배열에 차곡차곡 담는 식으로 풀어야 한다. 초기값은 처음 3개의 값인 1로 두면 된다. 성공 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for (int i = 0; i < t; i++) { int n = sc.nextInt(); System.out.print..