프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr CODE import java.util.*; class Solution { public TreeSet solution(int[] numbers) { TreeSet answer = new TreeSet(); for(int i = 0; i < numbers.length; i++) { for(int j = i+1; j < numbers.length; j++) { answer.add(numbers[i] + numbers[j]); } } return answer; } } HashSet 자료구조를 이용할까 하다가 오름차..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr CODE class Solution { public String solution(String s, int n) { StringBuffer answer = new StringBuffer(); boolean isUpper = false; char alphabet = ' '; int len = 0; for(int i = 0; i < s.length(); i++) { len = n; if(s.charAt(i) == ' ') { answer.append(" "); continue; } else if(Character...

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr CODE import java.util.*; class Solution { public int solution(int[] d, int budget) { int answer = 0; Arrays.sort(d); if(d[0] > budget) return 0; for(int i = 0; i = d[i]) { budget -= d[i]; answer++; } } return answer; } } 이번 문제는 가진 예산에서 '최대한 많은 부서'에게 지원한다는 맥..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr CODE import java.util.*; class Solution { public String solution(String s) { StringBuffer sb = new StringBuffer(); int idx = 0; for(int i = 0; i < s.length(); i++) { if(s.charAt(i) == ' ') { sb.append(" "); idx = 0; continue; } if(idx % 2 == 0) sb.append(Character.toUpperCase(s.charAt(i..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr CODE import java.util.*; class Solution { public int solution(int n) { int answer = 0; StringBuffer sb = new StringBuffer(Integer.toString(n, 3)); sb.reverse(); answer = Integer.parseInt(sb.toString(), 3); return answer; } } 문제 난이도가 쉬운 편이라 설명은 생략! 실행 결과

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr CODE class Solution { public int[] solution(int n, int m) { int[] answer = {0, 0}; answer[0] = gcd(n, m); answer[1] = (n * m) / answer[0]; return answer; } public int gcd(int a, int b) { if(a % b == 0) { return b; } return gcd(b, a%b); } } 유클리드 호제법을 이용해 풀이했다. 실행 결과

백준_12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 슬라이딩 윈도우 슬라이딩 윈도우 알고리즘은 두 개의 포인터로 범위를 지정한 다음, 그 범위를 유지한 채로 이동하며 문제를 해결한다. 예를들면, 슬라이딩 윈도우의 배열이 3인 슬라이딩 윈도우의 첫 번째 for문 범위는 아래와 같다. 그 다음 반복일 때는 슬라이딩 윈도우가 옆으로 이동하여 아래 그림과 같이 범위가 지정된다. 슬라이딩 윈도우의 범위만큼만 탐색을 진행하기 때문에 O(n)의 시간 복잡도로 문제를 해결할 수 있다. 코드..

백준_2018 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 투 포인터 투 포인터의 기초적인 설명은 아래 링크 참고. [백준] 2018_수들의 합5 - JAVA 백준_2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타 devhan.tistory.com 이번 문제도 저번 문제(주몽)와 마찬가지로 정렬을 이용하면 더욱 간단하게 풀 수 있다. 그래서 정렬 후 투 포인터를 ..

백준_1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 투 포인터 투 포인터에 대한 설명은 아래 링크를 참고 [백준] 2018_수들의 합5 - JAVA 백준_2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타 devhan.tistory.com 이 문제는 두 재료의 번호의 합을 구하고 크기를 비교하는 문제라 받..

백준_2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 투 포인터 투 포인터는 말 그대로 2개의 포인터이다. 이 두 개의 포인터를 이용해서 알고리즘의 시간 복잡도를 최적화할 수 있다. 예제에 나온대로 N의 값이 15라 할때 연속된 자연수의 합은 15(자기 자신), 7+8, 4+5+6, 1+2+3+4+5 이렇게 4개이다. 연속된 자연수의 합을 구하는 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수의 범위를 표현한다. 투 포인터의 이동 원칙 sum > N : sum -= s..

나머지 합 이 문제도 구간 합 배열을 이용해야 한다. 구간 합 배열의 설명은 아래 링크로 이동하면 볼 수 있다. [백준] 11659_구간 합 구하기4 - JAVA 구간 합 구간 합은 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 알고리즘이다. 구간 합을 이용하려면 합 배열을 구해야 한다. 합 배열 만들기 S[i] = S[i-1] + A[i] 인덱스 0 1 2 3 A 10 10 10 1 devhan.tistory.com 배열의 연속 구간의 합을 구하려면 (A+B) % C로 구할 수 있다. 예제를 참고해서 풀어보자. 예제의 배열 {1, 2, 3, 1, 2} 중에 2와 3의 값을 대입해 보자. (2+3) % 3은 2이다. 또, 모듈러 연산은 분배법칙이 가능하다. 그러므로 ((2 % 3) + (3 % ..

2차원 배열 구간 합 일단 1차원 배열의 구간 합부터 이해해야한다. [백준] 11659_구간 합 구하기4 - JAVA 구간 합 구간 합은 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 알고리즘이다. 구간 합을 이용하려면 합 배열을 구해야 한다. 합 배열 만들기 S[i] = S[i-1] + A[i] 인덱스 0 1 2 3 A 10 10 10 1 devhan.tistory.com 2차원 배열의 구간 합은 어려운 거 같으면서도 이해하면 쉽다. 일단 문제의 예시로 설명해보자. 위 원본 배열을 A라 하자. 원본 배열의 크기가 +1 된 이유는 구간 합 배열의 크기와 똑같이 만들어주기 위함이다. 이 A의 합 배열(S)을 채워보자. for문의 시작 인덱스는 0이 아닌 1이다. index 계산 시 0부터 시작이면..

구간 합 구간 합은 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 알고리즘이다. 구간 합을 이용하려면 합 배열을 구해야 한다. 합 배열 만들기 S[i] = S[i-1] + A[i] 인덱스 0 1 2 3 A 10 10 10 10 S 10 20 30 40 이런 식으로 합 배열을 만든다. S 배열에 값을 계산해서 저장하는 for문의 변수 초기화는 1부터 시작해야한다. 구간 합 공식 S[j] - S[i-1] 1부터 3까지의 구간 합을 구한다치면 S[3] - S[1-1]이 된다. 40-10 = 30이 된다. A배열의 값이 모두 10이라 뭔가 헷갈릴 수 있으니 다른 배열로도 계산해보자. 인덱스 0 1 2 3 A 10 16 3 49 S 10 26 29 78 위 배열에서도 1부터 3까지의 합을 구해보자. 78..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 숫자로 이루어진 문자열 t와 p가 주어질 때, t에서 p와 길이가 같은 부분문자열 중에서, 이 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 return하는 함수 solution을 완성하세요. 예를 들어, t="3141592"이고 p="271" 인 경우, t의 길이가 3인 부분 문자열은 314, 141, 415, 159, 592입니다. 이 문자열이 나타내는 수 중 271보다 작거나 같은 수는 141, 159 2개 입니다. 제한 사항 1 ≤ p의 길이 ≤ 18 p의 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있..