숫자의 표현
📑 문1) Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.
- 1 + 2 + 3 + 4 + 5 = 15
- 4 + 5 + 6 = 15
- 7 + 8 = 15
- 15 = 15
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.
제한사항
n은 10,000 이하의 자연수 입니다.
입출력 예
| n | result |
|---|---|
| 15 | 4 |
나의 풀이
package programmers;
public class RepresentationOfNumbers {
public static int solution(int n) {
int cnt = 0;
for(int i = 1; i <=n; i++) {
int temp = 0;
for(int j = i; j <= n; j++) {
temp +=j;
if(temp == n ) {
cnt++;
break;
}else if(temp > n) {
break;
}
}
}
return cnt;
}
public static void main(String[] args) {
solution(15);
}
}
나의 생각
예를들어,n = 15일 경우 다음과 같이 4가지 방법으로 표현가능하다.
- 1 + 2 + 3 + 4 + 5 = 15
- 4 + 5 + 6 = 15
- 7+ 8 = 15
- 15 = 15
임시변수 temp에 안쪽 for문 초기값 i 부터 1씩 증가한 값을 더하는데, 이 값이 매개변수 n과 같으면 cnt를 증가시키고, 해당 반복문을 빠져나간다. 그리고 임시변수 temp가 n보다 큰 수는 의미가 없기때문에 마찬가지로 for문을 빠져나온다. 이렇게하면 n보다 작거나 같은 수의 경우의 수를 모두 구할 수 있다.
다음 큰 숫자
📑 문2) 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.
- 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
- 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
- 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.
예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.
자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.
제한사항
- n은 1,000,000 이하의 자연수 입니다.
입출력 예
| n | result |
|---|---|
| 78 | 83 |
| 15 | 23 |
나의 풀이
package programmers;
public class NextBigNumber {
public static int solution(int n) {
int answer = 0;
int nOneCnt = 0;
String binary = Integer.toBinaryString(n);
for(char c : binary.toCharArray()) {
if(c == '1') {
nOneCnt++;
}
}
int a = n + 1;
int nPlusOneCnt = 0;
while(a > n) {
String s = Integer.toBinaryString(a);
for(char d : s.toCharArray()) {
if(d == '1') {
nPlusOneCnt++;
}
}
if(nOneCnt == nPlusOneCnt) {
answer = a;
break;
}
nPlusOneCnt = 0;
a++;
}
return answer;
}
public static void main(String[] args) {
solution(15);
}
}
나의 생각
해당 조건을 보면 매개변수 n을 2진수로 변환하고 1의 갯수가 몇개인지를 저장한다. 그런다음 n보다 큰 수중에 2진수로 변환했을때 n을 2진수로 변환했을 때의 1의 갯수와, n보다 큰 수를 2진수로 변환했을때 1의 갯수가 같은지를 판별하여, 같으면 해당하는 수의 정수값이 얼마인가를 리턴하는 문제이다.
int nOneCnt = 0;
String binary = Integer.toBinaryString(n);
for(char c : binary.toCharArray()) {
if(c == '1') {
nOneCnt++;
}
}nOneCnt 변수에는 매개변수 n을 2진수로 변환했을 때의 1의 갯수를 저장한다.
int a = n + 1;
int nPlusOneCnt = 0;
while(a > n) {
String s = Integer.toBinaryString(a);
for(char d : s.toCharArray()) {
if(d == '1') {
nPlusOneCnt++;
}
}
if(nOneCnt == nPlusOneCnt) {
answer = a;
break;
}
nPlusOneCnt = 0;
a++;
}해당 로직은 a = n + 1을 while문의 조건으로 놓으면 항상 참(true)가 되고, 위의 1을 찾는 메서드와 동일한 방법으로 1을 검출한뒤, 매개변수 2진수 변환 값의, 1의 갯수와 매개변수보다 큰 수의 2진수 변환 값의, 1의 갯수와 비교하여 그 수가 동일하면 answer = a를 리턴한다.
클린 코드 작성
package programmers;
public class NextBigNumber {
public static int solution(int n) {
int cntOfOnesInN = Integer.bitCount(n);
int nextNum = n + 1;
while(true) {
if(Integer.bitCount(nextNum) == cntOfOnesInN) {
return nextNum;
}
nextNum++;
}
}
public static void main(String[] args) {
solution(15);
}
}
Integer.bitCount() : Java의 Integer 클래스 내에 있는 정적(static) 메서드로 주어진 정수 n의 2진수 표현에서 1의 개수를 반환합니다.
피보나치 수
📑 문3) 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
예를들어
- F(2) = F(0) + F(1) = 0 + 1 = 1
- F(3) = F(1) + F(2) = 1 + 1 = 2
- F(4) = F(2) + F(3) = 1 + 2 = 3
- F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.
2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.
제한사항
- n은 2 이상 100,000 이하인 자연수입니다.
입출력 예
| n | return |
|---|---|
| 3 | 2 |
| 5 | 5 |
나의 풀이
package programmers;
import java.util.ArrayList;
public class FibonacciNumber {
public static int solution(int n) {
ArrayList<Integer> fibonacciList = new ArrayList<>();
fibonacciList.add(0);
fibonacciList.add(1);
for(int i = 2; i <= n; i++) {
int fibonacci = (fibonacciList.get(i - 2) + fibonacciList.get(i - 1)) % 1234567;
fibonacciList.add(fibonacci);
}
return fibonacciList.get(n);
}
public static void main(String[] args) {
solution(25);
}
}
나의 생각
F(0) = 0
F(1) = 1
F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5F(n) = F(n-1) + F(n-2) 가 적용되어야 하기때문에, 리스트에 모든 값을 쉽게 저장할 수 있게 로직을 구현하였다. ArrayList<Integer> fibonacciList에 주어진 F(0) = 0, F(1) = 1을 넣고, 그 뒤로 부터는 매개변수 n과 같아질때까지 반복을 돌려 fibonacci를 구하는 방법을 사용하였다. 예를들어, 매개변수 n = 25일 경우 리스트의 마지막 값으로 값을 추출할 수 있다.
짝지어 제거하기
📑 문4) 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.
예를 들어, 문자열 S = baabaa 라면
b aa baa → bb aa → aa →
의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.
제한사항
- 문자열의 길이 : 1,000,000이하의 자연수
- 문자열은 모두 소문자로 이루어져 있습니다.
입출력 예
| s | result |
|---|---|
| baabaa | 1 |
| cdcd | 0 |
나의 풀이
package programmers;
import java.util.Stack;
public class RemovePairing {
public static int solution(String s) {
Stack<Character> stack = new Stack<>();
for(char c : s.toCharArray()) {
System.out.println(c);
if(!stack.isEmpty() && stack.peek() == c) {
stack.pop();
}else {
stack.push(c);
}
System.out.println(stack);
}
return stack.isEmpty() ? 1 : 0;
}
public static void main(String[] args) {
solution("baabaa");
}
}
카펫
📑 문5) Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
- 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
- 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
- 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
입출력 예
| brown | yellow | return |
|---|---|---|
| 10 | 2 | [4,3] |
| 8 | 1 | [3,3] |
| 24 | 24 | [8,6] |
나의 풀이
잘못된 풀이
package programmers;
import java.util.ArrayList;
import java.util.Arrays;
public class Carpet {
public static int[] solution(int brown, int yellow) {
int[] answer = new int[2];
int total = brown + yellow;
ArrayList<Integer> factors = new ArrayList<>();
for(int i = 1; i <= total; i++) {
if(total % i == 0) {
System.out.println(i);
factors.add(i);
}
}
int width = 0;
int length = 0;
int size = factors.size();
if(size % 2 == 0) {
width = factors.get(size / 2);
length = factors.get((size / 2) - 1);
}else {
width = factors.get(size / 2);
length = total / width ;
}
answer[0] = width;
answer[1] = length;
System.out.println(Arrays.toString(answer));
return answer;
}
public static void main(String[] args) {
solution(18, 6);
}
}나의 생각
매개변수로 주어진 brown과 yellow의 값을 더한 결과를 total이라고 할때, 이 값의 약수를 구해 중간값으로 값을 도출할 수 있을것이라고 판단하여 이에 해당하는 로직을 구성하였다.
하지만, 이 문제에서 요구하는 결과를 얻을수 없었는데, 예를들어, 18,6을 매개변수로 주어진다고 했을때,
24의 약수를 구하면 1,2,3,4,6,8,12,24 이고, 가로와 세로는 6,4가 된다. 하지만 이 경우, brown이 yellow를 모두 감쌀 수 없기 때문에 오답이된다. 따라서, 이 조건에서는 가로 8, 세로 3이 도출되어야 한다.
정답 풀이
package programmers;
public class Carpet {
public static int[] solution(int brown, int yellow) {
int total = brown + yellow;
for(int width = total; width >= 3; width--) {
if(total % width == 0) {
int length = total / width;
int currentBrown = (width * 2) + (length - 2) * 2;
if(currentBrown == brown) {
return new int[] {width, length};
}
}
}
return null;
}
public static void main(String[] args) {
solution(18, 6);
}
}
나의 생각
for(int width = total; width >=3; width--) 를 보면 알 수있듯이 width길이가 최소 3이상이 되어야 yellow길이가 1을 만족하기때문에, 길이가 3이상은 되어야한다.
if(total % width == 0) {
int length = total / width;
위 조건을 만족하는 가로, 세로 길이를 보면 (24,1),(12,2),(8,3)이 만족함을 알 수 있다.
int currentBrown = (width * 2) + (length - 2) * 2;핵심 로직을 보면
- 가로 길이
width
- 가로 방향의 위쪽 테두리
- 가로 방향의 아래쪽 테두리
따라서, 두 테두리를 합치면 갈색 타일은width * 2
- 세로 길이
length
- 세로 방향의 왼쪽 테두리
- 세로 방향의 아래쪽 테두리
하지만, 각 세로 방향 테두리의 맨 위와 맨 아래 타일은 이미 가로 방향 테두리에의 해 포함되었기때문에, 중복을 피하기 위해 각 세로 테두리에서 2개의 타일을 제외해야한다.
따라서, 각 세로 테두리의 갈색 타일 수는 length -2 * 2
먼저 (8,3)을 예를들어 살펴보자.
currentBrown = (8 * 2) + (3 - 2) * 2 = 16 + 2 = 18
