-
[programmers] 머쓱이보다 키 큰 사람 (프로그래머스 java 풀이)
intro : level0 문제라 굉장히 쉽게 풀 수 있다.
프로그래머스 문제링크
문제 설명
머쓱이는 학교에서 키 순으로 줄을 설 때 몇 번째로 서야 하는지 궁금해졌습니다. 머쓱이네 반 친구들의 키가 담긴 정수 배열 array와 머쓱이의 키 height가 매개변수로 주어질 때, 머쓱이보다 키 큰 사람 수를 return 하도록 solution 함수를 완성해보세요.
제한사항
1 ≤ array의 길이 ≤ 100
1 ≤ height ≤ 200
1 ≤ array의 원소 ≤ 200
입출력 예
array
height
result
[149, 180, 192, 170]
167
3
[180, 120, 140]
190
0
입출력 예 설명
입출력 예 #1
149, 180, 192, 170 중 머쓱이보다 키가 큰 사람은 180, 192, 170으로 세 명입니다.
입출력 예 #2
180, 120, 140 중 190보다 큰 수는 없으므로 0명입니다.
문제풀이
class Solution {
public int solution(int[] array, int height) {
// 리턴할 변수 선언
int answer = 0;
// 향상된 for문 실행 (for-each)
for (int i : array) {
// 매개변수로 주어진 height 값보다 큰지 판별
if (i > height) {
// 만약 크다면 +1
answer += 1;
}
}
// 결과값 반환
return answer;
}
}
// 테스트 1 통과 (0.02ms, 81.3MB)
// 테스트 2 통과 (0.01ms, 75.5MB)
// 테스트 3 통과 (0.02ms, 76.5MB)
// 테스트 4 통과 (0.01ms, 72.6MB)
문제 해석
주어진 height 값보다 큰 값을 array 배열안에서 찾아서 개수를 세어 반환하면 되는 문제이다. 단순히 배열을 반복문을 통해 순회하면서 height 보다 큰 값을 if 조건문을 통해 찾으면 된다.
-
[baekjoon] 피보나치 수 5 (백준 10870 java 풀이)
intro : 재귀함수는 싫다. 싫어.
백준 문제링크
문제
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 n번째 피보나치 수를 출력한다.
문제 풀이 (100ms)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력값을 받아서 정수로 변환
int n = Integer.parseInt(br.readLine());
// 재귀함수를 호출하고 return 받음
int result = recursion(n);
// 결과값 출력
System.out.println(result);
// 자원 반납
br.close();
}
// 피보나치 계산을 수행할 재귀함수
public static int recursion(int n) {
// 0과 1은 각자 자기자신의 값을 반환함
if (n <= 1) {
return n;
}
// recursion(10) = recursion(9) + recursion(8) ... 1까지 반복됨
return recursion(n - 1) + recursion(n - 2);
}
}
문제 해석
재귀함수의 기초를 닦을수 있는 문제인거 같다. 난 재귀함수 문제는 반복문으로도 풀수 있어야 한다고 생각해서 아래와같이 재귀함수로도 풀어보고 반복문으로도 풀어봤다. 두개의 풀이방식에는 차이가 있지만 결국에 구하고자하는 결과값은 피보나치 수열의 값을 어떻게 계산할 것인가? 가 포인트가 되는거 같다. 피보나치 수열에서의 중요한 점은 다음과 같은 단계로 나누어 볼 수 있다.
// 각 단계에서 메서드가 종료된게 아님,
// return 문에서 새로운 recursion을 호출할때마다 해당 메서드 결과값 반환을 기다리고 있음
recursion(10) 호출 → recursion(9) + recursion(8) 계산을 기다림
recursion(9) 호출 → recursion(8) + recursion(7) 계산을 기다림
recursion(8) 호출 → recursion(7) + recursion(6) 계산을 기다림
recursion(7) 호출 → recursion(6) + recursion(5) 계산을 기다림
recursion(6) 호출 → recursion(5) + recursion(4) 계산을 기다림
recursion(5) 호출 → recursion(4) + recursion(3) 계산을 기다림
recursion(4) 호출 → recursion(3) + recursion(2) 계산을 기다림
recursion(3) 호출 → recursion(2) + recursion(1) 계산을 기다림
recursion(2) 호출 → 반환: 1 + 0 = 1
recursion(3) 반환 → 1 (recursion(2)) + 1 (recursion(1)) = 2
recursion(4) 반환 → 2 (recursion(3)) + 1 (recursion(2)) = 3
recursion(5) 반환 → 3 (recursion(4)) + 2 (recursion(3)) = 5
recursion(6) 반환 → 5 (recursion(5)) + 3 (recursion(4)) = 8
recursion(7) 반환 → 8 (recursion(6)) + 5 (recursion(5)) = 13
recursion(8) 반환 → 13 (recursion(7)) + 8 (recursion(6)) = 21
recursion(9) 반환 → 21 (recursion(8)) + 13 (recursion(7)) = 34
recursion(10) 반환 → 34 (recursion(9)) + 21 (recursion(8)) = 55
// 각 단계에서 값을 반환하고 차례대로 계산 진행
최종적으로 recursion(10)이 55을 반환
위 단계를 천천히 읽어보면 재귀함수의 호출 시점과 종료 시점에 대해서 알 수 있다.
반복문을 통해 재귀함수 없이 풀이 방법 - 106ms 소요
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 입력값을 받아서 정수로 변환
int input = Integer.parseInt(br.readLine());
// 배열의 크기를 21로 초기화
int[] array = new int[21];
// 인덱스 0번과 1번은 0과 1로 초기화
array[0] = 0;
array[1] = 1;
// 반복문을 통해 피보나치 수열의 각각의 값을 계산
for (int i = 2; i < array.length; i++) {
array[i] = array[i - 1] + array[i - 2];
}
// 입력값으로 받은 찾고자 하는 값에 해당하는 값 append()
sb.append(array[input]);
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
마무리
호출 단계와 메서드 종료 시점을 확인해보니 각 해당 단계에서 중복된 계산 결과가 반복 되는것을 확인 할 수 있었다. (recursion(8)이 recursion(10)와 recursion(9) 에서 각각 한번씩 총 두번 호출 됨) 재귀함수에서는 각 계층에서의 호출이 각각 일어나기에 추적하기 어려웠던 부분인데, 그림으로 그려보고 눈으로 확인해보니 확실하게 알 수 있었던 것 같다. 다음에는 좀 더 최적화된 로직 구현 방법을 적용해 보고 싶다.
-
[baekjoon] 팩토리얼 2 (백준 27433 java 풀이)
intro : 재귀함수는 내가 제일 싫어하는데, 드디어 하기싫은 Chapter 들이 등장하는군.
백준 문제링크
문제
0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N(0 ≤ N ≤ 20)이 주어진다.
출력
첫째 줄에 N!을 출력한다.
문제 풀이 (104ms)
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 재귀함수 factorial 메서드 실행
long result = factorial(Integer.parseInt(br.readLine()));
// 반환된 결과값 append()
sb.append(result);
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
// N! 팩토리얼을 계산할 재귀함수 메서드
// return 타입이 long인 이유는 20!은 int 타입으로 담을 수 있는 크기의 값이 아니다.
public static long factorial(int n) {
// 만약 입력값이 1보다 작다면 1을 return
if (n <= 1) {
return 1;
}
// n * (자기자신의 메서드를 호출한다 (n-1)).
return n * factorial(n - 1);
}
}
문제 해석
드디어 재귀함수 Chapter까지 단계가 올라왔다. 재귀함수는 싫어하는 이유가 3차원적으로 생각하고 로직을 구성해야해서 항상 이 부분이 싫은건데 이번 문제는 그래도 간단하게 구현할 수 있는 문제라서 다행이라고 생각했다.
factorial의 재귀함수 실행순서는 어떻게 되는가 ?
메서드의 재귀함수 호출의 순서는 다음과 같다. 만약 10!의 값을 게산한다면 다음과같은 과정을 거쳐서 결과값을 도출하게 된다. return 문에서 계속해서 자기자신의 메서드를 (n -1)을 한 값으로 호출하게 되는데 n이 1이 되는 시점에서 모든 메서드의 return문이 실행되면서 계산이 마무리 된다.
// 각 단계에서 메서드가 종료된게 아님,
// return 문에서 새로운 factorial을 호출할때마다 해당 메서드 결과값 반환을 기다리고 있음
factorial(10) 호출 -> 10 * factorial(9)
factorial(9) 호출 -> 9 * factorial(8)
factorial(8) 호출 -> 8 * factorial(7)
factorial(7) 호출 -> 7 * factorial(6)
factorial(6) 호출 -> 6 * factorial(5)
factorial(5) 호출 -> 5 * factorial(4)
factorial(4) 호출 -> 4 * factorial(3)
factorial(3) 호출 -> 3 * factorial(2)
factorial(2) 호출 -> 2 * factorial(1)
factorial(1) 호출 -> 종료 조건에 의해 1 반환
// 각 단계에서 값을 반환하고 차례대로 계산 진행
최종적으로 factorial(10)이 3628800을 반환
재귀 함수로 풀지않아도 풀 수 있는 문제이기는 하다.
팩토리얼 문제처럼 while문을 통해서도 충분히 풀 수 있다, 아니면 아래처럼 배열로도 충분히 풀 수 있는 문제이기는 하다. 하기 코드는 팩토리얼의 특성을 이용해서 푼 코드인데, factorial(2) = 2 * factorial(1), factorial(3) = 3 * factorial(2), factorial(4) = 4 * factorial(3), factorial(5) = 5 * factorial(4)… 위와같은 과정을 배열로 구현한 것이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
// 입력을 위한 BufferedReader 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 0 부터 20까지 인덱스가 필요하기에 21개로 배열설정
long[] array = new long[21];
// 팩토리얼은 0과 1은 1값임
array[0] = array[1] = 1;
// 팩토리얼의 특징을 이용해서 배열 인덱스마다 팩토리얼 결과값을 할당
for (int i = 2; i < 21; i++) array[i] = i * array[i - 1];
// 결과값 출력
System.out.println(array[Integer.parseInt(br.readLine())]);
// 자원 반납
br.close();
}
}
마무리
재귀함수 Chapter 이지만 재귀험수로 풀고싶지가 않다. 그냥 디버깅도 쉽고 직관적으로 반복문으로 풀면 안되나. 다음에 푸는 재귀함수 문제에서는 재귀함수를 꼭 써야지만 얻을 수 있는 메리트가 있는지 확인해 보고싶다. 이번 문제에서는 속도차이도 없고 더 나은점을 모르겠다.
-
[baekjoon] 좌표 압축 (백준 18870 java 풀이)
intro : 간만에 문제에서 뭘 원하는지 모르겠는 문제가 나왔다.
백준 문제링크
문제
수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자.
입력
첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, …, XN이 주어진다.
출력
첫째 줄에 X’1, X’2, …, X’N을 공백 한 칸으로 구분해서 출력한다.
문제 풀이 (1772ms)
import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 입력값의 개수
int forCount = Integer.parseInt(br.readLine());
// 원데이터를 저장할 배열 변수
int[] originalArray = new int[forCount];
// 정렬데이터를 저장할 배열 변수
int[] sortArray = new int[forCount];
// 입력값을 공백기준으로 나누기 위한 StringTokenizer 객체 생성
StringTokenizer st = new StringTokenizer(br.readLine());
// 반복문을 통해 originalArray, sortArray에 데이터 할당
for (int i = 0; i < forCount; i++) {
String line = st.nextToken();
originalArray[i] = Integer.parseInt(line);
sortArray[i] = Integer.parseInt(line);
}
// 배열 오름차순으로 정렬
Arrays.sort(sortArray);
int index = 0;
// Map<정렬데이터, index(순서)> 로 저장하기 위한 map 변수 선언
Map<Integer, Integer> map = new HashMap<>();
for (int value : sortArray) {
// 중복된 데이터인 경우는 거르기 위함
if (!map.containsKey(value)) {
map.put(value, index);
index++;
}
}
// 원데이터를 몇번째 인덱스에 해당하는지 map 에서 찾기
for (int ori : originalArray) {
// sb.append() 메서드를 통해 저장
sb.append(map.get(ori)).append(" ");
}
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
문제 해석
간만에 문제 자체만으로 무슨말인지 도저히 모르겠는 문제가 나왔다. 가끔 이런 문제를 보면 문제를 너무 성의없이 내는게 아닌가 싶을때가 있는데, 딱 이런문제가 그런 문제다. 정확히 무엇을 원하는지가 명확하지가 않다. 입력예제랑 출력을 보고 문제에서 원하는 바를 추측해 보았다.
[입력 예제 1]
5
2 4 -10 4 -9
------------------
[예제 출력 1]
2 3 0 3 1
------------------
[입력 예제 1 정렬 (오름차순)]
-10(0), -9(1), 2(2), 4(3), 4(4)
문제 추측
딱 위 내용을 보니까 대충 문제에서 원하는 바가 정렬한 값이 원래 값에 맞춰서 인덱스 값을 추출하는걸 원하는 거구나 싶었다. 다만 중복된 값을 하나의 인덱스만을 가지는거 같았다, 입력예제 1번에서의 4는 두번등장하는데 출력된 결과를 보면 3이 2번 출력된다. 만약 중복을 포함하는거라면 3,4 로 값이 나왔을거 같은데 그게 아닌거보니 중복을 제거해서 인덱스를 계산해야한다는 점을 알 수 있다.
(과연 이런식으로 추측해서 문제를 푸는게 맞나싶은데, 정말이지 이 문제는 문제 텍스트가 너무 성의가 없는거 같다.)
구현 방향
이 문제의 핵심은 주어진 좌표들을 압축하여 정수 인덱스로 변환하는 것 같았다. 이해한 내용을 기반으로 좌표 간의 상대적 크기를 반영하여 배열을 생성하였고 원데이터와, 정렬한 데이터를 두개로 나누어 관리하였다. 그후에 정렬한 데이터를 map 변수에 저장을 하는데, 이때 중복된 데이터를 저장하지 않기 위해 검증로직을 추가하였다. containsKey 메서드는 시간복잡도가 1이라 빨라서 나는 자주 애용한다.
그 이후 원데이터를 반복문을 돌면서 원데이터의 값을 map에서 꺼낸다, Hash값이기 떄문에 이 또한 시간 복잡도는 1이라 빠르게 값을 찾아서 StringBuilder에 값을 추가할 수 있다.
마무리
문제 자체를 정확히 이해하지 못하고 풀어서 뭔가 다양한 관점으로 보기 어려웠던게 좀 많이 아쉽다. 그리고 시간이 굉장히 오래걸리길래 다른 분들 풀이 시간을 확인해보았는데, 다들 1초 ~ 2초 사이를 소요하고 있으신거 같았다. 이 문제 특성상 입력값이 크게주어져서 시간이 굉장히 오래 소요 되는 것 같았다.
-
[baekjoon] 나이순 정렬 (백준 10814 java 풀이)
intro : static 내부 class를 통해 문제를 풀어보자
백준 문제링크
문제
온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.
출력
첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.
문제 풀이 (548ms)
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 입력값의 개수
int forCount = Integer.parseInt(br.readLine());
// Member 배열 선언
Member[] members = new Member[forCount];
// 반복문을 통해 Member 객체를 배열로 저장
for (int i = 0; i < forCount; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
// 이때 가입한 순서를 i로 Member 클래스의 index 값을 저장
members[i] = new Member(Integer.parseInt(st.nextToken()), st.nextToken(), i);
}
// 배열 정렬
Arrays.sort(members, (o1, o2) -> {
// 나이값을 기준으로 오름차순 정렬
if (o1.age != o2.age) {
return o1.age - o2.age;
} else {
// 나이값이 같다면 가입한 순서로 오름차순 정렬
return o1.index - o2.index;
}
});
// 정렬된 members 데이터 sb.append() 메서드를 통해 저장
for (Member member : members) {
sb.append(member.age).append(" ").append(member.name).append("\n");
}
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
// Member 클래스 생성
// static 으로 생성하는 이유는 내부 클래스는 static 으로 생성해야
// 메모리 관점에서 효율적으로 관리할 수 있고, 누수를 막을 수 있다.
static class Member {
int age; // 나이
String name; // 이름
int index; // 가입 순서
// 생성자를 통한 객체 생성
public Member(int age, String name, int index) {
this.age = age;
this.name = name;
this.index = index;
}
}
}
문제 해석
이 문제는 기존에 풀던 정렬문제랑 크게 차이가 없었는데 관리해야하는 값의 개수가 2개에서 3개로 늘어남에 따라 어떻게 처리하는게 좋을지 생각하다가 배열을 통해 관리를 하는게 어떨지 생각하고 다음과 같이 문제를 풀어보았었다.
856ms 소요
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 입력값의 개수
int forCount = Integer.parseInt(br.readLine());
// 나이, 이름, 가입순서를 저장할 배열 선언
String[][] array = new String[forCount][3];
// 반복문을 통해 array 데이터 저장
for (int i = 0; i < forCount; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
array[i][0] = st.nextToken();
array[i][1] = st.nextToken();
array[i][2] = Integer.toString(i);
}
// 배열 정렬
Arrays.sort(array, (o1, o2) -> {
// 나이값을 기준으로 오름차순 정렬
if (!o1[0].equals(o2[0])) {
return Integer.parseInt(o1[0]) - Integer.parseInt(o2[0]);
} else {
// 나이값이 같다면 가입한 순서로 오름차순 정렬
return Integer.parseInt(o1[2]) - Integer.parseInt(o2[2]);
}
});
// 정렬된 array 데이터 sb.append() 메서드를 통해 저장
for (String[] arr : array) {
sb.append(arr[0]).append(" ").append(arr[1]).append("\n");
}
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
static class를 사용하게된 이유
근데 위와같이 풀고나니까, 정렬하는 부분에서 각 값을 자꾸 형변환을 해줘야하는게 너무 신경이 쓰였다. 뭐 이대로 풀어도 정답처리되는 코드이지만 뭔가 석연치않는 부분이 남는거 같다는 생각이 들었다. 아무래도 정수형 데이터와 문자열 데이터를 같이 관리해야하다보니, 다른 자료구조를 사용하는게 좋을거 같다는 생각이 들었는데, 객체를 통해 자료구조를 만들어 보는게 어떨까? 라는 생각이 들었다.
static class를 사용하면서 얻게 되는 이점
가장 큰 이점은 형변환을 하지 않아도 되는점이다. 아무래도 정렬 로직에서 각 값을 계속해서 Integer.parseInt를 하는게 시간복잡도 관점에서 크게 영향을 미치기도하고, 배열을 통해 3개의 데이터를 0,1,2 번 인덱스에 값을(나이,이름,가입순서) 할당하는게 누군가 보았을때 유지보수 관점에서도 크게 좋지 않는데 내부 클래스를 이용해서 객체로 관리하니 유연성 및 확장성 에서도 이점을 가져올수 있고 가독성 부분에서도 굉장히 쉽게 읽히는 부분이 생긴다.
마무리
처음으로 알고리즘 문제에서 객체를 활용해 문제를 풀어봤는데, 다음에도 혹시 관리포인트가 늘어나는 자료구조가 필요하다면 기존에 자바에서 제공해주는 자료구조 및 객체도 고민거리에 포함해서 생각해 보아야 겠다고 생각이 들었다.
-
[baekjoon] 단어 정렬 (백준 1181 java 풀이)
intro : TreeSet을 사용하면, 중복제거 및 정렬 기능을 동시에 이점을 가져올 수 있다.
백준 문제링크
문제
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.길이가 짧은 것부터 길이가 같으면 사전 순으로 단, 중복된 단어는 하나만 남기고 제거해야 한다.
입력
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
출력
조건에 따라 정렬하여 단어들을 출력한다.
문제 풀이 (308ms)
import java.io.*;
import java.util.Set;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 입력값의 개수
int forCount = Integer.parseInt(br.readLine());
// 중복 제거를 위한 Set 변수 선언
// TreeSet 의 특징은 중복을 제거하고, 정렬기능을 제공한다.
// 또한 특정 정렬 기준을 적용한 TreeSet 을 설정할 수 있다.
Set<String> set = new TreeSet<>((o1, o2) -> {
// 문자길이가 짧은게 앞에오도록 오름차순 정렬
if (o1.length() != o2.length()) {
return o1.length() - o2.length();
} else {
// 문자길이가 같을때, 사전순으로 정렬될 수 있도록 정렬
return o1.compareTo(o2);
}
});
// 입력값을 set 변수에 저장
for (int i = 0; i < forCount; i++) set.add(br.readLine());
// 정렬된 set 데이터 sb.append() 메서드를 통해 저장
for (String str : set) sb.append(str).append("\n");
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
문제 해석
정렬하는 문제를 좀 풀어봤다 싶지만, TreeSet을 통해 푸는 방법이 굉장히 좋은거 같다. 중복제거를 해줌과 동시에 정렬기준또한 변수 선언시에 정할 수 있다. 처음에는 위 방식으로 코드를 작성했던 것이 아닌 아래 코드처럼 List를 통한 정렬을 했었다.
328ms 소요
import java.io.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 입력값의 개수
int forCount = Integer.parseInt(br.readLine());
// 중복 제거를 위한 Set 변수 선언
Set<String> set = new HashSet<>();
for (int i = 0; i < forCount; i++) {
set.add(br.readLine());
}
// 정렬하기 위한 List 변수 선언 (Set 을 통해 생성)
List<String> list = new ArrayList<>(set);
// 정렬 진행
list.sort((o1, o2) -> {
// 문자열 길이기준으로 오름차순 정렬 (짧으면 앞으로 옴)
if (o1.length() != o2.length()) {
return o1.length() - o2.length();
} else {
// 길이가 같으면 사전순으로 정렬
return o1.compareTo(o2);
}
});
// 반복문을 통해 sb.append() 메서드 호출
for (String str : list) {
sb.append(str).append("\n");
}
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
기존에도 많이 사용하던 방법이라, 이질감 없이 코드를 작성하고 문제를 풀어냈는데, 중복을 제거하고 정렬하는 부분이 다른 자료구조를 사용하면 더 편하게 처리할 수 있을거 같다는 생각이 들어서 찬찬히 생각해보니, TreeSet 자료구조가 있었다.
왜 TreeSet을 사용하는가 ?
TreeSet은 다음과 같은 특징이 있다. 중복을 제거하며, 정렬한 데이터를 제공해준다. 추가적으로 정렬을 하는 기준을 내가 커스터마이징하여 지정할 수 있다. 비슷한 자료구조 중에 PriorityQueue에도 정렬기능을 커스터마이징 하는게 있는데 TreeSet 또한 그렇다.
TreeSet을 사용하면서 얻는 이점
TreeSet을 사용하니 기존에 코드에서 다음과 같은 이점이 생긴다. Set에서 List로 변환할 필요가 없다. List를 통해 따로 Sort() 메서드를 호출할 필요가 없다. 또한 코드가 간결해지며 직관적으로 작성된다.
마무리
문제에 따라 사용하는 자료구조에 따라, 수행시간과 코드 가독성에도 큰 영향을 미치는게 위 문제를 통해 많이 느껴진다.
-
[baekjoon] 좌표 정렬하기 2 (백준 11651 java 풀이)
intro : 좌표 정렬하기 문제 방금풀었는데, 그 문제랑 다른건 x,y 정렬 기준 뿐이다.
백준 문제링크
문제
2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.
출력
첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.
문제 풀이 (596ms)
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 입력값의 개수
int forCount = Integer.parseInt(br.readLine());
// 좌표값을 저장할 2차원 배열 선언
int[][] array = new int[forCount][2];
// 빈복문을 통해 2차원 배열에 데이터 저장
for (int i = 0; i < forCount; i++) {
// 입력값을 공백 기준으로 데이터를 자르기 위한 StringTokenizer 객체 생성
StringTokenizer st = new StringTokenizer(br.readLine());
array[i][0] = Integer.parseInt(st.nextToken());
array[i][1] = Integer.parseInt(st.nextToken());
}
// 배열 정렬
Arrays.sort(array, (o1, o2) -> {
// y값이 다르다면 y값을 기준으로 오름차순 정렬
if (o1[1] != o2[1]) {
return o1[1] - o2[1];
} else {
// y값이 같다면 x값을 기준으로 오름차순 정렬
return o1[0] - o2[0];
}
});
// 정렬된 2차원 배열 데이터 sb.append() 메서드를 통해 저장
for (int[] arr : array) {
sb.append(arr[0])
.append(" ")
.append(arr[1])
.append("\n");
}
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
문제 해석
이 문제는 좌표 정렬하기 문제와 정렬기준이 반대인거 말고는 차이가 1도 없다. 정렬기준이 반대라는 점은 이전 좌표정렬하기 문제에서는 x값 기준으로 먼저 정렬하고 x값이 같다면 y값을 기준으로 오름차순 정렬을 하였는데, 이번 문제는 y값 기준으로 먼저 정렬하고 y값이 같다면 x값 기준으로 오름차순 정렬을 하는것으로 차이가 있다.
중요로직 (정렬)
아래로직은 2차원 배열을 y값을 기준으로 오름차순 정렬하고, y값이 같다면 x값을 기준으로 정렬하는 코드이다. 아래 코드가 이 문제를 푸는 키 포인트 이다.
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
...
...
// 배열 정렬
Arrays.sort(array, (o1, o2) -> {
// y값이 다르다면 y값을 기준으로 오름차순 정렬
if (o1[1] != o2[1]) {
return o1[1] - o2[1];
} else {
// y값이 같다면 x값을 기준으로 오름차순 정렬
return o1[0] - o2[0];
}
});
...
...
}
}
-
[baekjoon] 좌표 정렬하기 (백준 11650 java 풀이)
intro : List를 통해서도 풀 수 있지만 값의 범위가 지정되어 있으니 2차원 배열로도 풀 수 있다.
백준 문제링크
문제
2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.
출력
첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.
문제 풀이 (640ms)
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 입력값의 개수
int forCount = Integer.parseInt(br.readLine());
// 좌표값을 저장할 2차원 배열 선언
int[][] inputArray = new int[forCount][2];
// 빈복문을 통해 2차원 배열에 데이터 저장
for (int i = 0; i < forCount; i++) {
// 입력값을 공백 기준으로 데이터를 자르기 위한 StringTokenizer 객체 생성
StringTokenizer st = new StringTokenizer(br.readLine());
inputArray[i][0] = Integer.parseInt(st.nextToken());
inputArray[i][1] = Integer.parseInt(st.nextToken());
}
// 배열 정렬
Arrays.sort(inputArray, (o1, o2) -> {
if (o1[0] != o2[0]) {
// x값이 다르다면 x값을 기준으로 오름차순 정렬
return o1[0] - o2[0];
} else {
// x값이 같다면 y값을 기준으로 오름차순 정렬
return o1[1] - o2[1];
}
});
// 정렬된 2차원 배열 데이터 sb.append() 메서드를 통해 저장
for (int[] arr : inputArray) {
sb.append(arr[0])
.append(" ")
.append(arr[1])
.append("\n");
}
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
문제 해석
이 문제를 풀기전에 다른 비슷한 정렬 문제를 하나 풀어보니까 이제는 이런 문제나오면 반갑다.. 혹시 그 문제가 무엇인지 궁금하다면 영단어 암기는 괴로워 를 풀어보는걸 추천한다. 이문제랑 결이 비슷하면서도 조금 더 ? 어주 살짝 더 어려운 문제인거 같다.
문제 해석 방향
이 문제는 정렬의 조건이 오름차순으로 정렬해야 하는것으로 굉장히 명확하다, x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬 이라는 조건이 문제에서 주어지는데, 그렇다면 해당 정렬을 하기 위해 어떤 자료구조를 사용할지 선택만하면 된다. 초기에는 2차원 배열을 통해 데이터를 관리했던것은 아니고, List를 통해 데이터를 관리했는데, 다음과 같이 코드를 작성하여 문제를 풀었었다.
620ms 소요
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 좌표값을 저장할 리스트 선언 (타입은 1차원 배열)
List<int[]> list = new ArrayList<>();
// 입력값의 개수
int forCount = Integer.parseInt(br.readLine());
// 빈복문을 통해 리스트에 데이터 저장
for (int i = 0; i < forCount; i++) {
// 입력값을 공백 기준으로 데이터를 자르기 위한 StringTokenizer 객체 생성
StringTokenizer st = new StringTokenizer(br.readLine());
// 리스트에 저장할 1차원 배열 객체 생성
int[] tempArray = new int[2];
tempArray[0] = Integer.parseInt(st.nextToken());
tempArray[1] = Integer.parseInt(st.nextToken());
list.add(tempArray);
}
// 리스트 정렬
list.sort((o1, o2) -> {
if (o1[0] != o2[0]) {
// x값이 다르다면 x값을 기준으로 오름차순 정렬
return o1[0] - o2[0];
} else {
// x값이 같다면 y값을 기준으로 오름차순 정렬
return o1[1] - o2[1];
}
});
// 정렬된 리스트 sb.append() 메서드를 통해 저장
for (int[] intArray : list) {
sb.append(intArray[0])
.append(" ")
.append(intArray[1])
.append("\n");
}
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
List 타입으로 문제 잘 풀어놓고 왜 배열로 리팩토링을 하였는가 ?
항상 알고리즘 문제를 풀때 다양한 관점으로 문제를 풀어보려 하는데, 해당 문제는 배열로 풀 수 있는 가능성이 있었다. 그 이유는 입력값으로 정확히 배열의 사이즈를 지정할 수 있는 개수를 초기에 지정해주기에 배열로 선언해서 사이즈를 지정할 수 있었고, 해당 문제의 시간복잡도는 배열의 정렬을 어떻게 하는냐에 따라서 시간적으로 차이가 많이 날 것이라고 생각했다. 왜냐하면, Arrays.sort()는 List.sort()보다 이론적으로 빠르게 작동하기에 당연히 배열을 통해 문제를 푸는게 더 나을거라고 생각했다.
Arrays.sort()가 List.sort()보다 왜 더 빠르게 작동하는가 ?
보통 성능적으로 크게 차이가 나지 않을거라고 생각하지만 입력값의 크기가 커지면 커질수록 성능의 차이는 더 커진다. 그 이유는 List.sort()는 내부적으로 컬렉션을 배열로 변환하는 과정을 거친다. 그 이후 배열의 대한 정렬(Arrays.sort())를 진행하고 다시 List로 변환한다. 해당 과정을 거치는 이유 때문에 Arrays.sort()가 보다 더 빠르게 동작한다. (동작 단계로만 따져봐도 누가 더 빠르게 동작할지 알 수 있다.)
그래서 두개의 코드 실행 시간은 차이가 얼마인가 ?
이론적으로는 2차원 배열로 푸는것이 빠르다고 생각했는데 실제로는 리스트가 더 빨랐다. 여러번 실행해보니 거의 속도적인 차이는 없었는데, 그 이유는 문제에서 주어진 입력값의 개수가 크지않기에 속도적인 차이가 나지않았다. 아무래도 100,000개의 데이터를 처리하는 코드에 있어서는 큰 차이를 볼수없고, 몇백만개정도는 되어야 두개의 자료구조를 통한 풀이가 속도 차이가 있을 것 같다.
혹시 정렬코드 return o1 - o2 가 이해가 안된다면?
다른 방식으로도 정렬기준을 정할 수 있다. 다음과 같이 코드를 작성할 수 도 있고 사실상 해당 문제에 한해서는 속도적인 차이가 거의 나지를 않으니 본인 코드 스타일에 맞게 선택 하면 될 것 같다.
616ms 소요
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 좌표값을 저장할 리스트 선언 (타입은 1차원 배열)
List<int[]> list = new ArrayList<>();
// 입력값의 개수
int forCount = Integer.parseInt(br.readLine());
// 빈복문을 통해 리스트에 데이터 저장
for (int i = 0; i < forCount; i++) {
// 입력값을 공백 기준으로 데이터를 자르기 위한 StringTokenizer 객체 생성
StringTokenizer st = new StringTokenizer(br.readLine());
// 리스트에 저장할 1차원 배열 객체 생성
int[] tempArray = new int[2];
tempArray[0] = Integer.parseInt(st.nextToken());
tempArray[1] = Integer.parseInt(st.nextToken());
list.add(tempArray);
}
// 리스트 정렬
list.sort((o1, o2) -> {
// x 값 기준으로의 오름차순 정렬
if (o1[0] < o2[0]) {
return -1;
} else if (o1[0] == o2[0]) {
// x 값이 같다면 y값 기준으로의 오름차순 정렬
if (o1[1] < o2[1]) {
return -1;
} else if (o1[1] == o2[1]) {
return 0;
} else {
return 1;
}
} else {
return 1;
}
});
// 정렬된 리스트 sb.append() 메서드를 통해 저장
for (int[] intArray : list) {
sb.append(intArray[0])
.append(" ")
.append(intArray[1])
.append("\n");
}
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
마무리
왜 리팩토링을 하면 할수록 속도가 더 느려지는지는 의문이지만(미비하게나마 느려진다), 분명히 이론적으로는 Arrays.sort()가 빠르다고했는데… 그냥 직관적으로 단순하게 풀어버릴걸 그랬나 싶기도 하지만 다양하게 테스트 해보고 왜 빠르고 느린지에 대해서 스스로 탐구하고 이해하는 과정이 나에게 큰 도움이 되었던 것 같다.
-
[baekjoon] 영단어 암기는 괴로워 (백준 20920 java 풀이)
intro : 정렬은 항상 고려할게 많아서 어렵다. 정렬 방법과 종류도 너무많고.. 따로 내용을 정리할 Chapter가 필요할정도다.
백준 문제링크
문제
화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.자주 나오는 단어일수록 앞에 배치한다. 해당 단어의 길이가 길수록 앞에 배치한다. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다. M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자.
입력
첫째 줄에는 영어 지문에 나오는 단어의 개수 N과 외울 단어의 길이 기준이 되는 M이 공백으로 구분되어 주어진다. (1 <= N <= 100,000, 1 <= M <= 10) 둘째 줄부터 N+1번째 줄까지 외울 단어를 입력받는다. 이때의 입력은 알파벳 소문자로만 주어지며 단어의 길이는 10을 넘지 않는다. 단어장에 단어가 반드시 1개 이상 존재하는 입력만 주어진다.
출력
화은이의 단어장에 들어 있는 단어를 단어장의 앞에 위치한 단어부터 한 줄에 한 단어씩 순서대로 출력한다.
문제 풀이 (700ms)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 공백을 기준으로 자르기 위한 StringTokenizer 객체 사용
StringTokenizer st = new StringTokenizer(br.readLine());
// 입력값의 개수
int forCount = Integer.parseInt(st.nextToken());
// 입력받아야 하는 단어의 길이 최소값
int minLength = Integer.parseInt(st.nextToken());
// 최빈값을 보관하기 위한 자료구조 Map 사용
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < forCount; i++) {
String input = br.readLine();
// 최소 길이 이상의 단어만 빈도수를 증가시키며 map 변수에 담음
if (input.length() >= minLength) {
map.put(input, map.getOrDefault(input, 0) + 1);
}
}
// 출력값은 중복을 제거한 단어의 값이기에, map 의 키값을 통해 정렬진행
List<String> list = new ArrayList<>(map.keySet());
list.sort((o1, o2) -> {
Integer first = map.get(o1);
Integer second = map.get(o2);
// 자주 나오는 단어일수록 앞에 배치한다.
if (!Objects.equals(first, second)) {
// 앞에 배치한다는 말은 내림차순 정렬을 한다는 말과 같음
// 만약 return first - second 인 경우는 오름차순 정렬과 같음
return second - first;
}
// 해당 단어의 길이가 길수록 앞에 배치한다.
if (o1.length() != o2.length()) {
// 위 주석과 같은 의미를 가지고 있음
return o2.length() - o1.length();
}
// 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다
// String은 Comparable 인터페이스를 구현하고 있음
// 제공되는 사전순 정렬 메서드 compareTo를 사용가능
return o1.compareTo(o2);
});
// 정렬된 key 값을 StringBuilder 에 저장
for (String l : list) {
sb.append(l).append("\n");
}
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
문제 해석
정렬문제는 항상 손이 많이가는 편인데, 해당 문제는 사용자 정의 정렬을 구현할수 있냐를 물어보는 문제인거 같다는 생각이 들었다. 문제에서 직관적으로 정렬 조건을 명확하게 주어졌는데, 자주 나오는 단어일수록 앞에 배치, 해당 단어의 길이가 길수록 앞에 배치, 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치. 결국 이 세가지 정렬 조건을 코드로 구현할 수 있냐를 물어보는 것이다. 너무 별거 아닌거라서 가장 첫번째 조건을 누락할뻔했는데 M이상인 단어들만 외운다 까지 포함해야한다.
부가 조건
주어지는 M 이상의 단어만 입력값으로 받아야함.
정렬 조건 정리
자주 나오는 단어일수록 앞에 배치 : 빈도수를 계산해서 내림차순 정렬을 진행해야한다.
해당 단어의 길이가 길수록 앞에 배치 : 단어의 길이를 계산해서 내림차순 정렬을 진행해야한다.
알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치 : String Class의 CompareTo를 사용하자.
Map을 사용한 이유
첫번째 정렬조건인 자주 나오는 단어일수록 앞에 배치의 말 뜻은 빈도수를 계산 해야한다는 말이다. 여기서 빈도수는 단어가 입려값으로 몇번이나 나오는가? 를 물어보는것과 같다. 그렇다면 다양한 자료구조를 통해서 빈도수를 계산할 수 있는데, 출력값 예제를 확인해보면 중복된 값은 출력하지 않고 있다. 왜냐하면 외워야하는 단어를 목록을 만들어서 출력하는것이기에 중복된 단어를 포함할 이유가 없다. 또한 두번째 정렬 기준인 단어의 길이를 가지고 정렬조건을 사용하기 위해선 어떤 단어인지를 알아야하는데 Map<단어, 빈도수> 로 변수를 구성해서 관리하면 쉽게 정렬에서 연산과정을 수행할수 있다. 이하동문으로 알파벳 사전순으로 정렬하기도 2번째 조건에서 연산하는것과 같이 Map의 키값에 CompareTo 메서드를 사용하면 되기에 이 문제에서 Map이 적합한 자료구조 타입이라고 생각이 들었다.
정렬 로직에서 return second - first 와 같은 맥락을 사용한 이유 (자주 나오는 단어, 단어의 길이를 앞에 배치할때 사용한 기준)
보통 사용자 정의 정렬 로직을 구현하는 코드를 찾아보면 다음과 같은 코드 로직을 자주 볼 수 있다. 만약 문자열 길이를 기준으로 오름차순으로 정렬해야한다, 라는 문제가 있다면 다음과 같이 정렬하는 로직을 자주 보곤 한다.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
String[] array = {"a", "b", "c", "ab", "abc", "abed", "addon"};
// 아래 정렬 기준과 return 값을 집중해보자
Arrays.sort(array, (o1, o2) -> {
if (o1.length() < o2.length()) {
return -1;
} else if (o1.length() > o2.length()) {
return 1;
} else {
return 0;
}
});
// 배열을 한번에 출력하기 위해 Arrays.toString 메서드 사용
System.out.println(Arrays.toString(array));
}
}
// 출력값
// [a, b, c, ab, abc, abed, addon]
위처럼 if문 조건을 통해 첫번째 값과 두번째값의 비교를 통해 어떤값을 return하는가? -1,0,1 에 따라 정렬이 달라진다. 만약 위처럼 오름차순이 아니라 내림차순으로 정렬해야한다면 아래와 같이 return값이 반대로만 적용되면 된다.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
String[] array = {"a", "b", "c", "ab", "abc", "abed", "addon"};
// 아래 정렬 기준과 return 값을 집중해보자
Arrays.sort(array, (o1, o2) -> {
if (o1.length() < o2.length()) {
return 1;
} else if (o1.length() > o2.length()) {
return -1;
} else {
return 0;
}
});
// 배열을 한번에 출력하기 위해 Arrays.toString 메서드 사용
System.out.println(Arrays.toString(array));
}
}
// 출력값
// [addon, abed, abc, ab, a, b, c]
두개의 차이는 같은 조건이면서도 return 되는값이 -1이냐 0이냐 1이냐에 따라서 정렬이 다르게 적용된다는 것이다. 그말은 다르게 풀이해보자면 return 값은 그저 정렬 알고리즘이 두 값을 비교해 위치를 교환하거나 유지하는지 결정하는데 사용하는 기준 값일 뿐이고 실제로는 음수인 값인지 정수인 값인지만 알면 된다는것이다. 이 말을 이해 했다는 가정하에 다시 return second - first; 에 대해서 확인해보면 만약 second 값이 100인데, first가 50 이라면 양수의 값이 return 된다. 그때 second 값이 앞으로 이동하는데 그 이유는 o1, o2에 대한 비교를 진행시에 만약 first - second를 했고 결과값이 양수라면 first가 뒤로 이동하는게 맞는데, 이건 오름차순 정렬일때 해당하는 말이고, 우리는 출력을 내림차순으로 해야하기에 과정을 반대로 뒤집어서 return second - first; 를 이용해야 우리가 원하는 반대의 결과 즉 내림차순 정렬을 할 수 있음을 알 수 있다.
Integer 클래스에도 String Class 처럼 CompareTo 메서드가 있는데 왜 사용을 안하는가?
먼저 아래코드를 확인해보자, Integer 클래스의 일부 코드를 발췌한 것이다.
public final class Integer extends Number implements Comparable<Integer> {
...
...
...
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}
...
...
...
}
Integrer 클래스도 String Class 처럼 compareTo 메서드를 제공한다. 그럼에도 불구하고 왜 return second - first; 를 사용했을까? 사실 아주 간단한 이유가 있다. 단순 - 를통한 연산과 내부 메서드를 호출하여 연산 결과를 리턴받는 것과 효율의 관점으로 바라봤을때 당연히 단순 연산이 조금 더 낫다는 판단이 있었다. 메서드를 통해서 풀이를 하는것도 가독성 관점에서 본다면 나쁘찌 않다고 생각하지만, 알고리즘 문제를 푸는 관점에서는 시간복잡도 및 최적의 연산이 가장 우선시 되어야 하기에 단순 - 연산을 통해 코드를 구성했다.
마무리
위 문제를 풀면서 여러 방면으로 고민할 수 있었던 문제였던거 같은데 더 깊게 들어가면 더 깊은 고찰을 해야할거 같아서 이정도로만 정리하고 넘어가고자 한다. 실버4 문제랑 실버3 문제랑 갭차이가 이정도인가 싶은데 갑자기 난이도가 확 올라간 느낌이다.
-
[baekjoon] 통계학 (백준 2108 java 풀이)
intro : 최빈값을 구하는 부분을 염두해야 한다.
백준 문제링크
문제
수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값, 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값, 최빈값 : N개의 수들 중 가장 많이 나타나는 값, 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.
출력
첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다. 둘째 줄에는 중앙값을 출력한다. 셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다. 넷째 줄에는 범위를 출력한다.
문제 풀이1 (배열 풀이 552ms)
import java.io.*;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 입력값의 개수
int count = Integer.parseInt(br.readLine());
// 평균값, 중앙값, 범위 값을 구하기 위해 사용되는 변수
int[] array = new int[count];
// 최빈값을 구하기 위해 사용되는 변수, -4000 값이 0번 인덱스 4000 값이 8000번 인덱스
int[] freq = new int[8001];
// 최빈값을 1차적으로 구하기 위한 변수
int maxFreq = 0;
// 합계를 구하기 위한 변수
int sum = 0;
// 반복문을 통해 합계 sum, array, freq (최빈값을 구하기 위한 배열 변수)
for (int i = 0; i < count; i++) {
int input = Integer.parseInt(br.readLine());
sum += input;
array[i] = input;
// 여기서 입력되는 값에 대해 각 인덱스에 맞게 값이 증가함
// 예를들어서 4000 값이 두번 입력되었다면 freq[8000] = 2
freq[input + 4000]++;
// 가장 많이 나온 최빈값을 찾기위해서 여기서 먼저 계산해서 값을 가지고 있음
// 1차로 먼저 값을 구하는 이유는, 최빈값이 동일한 값이 존재할 수 있기에 먼저 계산을 진행
maxFreq = Math.max(maxFreq, freq[input + 4000]);
}
// 배열 정렬 (중앙값을 찾기 위함에 있음)
Arrays.sort(array);
// 산술평균 값
sb.append(Math.round((double) sum / count)).append("\n");
// 중앙값
sb.append(array[count / 2]).append("\n");
// 최빈값 구하는 중요 로직
int realFreqValue = 0;
// 첫번째 최빈값을 찾을때 true 로 변경
boolean flag = false;
for (int i = 0; i < 8001; i++) {
if (maxFreq == freq[i]) {
if (!flag) {
// -4000을 하는 이유는 0번 인덱스에 -4000값을 할당하도록 위에서 설정하였기 때문
// 실제 값을 계산하기 위해서는 0번인덱스의 값 = i - 4000
realFreqValue = i - 4000;
flag = true;
} else {
// flag 가 ture 라는것은 이미 첫번째 최빈값을 찾았고 현재 이 로직으로 들어왔을때가
// 두번째로 작은 최빈값이라는 뜻
realFreqValue = i - 4000;
break;
}
}
}
// 최빈값 계산
sb.append(realFreqValue).append("\n");
// 범위값 계산
sb.append(array[count - 1] - array[0]).append("\n");
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
문제 해석
이 문제는 마치 4개의 조각난 문제를 하나로 합친? 듯한 느낌이 드는 문제이다. 결국 구해야 하는 값을 정리해보자면 산술평균값, 중앙값, 최빈값, 범위 총 4가지인데 이중 최빈값을 제외한 나머지 값들은 하나의 배열에 값을 순차적으로 입력받고 계산하면 쉽게 풀리는데 이 최빈값 부분이 조건이 까다로웠다. 문제에서 예외적으로 최빈값이 여러개 있을 때는 두번째로 작은 값을 출력하라고 하였는데, 난 처음에는 이 문장을 읽고 오름차순으로 정렬한 배열에서 마지막 인덱스에서 - 1한 값이 두번째로 작은값을 뜻하는 줄 알았다. 뭔가 어떻게 읽냐에 따라서 문제의 해석이 좀 다르게 되는거 같은데 나에게만 해당하는 기분탓 일수도 있다…. 그래서 처음으로 풀었을때는 해당 문제에 대해서 틀렸었다.
산술평균값, 중앙값, 범위는 문제에서 주어진대로 계산을 하면 되는데, 최빈값 만큼은 로직구현이 다들 다르게 구성될거라 생각되어서 해당 부분을 나의 방법에 대해 설명하도록 하겠다. 나는 최빈값을 구하기 위해서 사실 처음에는 배열을 사용해서 문제 계산을 한게 아니라, 다양한 자료구조를 통해 문제를 해결하고자 하였다. 내가 처음으로 정답을 받은 코드를 먼저 확인해보자. (배열 사용 X, 다양한 Collection 자료구조 사용함)
문제 풀이2 (컬렉션 풀이 624ms)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 입력값의 개수
int count = Integer.parseInt(br.readLine());
// 평균값, 중앙값, 범위 값을 구하기 위해 사용되는 변수
int[] array = new int[count];
// 최빈값을 구하기 위해 사용되는 변수
Map<Integer, Integer> map = new HashMap<>(); // 최빈값 구하기
// 합계를 구하기 위한 변수
int sum = 0;
for (int i = 0; i < count; i++) {
int input = Integer.parseInt(br.readLine());
sum += input;
array[i] = input;
// 최빈값을 찾기 위한 map 을 통한 값 저장
// key 값 = input 값, value 값 = 입력 횟수
map.put(input, map.getOrDefault(input, 0) + 1);
}
// 배열 정렬 (중앙값을 찾기 위함에 있음)
Arrays.sort(array);
// 산술평균 값
sb.append(Math.round((double) sum / count)).append("\n");
// 중앙값
sb.append(array[array.length / 2]).append("\n");
// 최빈값
sb.append(findMode(map)).append("\n");
// 범위
sb.append(array[array.length - 1] - array[0]).append("\n");
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원반납
bw.close();
br.close();
}
// 최빈값을 찾기 위한 메서드
public static int findMode(Map<Integer, Integer> map) {
// 가장 큰 값을 찾기 위한 변수 선언
int maxValue = Integer.MIN_VALUE;
// 반복문을 통해 value 값이 가장 큰 값 찾기
for (Integer key : map.keySet()) {
Integer value = map.get(key);
if (value > maxValue) {
maxValue = value;
}
}
// Set 자료구조중에 TreeSet은 자동으로 정렬해주는 특징을 가지고 있다.
Set<Integer> set = new TreeSet<>();
for (Map.Entry<Integer, Integer> es : map.entrySet()) {
// 가장 큰값에 해당하는 key 값들을 set에 할당
if (es.getValue() == maxValue) {
set.add(es.getKey());
}
}
// Set 자료구조를 List로 변환
List<Integer> list = new ArrayList<>(set);
if (list.size() > 1) {
// 최빈값이 여러개라면? 두번째로 작은 값 retrun
return list.get(1);
} else {
// 최빈값이 하나라면 첫번째 값 return
return list.get(0);
}
}
}
왜 컬렉션 풀이에서 배열 풀이로 리팩토링을 하였는가?
위 방법으로 문제를 풀었을때는 최빈값부분에서 아무래도 형변환도 자주 일어나고 findMode 메서드를 통해 내부적으로 반복문이 한번더 실행되는게 시간복잡도 관점에서 보았을때 좀 별로라고 생각하였고, 최빈값을 구하는데에 있어서 저렇게 코드가 번잡하게 작성해야 할 필요가 있는가? 라는 물음에 스스로 답을 해보았을때 리팩토링이 필요하다고 생각이 되었다. 해서 문제의 조건을 다시 읽어보니, 입력되는 값의 범위가 절대값 4000까지 라는 문장이 숨어있었고, 해당 문장을 읽고나서 배열을 통해서 최빈값을 찾을 수 있겠다는 생각이 들어서 문제풀이1 과 같은 코드를 재 작성하게 되었다.
배열을 사용할수 있었던 이유
입력값이 범위가 절대값 4000 과 같이 문제에서 주어지지 않는다면 배열을 통해서 어느정도의 배열크기를 지정해서 선언하고 최빈값을 기록해야 하는지 알 수 없기에 컬렉션을 통해 최빈값을 찾는게 좋은 방법이 될 수 있지만, 현재 문제에서는 정확히 입력값의 범위가 주어졌기 때문에 배열을 통해서 푸는게 출제자가 의도한 문제 해답에 좀 더 가까운 해결책이라고 생각이 들었다.
배열풀이에서 가장 어려웠던 부분
배열을 통해서 본격적으로 코드를 작성할때 가장 난관이었던 부분은 최빈값이 여러개일때 두번째로 작은 값을 어떻게 구할것인가? 잘 생각해보니 freq라는 배열은 이미 어떻게 보면 정렬이 되어있는 배열이다. 그말이 무슨말이냐면 배열의 크기가 8001이며 0번 인덱스부터 8000번 인덱스 까지 값이 순차적으로 할당되어 있다. 이말은 정렬이 되어있는 최빈값의 배열이라는 말과 동일하다.
예를들어서 최빈값의 크기가 8이고 freq[0] = 1, freq[1] = 2, …. freq[302] = 8, …… freq[3302] = 8, …. 이런식의 상황이 있다면 순차적으로 freq 배열을 반복문을 돌았을때 첫번째 최빈값을 찾는 인덱스는 302번이다. 다만 최빈값이 8인 인덱스가 3302에도 있기에 두번째로 작은 값은 3302번이 되는데, 여기서 왜 이값이 두번쨰로 작은 값이냐면 위에서 freq 배열에 값을 할당할때 + 4000된 값을 freq 배열에 할당하였기에 실제로 return 되는 값은 3302 - 4000 값으로 -698이 return 된다.
마무리
위와 같은 방법을 통해 배열과 컬렉션을 사용한 문제풀이를 작성할 수 있었고, 어떤 상황에서 배열을 적용할지 컬렉션을 적용할지에 대해서도 느끼는 점이 많은 문제였던거 같다.
-
[baekjoon] 붙임성 좋은 총총이 (백준 26069 java 풀이)
intro : Set은 참 훌륭한 자료구조이다. (빠르고 중복제거도 해줌)
백준 문제링크
문제
총총이는 친구 곰곰이의 소개로 제2회 곰곰컵에 출연할 기회를 얻었다! 총총이는 자신의 묘기인 무지개 댄스를 선보여, 여러분의 환심을 사려 한다. 이 댄스는 중독성이 강하기 때문에, 한번 보게 된 사람은 모두 따라 하게 돼버린다. 무지개 댄스를 추는 총총 2마리 사람들이 만난 기록이 시간 순서대로 N개 주어진다. (총총이는 토끼이지만 이 문제에서는 편의상 사람이라고 가정한다.) 무지개 댄스를 추지 않고 있던 사람이 무지개 댄스를 추고 있던 사람을 만나게 된다면, 만난 시점 이후로 무지개 댄스를 추게 된다. 기록이 시작되기 이전 무지개 댄스를 추고 있는 사람은 총총이 뿐이라고 할 때, 마지막 기록 이후 무지개 댄스를 추는 사람이 몇 명인지 구해보자!
입력
첫번째 줄에는 사람들이 만난 기록의 수 N (1 <= N <= 1000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 사람들이 만난 기록이 주어진다. i + 1번째 줄에는 i번째로 만난 사람들의 이름 A와 B가 공백을 사이에 두고 주어진다. A와 B는 숫자와 영문 대소문자로 이루어진 최대 길이 20의 문자열이며, 서로 같지 않다. 총총이의 이름은 ChongChong으로 주어지며, 기록에서 1회 이상 주어진다. 동명이인은 없으며, 사람의 이름은 대소문자를 구분한다.(ChongChong과 chongchong은 다른 이름이다.)
출력
마지막 기록 이후 무지개 댄스를 추는 사람의 수를 출력하라.
문제 풀이 (124ms)
import java.io.*;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String stand = "ChongChong";
// 중복제거를 위한 set 변수 선언
// 무지개 댄스를 춘 사람들 및 전염시킬 수 있는 사람들의 모임
Set<String> set = new HashSet<>();
// ChongChong 미리 add
set.add(stand);
// 입력받을 값 개수
int count = Integer.parseInt(br.readLine());
StringTokenizer st;
for (int i = 0; i < count; i++) {
st = new StringTokenizer(br.readLine());
String first = st.nextToken();
String second = st.nextToken();
// 만약 무지개 댄스를 추고 있는사람들 이거나 전염된 사람들이라면
if (set.contains(first) || set.contains(second)) {
// 만남 사람들 또한 전염
set.add(first);
set.add(second);
}
}
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(String.valueOf(set.size()));
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
문제 해석
처음에 문제를 너무 쉽게 생각해서 빠르게 코드 제출하고 틀렸었는데 입력예제 1번에 속았던거 같다. 총총이가 나온다음 부터 모든 사람들은 전염되어 그냥 카운팅만 했었는데, 생각해보니까 총총이와 만난 사람들이 다음번에도 연속적으로 다른사람들과 만난다는 전제는 없으니, 전염된 사람들을 정확히 체크해서 전염된 사람들이 입력값으로 들어오는지 확인하여 카운팅을 해야한다.
위 말이 조금 이해가 안갈수도 있으니 좀더 명확하게 설명하자면, 총총이가 만난사람이 A라고 한다면 현재 무지개 댄스를 추는 사람은 총총이와 A다. 다음 입력값으로 B와 C가 들어온다면 이사람들은 총총이와 A를 만난게 아니니 무지개 댄스를 추지 않는다 하지만 다음 입력값으로 A와 D가 들어온다면 A는 총총이에게 전염당해 무지개댄스를 추구있는사람이니 D또한 무지개 댄스를 추게된다. (이후 같은 과정이 반복됨)
위 내용을 코드로 구현하게되면, 초기에 총총이를 set변수 (전염된 사람들의 모임)에 넣어두고 만나는 사람들이 set에 있는 사람들인지 확인하며 만약 set변수에 있는사람을 만났다는건 무지개 댄스를 추고 있는 사람이라는 것이니 만난 사람들 전부 set변수에 넣는다. 여기서 중복을 걱정할 수도 있지만. set은 중복을 제거하고 데이터를 관리하는 자료구조이기에 마음편히 set에 다 넣어서 관리해도 중복을 제거한 값들만 가지고 있게되어 결과적으로 size() 메서드를 통해 무지개 댄스를 추고 있는 사람들의 개수를 구할 수 있다.
-
-
[baekjoon] 약수 (백준 1037 java 풀이)
intro : 진짜 약수의 최소값과 최대값에 집중해보자.
백준 문제링크
문제
양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.
출력
첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.
문제 풀이 (104ms)
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 첫번째로 받는 입력값은 진짜약수의 개수
int count = Integer.parseInt(br.readLine());
// 진짜 약수를 보관할 배열 선언
int[] array = new int[count];
// 두번째 입력값으로
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < array.length; i++) {
array[i] = Integer.parseInt(st.nextToken());
}
// 배열을 정렬한다 (오름차순)
Arrays.sort(array);
// 구하고자 하는 N 값 = 배열의 첫번째 값 * 마지막값
int result = array[0] * array[array.length - 1];
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(String.valueOf(result));
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
문제 해석
처음에는 진짜약수 라는 말이 무슨말인지 이해가 잘 안갔는데, 결국 요약하자면 1과 본인자신의 숫자를 제외한 나머지 약수들을 진짜약수 라고 하는것을 알게 되자마자 문제가 눈에 좀 들어왔다.
내가 구하고자 하는 값은 진짜 약수들이 주어졌을때 해당 약수들을 갖는 원래의 수 N을 찾는것인데 만약 16이라는 N이 있다면 입력값으로 진짜 약수의 개수 3과 2,4,8이 주어질것이다. 그렇다면 N의 값은 진쨔약수를 오름차순으로 정렬했을때 첫번째 값 * 마지막 값이 = N이라는 것을 알 수 있다.
이건 문제에서 주어진 입력값과 출력값인데 내가 생각한 방법을 대입해보면 다음과 같은 결과를 얻을 수 있다.
예제입력 1 : 6
예제입력 2 : 3 4 2 12 6 8
예제입력 2 오름차순 정렬 : 2 3 4 6 8 12
예제입력 2의 첫번째 값과 마지막값을 곱 연산한 결과는 : 24
예제 출력값이 24 이므로 일치한다.
위 내용을 기반으로 코드의 구현 방향을 정하였고, 가장 작은 약수와 가장 큰 약수를 곱하면 원래의 숫자 𝑁 을 정확히 계산할 수 있게 되었다.
-
[baekjoon] 창문 닫기 (백준 13909 java 풀이)
intro : 이런 문제들 너무나도 싫다.
백준 문제링크
문제
서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다. 예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때, 1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1) 2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1) 3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0) 결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.
입력
첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.
출력
마지막에 열려 있는 창문의 개수를 출력한다.
문제 풀이 (108ms)
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 주어지는 입력값
int input = Integer.parseInt(br.readLine());
// 제곱근의 값으로 결과값 계산
int result = (int) Math.sqrt(input);
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(String.valueOf(result));
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
문제 해석
아, 이문제는 정말이지 푸는데 굉장히 오래걸렸다.(이전에도 말했지만 직관적이지 않은 문제, 정수론 같은 방법을 통해서 푸는 문제들은 난이도에 상관없이 항상 어렵다) 단순히 반복문을 통해서 1부터 주어진 N까지의 값만큼 반복문을 돌면서 열고 닫고를 체크하자니 주어지는 값의 N의 범위가 21억까지여서 시간복잡도만 단순히 따져보아도 이렇게 푸는 문제가 아니라고 느껴지니 다른 방법을 통해 문제를 풀어야겠다고 생각이 들었다.
잘 생각해보면 결국 내가 계산해야하는 결과값은 마지막에 열려 있는 창문의 개수 이다. 그렇다면 열려있는 창문은 언제 열려있는가? 주어지는 값이 5라고 생각해봤다.
그렇다면 다음과같이 1(닫힘),2(닫힘),3(닫힘),4(닫힘),5(닫힘) 값이 주어지고 순차적으로 1~5의 배수값들은 열고 닫고가 반복된다. 이내용을 다음과같이 순서대로 표현해보았다.
입력값 : 5 인 경우
초기상태: 1(닫힘),2(닫힘),3(닫힘),4(닫힘),5(닫힘)
반복문 1: 1(열림),2(열림),3(열림),4(열림),5(열림)
반복문 2: 1(열림),2(닫힘),3(열림),4(닫힘),5(열림)
반복문 3: 1(열림),2(닫힘),3(닫힘),4(닫힘),5(열림)
반복문 4: 1(열림),2(닫힘),3(닫힘),4(열림),5(열림)
반복문 5: 1(열림),2(닫힘),3(닫힘),4(열림),5(닫힘)
마지막에 열려있는 창문의 개수 : 2
대충 여기서 살짝 감이 왔던게 아 이거 약수와 연관이 있구나, 약수의 개수가 홀수인경우는 열려있고 짝수인 경우는 닫혀있다고 뭔가 느낌이 왔다, 여기서 한번 더 다른 케이스에 대해서 검증해 보았다.
입력값 : 9 인 경우
초기상태: 1(닫힘),2(닫힘),3(닫힘),4(닫힘),5(닫힘),6(닫힘),7(닫힘),8(닫힘),9(닫힘)
반복문 1: 1(열림),2(열림),3(열림),4(열림),5(열림),6(열림),7(열림),8(열림),9(열림)
반복문 2: 1(열림),2(닫힘),3(열림),4(닫힘),5(열림),6(닫힘),7(열림),8(닫힘),9(열림)
반복문 3: 1(열림),2(닫힘),3(닫힘),4(닫힘),5(열림),6(열림),7(열림),8(닫힘),9(닫힘)
반복문 4: 1(열림),2(닫힘),3(닫힘),4(열림),5(열림),6(열림),7(열림),8(열림),9(닫힘)
반복문 5: 1(열림),2(닫힘),3(닫힘),4(열림),5(닫힘),6(열림),7(열림),8(열림),9(닫힘)
반복문 6: 1(열림),2(닫힘),3(닫힘),4(열림),5(닫힘),6(닫힘),7(열림),8(열림),9(닫힘)
반복문 7: 1(열림),2(닫힘),3(닫힘),4(열림),5(닫힘),6(닫힘),7(닫힘),8(열림),9(닫힘)
반복문 8: 1(열림),2(닫힘),3(닫힘),4(열림),5(닫힘),6(닫힘),7(닫힘),8(닫힘),9(닫힘)
반복문 9: 1(열림),2(닫힘),3(닫힘),4(열림),5(닫힘),6(닫힘),7(닫힘),8(닫힘),9(열림)
마지막에 열려있는 창문의 개수 : 3개
여기까지 손으로 그려보니 뭔가 순차적으로 그려보면 규칙이 나오지 않을까 싶어서 다음과 같이 순차적으로 그려보고 마지막에 열려있는 창문의 개수와 연관관계를 유추해보고자 하였다.
입력값 : 1 인 경우
초기상태: 1(닫힘)
반복문 1: 1(열림)
마지막에 열려있는 창문의 개수 : 1개
입력값 : 2 인 경우
초기상태: 1(닫힘),2(닫힘)
반복문 1: 1(열림),2(열림)
반복문 2: 1(열림),2(닫힘)
마지막에 열려있는 창문의 개수 : 1개
입력값 : 3 인 경우
초기상태: 1(닫힘),2(닫힘),3(닫힘)
반복문 1: 1(열림),2(열림),(열림)
반복문 2: 1(열림),2(닫힘),(열림)
반복문 3: 1(열림),2(닫힘),(닫힘)
마지막에 열려있는 창문의 개수 : 1개
입력값 : 4 인 경우
초기상태: 1(닫힘),2(닫힘),3(닫힘),4(닫힘)
반복문 1: 1(열림),2(열림),(열림),(열림)
반복문 2: 1(열림),2(닫힘),(열림),(닫힘)
반복문 3: 1(열림),2(닫힘),(닫힘),(닫힘)
반복문 4: 1(열림),2(닫힘),(닫힘),(열림)
마지막에 열려있는 창문의 개수 : 2개
입력값 : 5 인 경우
초기상태: 1(닫힘),2(닫힘),3(닫힘),4(닫힘),5(닫힘)
반복문 1: 1(열림),2(열림),3(열림),4(열림),5(열림)
반복문 2: 1(열림),2(닫힘),3(열림),4(닫힘),5(열림)
반복문 3: 1(열림),2(닫힘),3(닫힘),4(닫힘),5(열림)
반복문 4: 1(열림),2(닫힘),3(닫힘),4(열림),5(열림)
반복문 5: 1(열림),2(닫힘),3(닫힘),4(열림),5(닫힘)
마지막에 열려있는 창문의 개수 : 2개
각 숫자의 약수의 개수가 짝수인 경우는 결론적으로 닫힌 창문이 되는데, 그 이유는 초기에 닫혀있던게 짝수번 2,4,6,8 만큼 열렸다 다시 닫히기 떄문에 결론적으로는 닫힌 창문이된다. 그렇다면 약수의 개수가 홀수인경우는 1,3,5,7,9 만큼 열리고 닫히고 다시 열리기 때문에 결론적으로는 열린 창문이 된다. 결론적으로 약수의 개수가 홀수인 경우만 창문이 열린다는걸 알 수 있다.
이걸 코드로 구현해보자면 주어지는 값 N의 제곱근의 값은 결론적으로 위 과정을 반복하였을때 열려있는 창문의 개수를 구할수 있는 공식이 된다는 걸 알 수 있다.
-
[baekjoon] 가로수 (백준 2485 java 풀이)
intro : 가로수길 걷다가 이 문제가 생각날것만 같다.
백준 문제링크
문제
직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다. 편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다. 예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다. 심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.
입력
첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 1,000,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르고, N개의 가로수는 기준점으로부터 떨어진 거리가 가까운 순서대로 주어진다.
출력
모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.
문제 풀이 (220ms)
import java.io.*;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 반복 횟수 변수 선언
int forCount = Integer.parseInt(br.readLine());
// 입력값 배열 선언
int[] array = new int[forCount];
for (int i = 0; i < array.length; i++) {
array[i] = Integer.parseInt(br.readLine());
}
// 오름차순으로 정렬 (각 가로수의 순차적인 차이를 알기 위해서 정렬)
Arrays.sort(array);
// 가로수의 각 차이를 저장할 배열 선언
int[] gap = new int[array.length - 1];
// 반복문을 통해 i + 1 인덱스의 가로수와, i 인덱스의 가로수의 거리 차이를 계산
for (int i = 0; i < array.length - 1; i++) {
gap[i] = array[i + 1] - array[i];
}
int gapStand = gap[0];
for (int i = 1; i < gap.length; i++) {
// 반복문을 통해 최대공약수를 계산
gapStand = gcm(gap[i], gapStand);
}
int result = 0;
for (int g : gap) {
// 각 가로수간의 차이를 최대공약수로 나눈 몫에 - 1 값이 새로 심어야 하는 가로수의 개수
result += (g / gapStand) - 1;
}
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(String.valueOf(result));
bw.flush();
// 자원 반납
bw.close();
br.close();
}
// 최대공약수를 구하는 메소드
// 유클리드 호제법
// return 해야하는 값(최대 공약수)는 몫이다.
public static int gcd(int a, int b) {
while (b > 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
}
문제 해석
생각보다 까다로웠다고 느낀 문제였다. (뭔가 풀이방법이 직관적으로 보이지않는 문제들은 난이도 레벨 이런거랑 상관없이 항상 까다롭다고 느낀다.) 각 가로수 간의 차이를 최대공약수를 통해 가로수의 간격이 같을 수 있도록 할 수 있는데. 이또한 문제를 그림으로 그려보다가 알게되었다.
만약 주어진 값이 아래와 같다면 같은 간격을 유지한채로 가로수를 심으려면 결국 2만큼의 간격마다 가로수를 심어야 한다는 것을 알 수 있다. 3칸 간격으로 가로수를 심자니 1과 3 사이의 간격이 2이므로 3칸 간격으로 심을수 없고 1칸 간격으로도 심을 수 있으나, 문제의 조건이 새로 심어야 하는 최소수를 구하는 것이기에 2칸 간격으로 가로수를 심어야 한다.
입력값 : 1 3 7 13
1과 3의 차이 : 2
3과 7의 차이 : 4
7과 13의 차이 : 6
2 4 6의 최대 공약수는 ? [2]
그러면 2칸 간격마다 가로수를 새로 심게되는데 이때 다음과 같이 새로운 가로수를 심게 된다.
1 3 [5] 7 [9] [11] 13
[5],[9],[11] 3개의 가로수를 새로 심어야 한다.
근데 우리가 계산해야하는 결과는 새로심는 가로수의 개수이기에 다음과 같은 계산방법을 통해 추출 할 수 있다. (가로수 사이의 차이 값 / 최대공약수) - 1 예시를 들어보자면, 7과 3의 차이는 4이다. 4 / 최대공약수(2) - 1은 1이다. 3과 7 사이에 새로 심는 가로수의 개수는 1개이다, 13과 7의 차이는 6이다. 6 / 최대공약수(2) - 1은 2이다. 7과 13 사이에 새로 심는 가로수의 개수는 2개이다.
이렇게 최대공약수를 통해 간격을 통일하고 추가 가로수의 최소 개수를 구하는 방식으로 문제를 해결할 수 있다. 문제를 처음에는 어렵게 느꼈지만, 최대공약수 활용이라는 공식을 통해 간결하게 풀이할 수 있다는게 신기한거 같다.
-
[baekjoon] 다리 놓기 (백준 1010 java 풀이)
intro : 최적화를 해서 문제를 풀어보자.
백준 문제링크
문제
재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.
출력
각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.
문제 풀이1 (BigInteger를 이용한 풀이 160ms)
import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 반복 횟수 변수 선언
int forCount = Integer.parseInt(br.readLine());
// 반복 횟수만큼 반복문 실행
for (int i = 0; i < forCount; i++) {
// 입력값이 13 29 이런식으로 라인별로 들어오기에 StringTokenizer 객체 생성
StringTokenizer st = new StringTokenizer(br.readLine());
int first = Integer.parseInt(st.nextToken());
int second = Integer.parseInt(st.nextToken());
// 문제에서 주어진 조건은 두번쨰로 들어온 값이 첫번쨰로 들어온 값보다 크거나 같음
BigInteger value1 = factorial(second);
BigInteger value2 = factorial(second - first);
BigInteger value3 = factorial(first);
// 곱하기, 나누기 연산
BigInteger multiply = value2.multiply(value3);
BigInteger divide = value1.divide(multiply);
sb.append(divide).append("\n");
}
// bw로 출력하기 위해 sb를 문자열로 변환 후 write
bw.write(sb.toString());
bw.flush();
// 자원 반납
bw.close();
br.close();
}
public static BigInteger factorial(int n) {
// factorial 메소드를 실행하기 위한 각 변수 BigInteger 타입으로 선언
BigInteger result = BigInteger.ONE;
BigInteger inputN = BigInteger.valueOf(n);
BigInteger zero = BigInteger.ZERO;
BigInteger one = BigInteger.ONE;
// BigInteger는 compareTo 메소드로 비교
while (inputN.compareTo(zero) > 0) {
result = result.multiply(inputN);
inputN = inputN.subtract(one);
}
return result;
}
}
문제 해석1
문제의 내용의 주된 포인트는 왼쪽 사이트의 지점에 모두 다리가 건설이 되어야 한다 라는 점이 포인트다. 그말은 즉슨 오른쪽 다리에서 왼쪽다리는 무조건 선택해서 다리를 지어야 하기에, 중복되지않게 다리를 지으려면 오른쪽 다리의 사이트 포인트 중에서 왼쪽 다리의 사이트 포인트 만큼의 조합의 개수를 구하면 된다는 말로 귀결된다. 결국 이 문제 또한 조합의 갯수를 구하는 문제이며 해당 문제를 이해했다면 구현 로직으로 넘어가면 된다.
구현 로직에서 함정이 있는데, 보통 아무리 큰 값을 계산하더라도 long 타입으로 어느정도는 계산이 되는데, 30!을 계산하려면 long 을 통해 계산을 할 수 없다.(아래 그림을 참고하면 30!의 값이 얼마나 큰 값인지 알 수 있다.) 그렇다면 그보다 더 큰 데이터 범위를 담을 수 있는 객체를 사용해야 하는데 해당 문제를 풀기위해 BigInteger 타입을 사용하여 계산해 주었다.
문제 풀이2 (최적화를 통한 풀이 112ms)
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter, StringBuilder 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 반복 횟수 변수 선언
int forCount = Integer.parseInt(br.readLine());
// 반복 횟수만큼 반복문 실행
for (int i = 0; i < forCount; i++) {
// 입력값이 13 29 이런식으로 라인별로 들어오기에 StringTokenizer 객체 생성
StringTokenizer st = new StringTokenizer(br.readLine());
int first = Integer.parseInt(st.nextToken());
int second = Integer.parseInt(st.nextToken());
// 조합을 계산하는 최적화 메소드 호출
long result = combination(second, first);
sb.append(result).append("\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
public static long combination(int second, int first) {
// 결과값 변수 1 선언
long result = 1;
for (int i = 0; i < first; i++) {
// 분자 계산
result *= second - i;
// 분모 계산
result /= i + 1;
}
return result;
}
}
문제 해석2
위 코드에서 팩토리얼의 불필요한 연산과정을 줄이고 BigInteger 타입을 사용하지 않더라도 long 타입으로 연산을 할 수 있는 방법이 존재한다. 문제풀이1에서는 현재 순차적으로 계산을 진행하다보니, 큰 결과값이 도출되어 어쩔수 없이 BigInteger을 사용했는데 다음과 같은 방법을 사용하면 long 타입으로도 문제를 해결 할 수 있다.
먼저 어떻게 중복된 연산과정을 줄였는지 아래 이미지를 보면서 알아보자.
만약 10개의 카드중에 3개의 카드의 조합을 구하는 문제가 있다면 위 계산을 적용할 것이다. 근데 잘 생각해보면 분자와 분모에서 중복되어 약분이 되는 부분이 있는데, 현재 상황에서는 아래 이미지처럼 바로 7!이 약분되어 나머지 부분만 연산을 진행하면 최적화된 계산을 진행할 수 있다.
해당 내용을 정리하자면 결국 10개의 카드중에 3개의 카드를 뽑는 조합을 구하는 문제를 풀기위한 연산은 10~8 까지의 팩토리얼 연산과(분자) 1~3까지의 팩토리얼 연산(분모)만 하면 최적화된 결과를 구할 수 있음을 알 수 있다.
-
-
-
[baekjoon] 녹색거탑 (백준 24723 java 풀이)
intro : 문제가 암청 거창한거에 비해 풀이는 간단하다.
백준 문제링크
문제
Naver D2를 아시나요? D2는 For Developers, By Developers의 약자로, 개발자들을 위해 개발자들이 직접 만들어 가고 있는 네이버 개발자 지원 프로그램입니다. 네이버가 축적한 기술과 지식을 공유하고, 외부 개발자들을 지원해 대한민국 개발자 역량 강화를 이끌고, 이를 통해 업계 전체와 네이버가 함께 성장하는 선순환 구조를 만들고자 합니다. 사실 네이버의 개발자 지원은 오랜 기간 꾸준히 이어져 왔습니다. 개발자 컨퍼런스 DEVIEW를 비롯, 오픈 소스와 개발 도구 공개, 학회 및 커뮤니티 지원 등 여러 지원 프로그램이 있었습니다. 이런 다양한 프로그램을 하나로 통합한 것이 바로 Naver D2입니다. 2022년 봄 어느 날. 전 세계에 코딩괴물이 나타났다. 그리고 코딩괴물과 함께 갑작스레 등장한 ‘그것’… 바로 녹색거탑이다. 녹색거탑의 정상에서는 매년 NAVER가 개최하는 개발자 컨퍼런스 DEVIEW가 열린다. 이 DEVIEW에 참여하면, 코딩에 깊은 깨달음을 얻어 코딩괴물이 될 수 있다고 전해진다. 그리고 코딩괴물은 녹색거탑의 정상에서 내려온다. 예전부터 전해 내려오는 D2 비전서에 의하면, 코딩괴물이 녹색거탑의 정상에서 내려오는 경우의 수를 파악한 사람은, 개발자 컨퍼런스 DEVIEW에 참여할 수 있다 한다. 그리고 DEVIEW에 참여해 본인도 코딩괴물이 될 수 있다! 녹색거탑은 위 그림과 같이 규칙적으로 쌓여있다. 그림의 시야에 보이지 않는 블록은 없다. 그림의 시야에 보이는 블록의 윗면만 이용해 녹색거탑을 내려올 수 있다. 녹색거탑이 N층이면, 총 N개의 블록을 이용한 최단 경로로만 내려온다. 녹색거탑을 내려올 때는 정상에서 시작해 노란색 바닥까지, 항상 인접한 아래층의 블록으로만 내려온다. 녹색거탑을 정복하고 DEVIEW에 참여하자.
입력
녹색거탑의 높이를 나타내는 정수 N이 주어진다. (1 <= N <= 5)
출력
녹색거탑의 정상에서 바닥으로 내려오는 경우의 수를 출력한다.
문제 풀이 (100ms)
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력을 위한 BufferedReader, BufferedWriter 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// br을 통해 읽은 값 정수로 변환
int input = Integer.parseInt(br.readLine());
// 최단 경로로 갈수 있는 경우의 수 계산
// Math.pow는 return 값이 double 이기에 (int)로 결과값 명시적 형변환
int result = (int) Math.pow(2, input);
// bw로 출력하기 위해 문자열로 변환 후 write
bw.write(String.valueOf(result));
bw.flush();
// 자원 반납
bw.close();
br.close();
}
}
문제 해석
문제에서 주어진 그림과, 문제의 주된 내용 녹색거탑이 N층이면, 총 N개의 블록을 이용한 최단 경로로만 내려온다., 항상 인접한 아래층의 블록으로만 내려온다. 를 생각해보면 이진트리를 떠올릴 수 있다. 5층의 녹색거탑을 내려온다면 무조건 5개의 블록을 이용해 내려와야 하는데 이때 5개의 블록을 내려올 수 있는 경우의 수는 1칸단 2개의 경우의 수가 존재하기에 층마다 제곱배로 경우의 수가 증가한다. 이를 순차적으로 표현하면 아래와 같다.
1층 2개
2층 4개
3층 8개
4층 16개
5층 32개
결국에는 문제의 최단경로로 내려올 수 있는 경우의 수를 구하는 계산 공식은 2^N(2의N승) 이라고 볼 수 있다.
-
-
[baekjoon] 골드바흐 파티션 (백준 17103 java 풀이)
intro : 에라토스테네스의 체 방식으로 문제풀이를 성공했다.
백준 문제링크
문제
골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.
입력
첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.
출력
각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.
문제 풀이 (252ms)
import java.io.*;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
int tcValMax = Integer.MIN_VALUE;
int tcCount = Integer.parseInt(br.readLine());
int[] tcArray = new int[tcCount];
for (int i = 0; i < tcArray.length; i++) {
tcArray[i] = Integer.parseInt(br.readLine());
if (tcArray[i] > tcValMax) {
tcValMax = tcArray[i];
}
}
boolean[] isPrime = new boolean[tcValMax + 1];
Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i * i <= isPrime.length; i++) {
if (isPrime[i]) {
for (int j = i * i; j < isPrime.length; j += i) {
isPrime[j] = false;
}
}
}
for (int tc : tcArray) {
int count = 0;
for (int i = 2; i <= tc / 2; i++) {
if (isPrime[i] && isPrime[tc - i]) {
count++;
}
}
sb.append(count).append("\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
}
문제 해석
이 문제는 큰 틀의 관점에서 보았을때 2가지의 단계로 나누어 문제를 접근 할 수 있다.
첫번째 단계
조건에서 주어진 2 < N ≤ 1,000,000 에 해당하는 범위의 값들 중 소수를 판별한다.
두번째 단계
위 첫번째 문제에서 판별한 소수들 중에서 테스트 케이스로 주어진 값의 조합으로 구할 수 있는 경우의 수를 구한다. 예를들어 테스트케이스로 5가 주어졌다면, 소수인 2 + 3 의 조합으로 골드바흐 파티션을 만족하므로 1을 출력한다.
첫번째 단계를 접근하기 위해 에라토스테네스의 체에 대해서 알아야 한다.
에라토스테네스의 체 란 ?
2부터 시작해서 소수를 찾아내고 해당 소수의 배수들을 모두 제외시키는 방식으로 소수를 구한다. 이때, 해당 소수는 제외하지않는다. 이렇게 제외를 시키다보면 남은 숫자들은 전부 소수이다.
위 내용을 다음과 같이 세부 단계를 나누어 설명할 수 있다.
먼저, 2부터 n까지의 모든 수를 소수로 가정하고 배열에 표시한다. 2는 소수이므로, 2의 배수(즉, 4, 6, 8, 10 등)는 소수가 아니므로 false로 표시한다. 그다음, 3은 소수이므로, 3의 배수(즉, 6, 9, 12, 15 등)는 소수가 아니므로 false로 표시한다. 4는 이미 2의 배수로 지워졌기 때문에 건너뛰고, 그다음 5는 소수이므로, 5의 배수(즉, 10, 15, 20, 25 등)는 소수가 아니므로 false로 표시한다. 이 과정이 계속해서 반복된다.
결국 소수가 아닌것들을 제외하는 과정을 로직상으로 구현하는것이 첫번째 문제를 푸는 것의 열쇠가 된다. 위 내용을 담은 코드는 다음과 같다. (주석을 참고하자)
첫번째 단계 코드 주석
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
// 입력값을 받기위한 BufferedReader 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
// 테스트 케이스로 입력받는 값들중 가장 큰값을 구하기 위한 기준 값
int tcValMax = Integer.MIN_VALUE;
// 테스트 케이스 갯수
int tcCount = Integer.parseInt(br.readLine());
// 테스트 케이스의 값을 담을 배열
int[] tcArray = new int[tcCount];
// 테스트 케이스 갯수만큼의 반복문을 실행
for (int i = 0; i < tcArray.length; i++) {
tcArray[i] = Integer.parseInt(br.readLine());
// 테스트 케이스 값들중 가장 큰값을 구하는 로직
if (tcArray[i] > tcValMax) {
tcValMax = tcArray[i];
}
}
// 테스트 케이스 중에서 가장 큰값에 대한 배열
// +1 을 하는이유는 인덱스는 0부터 시작이기에
boolean[] isPrime = new boolean[tcValMax + 1];
// 초기는 전부 소수라고 가정 하고 시작
Arrays.fill(isPrime, true);
// 0과 1은 소수가 아님
isPrime[0] = false;
isPrime[1] = false;
// 2부터 시작해서 i * i 가 배열의 길이보다 작은지 검증
// i * i 를 하는 이유는 내부 반복문에서 이미 소수인지 검증한 값을 생략하기 위함
for (int i = 2; i * i <= isPrime.length; i++) {
// 만약 소수라면
if (isPrime[i]) {
// 해당 소수값은 제외하고 소수값의 배수들을 소수에서 제외함
for (int j = i * i; j < isPrime.length; j += i) {
isPrime[j] = false;
}
}
}
// ---------------------------- 이 아래는 차후 설명 ----------------------------
for (int tc : tcArray) {
int count = 0;
for (int i = 2; i <= tc / 2; i++) {
if (isPrime[i] && isPrime[tc - i]) {
count++;
}
}
sb.append(count).append("\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
}
여기까지 이해했다면 isPrime 배열안에 소수들만 true 값을 갖게된다.
이제 두번째 단계인 골드바흐 파티션을 구하기 위해서 다음과 같은 방법을 사용하고자한다. 예제를 통해 이해해보자면, 10을 이루는 소수의 합이 있는가를 검증하고 싶다면 아래와 같이 검증한다.
소수 2 + ? = 10 여기서 ? 값은 8 이다 8은 소수가 아니기에 2와 어떤 소수와 합을 이루어 10을 이루는 골드바흐 파티션은 존재하지 않는다. 3 + ? = 10 ? 값은 7 3과 7은 둘다 소수이기에 골드바흐 파티션을 만족한다. 5 + ? = 10 ? 은 5 이기에 이 또한 골드바흐 파티션을 만족한다. 6 + ? =10 ?는 4 이기에 만족하지 못한다. 7 + ? = 10 ?는 3이기에 소수여서 골드바흐 파티션을 만족하지만 이미 3과7 조합이 나왔기에 중복된걸로 간주된다. 이 과정을 코드로 표현 하자면 다음과 같다. (위 코드와 이어진다.)
두번째 단계 코드 주석
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
// 입력값을 받기위한 BufferedReader 객체 생성
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 출력하기 위한 BufferedWriter 객체 생성
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 값을 한번에 문자열로 다루기 위한 StringBuilder 객체 생성
StringBuilder sb = new StringBuilder();
// 테스트 케이스로 입력받는 값들중 가장 큰값을 구하기 위한 기준 값
int tcValMax = Integer.MIN_VALUE;
// 테스트 케이스 갯수
int tcCount = Integer.parseInt(br.readLine());
// 테스트 케이스의 값을 담을 배열
int[] tcArray = new int[tcCount];
// 테스트 케이스 갯수만큼의 반복문을 실행
for (int i = 0; i < tcArray.length; i++) {
tcArray[i] = Integer.parseInt(br.readLine());
// 테스트 케이스 값들중 가장 큰값을 구하는 로직
if (tcArray[i] > tcValMax) {
tcValMax = tcArray[i];
}
}
// 테스트 케이스 중에서 가장 큰값에 대한 배열
// +1 을 하는이유는 인덱스는 0부터 시작이기에
boolean[] isPrime = new boolean[tcValMax + 1];
// 초기는 전부 소수라고 가정 하고 시작
Arrays.fill(isPrime, true);
// 0과 1은 소수가 아님
isPrime[0] = false;
isPrime[1] = false;
// 2부터 시작해서 i * i 가 배열의 길이보다 작은지 검증
// i * i 를 하는 이유는 내부 반복문에서 이미 소수인지 검증한 값을 생략하기 위함
for (int i = 2; i * i <= isPrime.length; i++) {
// 만약 소수라면
if (isPrime[i]) {
// 해당 소수값은 제외하고 소수값의 배수들을 소수에서 제외함
for (int j = i * i; j < isPrime.length; j += i) {
isPrime[j] = false;
}
}
}
// ------------ 여기까지가 위 코드내용과 같고 아래가 골드바흐파티션을 검증하는 로직이다 -------
// 테스트 케이스의 값을 순차적으로 꺼낸다
for (int tc : tcArray) {
// 초기 카운트 값 0으로 초기화
int count = 0;
// 소수의 합으로 tc를 이룰수 있는지 검증
// 소수의 합을 구해야 하기 떄문에 2부터 시작
// tc / 2를 하는 이유는 중복된 조합을 생략하기 위함에 있다.
for (int i = 2; i <= tc / 2; i++) {
// isPrime의 index는 각 숫자를 뜻하며 해당 index의 value 값은 소수여부 판별값이다.
// 결국 tc가 10이이고 i가 3이라면
// isPrime[3] = true, isPrime[10 - 3] = true (7은 소수이다.)
if (isPrime[i] && isPrime[tc - i]) {
// 값 증가
count++;
}
}
sb.append(count).append("\n");
}
// 출력
bw.write(sb.toString());
bw.flush();
// 객체 자원 반환
bw.close();
br.close();
}
}
-
-
-
-
-
[baekjoon] 풍선 터뜨리기 (백준 2346 java 풀이)
intro : 계속 고민하게 되는 부분은 풍선의 순서 번호와, 풍선안의 이동해야하는 값을 동시에 어떻게 관리할 것인가를 생각해 보았다.
백준 문제링크
문제
1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다. 우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다. 예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.
출력
첫째 줄에 터진 풍선의 번호를 차례로 나열한다.
문제 풀이 1 (Map을 이용 180ms)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Deque<Map<Integer, Integer>> deque = new ArrayDeque<>();
int forCount = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= forCount; i++) {
Map<Integer, Integer> map = new HashMap<>();
int value = Integer.parseInt(st.nextToken());
map.put(i, value);
deque.addLast(map);
}
Map<Integer, Integer> remove = deque.removeFirst();
Integer value = remove.get(1);
sb.append(1).append(" ");
while (!deque.isEmpty()) {
if (value > 0) {
for (int i = 0; i < value - 1; i++) deque.addLast(deque.removeFirst());
remove = deque.removeFirst();
} else {
for (int i = 0; i < Math.abs(value) - 1; i++) deque.addFirst(deque.removeLast());
remove = deque.removeLast();
}
Integer index = new ArrayList<>(remove.keySet()).get(0);
sb.append(index).append(" ");
value = remove.get(index);
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
}
문제 풀이2 (int[] 을 이용 152ms)
import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Deque<int[]> deque = new ArrayDeque<>();
int forCount = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= forCount; i++) {
int value = Integer.parseInt(st.nextToken());
deque.addLast(new int[]{i, value});
}
int[] removeArray = deque.removeFirst();
int value = removeArray[1];
sb.append(removeArray[0]).append(" ");
while (!deque.isEmpty()) {
if (value > 0) {
for (int i = 0; i < value - 1; i++) deque.addLast(deque.removeFirst());
removeArray = deque.removeFirst();
} else {
for (int i = 0; i < (-value) - 1; i++) deque.addFirst(deque.removeLast());
removeArray = deque.removeLast();
}
value = removeArray[1];
sb.append(removeArray[0]).append(" ");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
}
-
[baekjoon] 도키도키 간식드리미 (백준 12789 java 풀이)
intro : ArrayDeque를 두개 사용하여 문제를 풀어가는게 포인트.
백준 문제링크
문제
인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다. 그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다. 사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라. 현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.
위 예제는 다음 그림과 같이 움직였을 때 모두가 순서대로 간식을 받을 수 있다.
입력
입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다. 다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,…,N) 순서가 앞에서부터 뒤 순서로 주어진다.
출력
승환이가 무사히 간식을 받을 수 있으면 “Nice”(따옴표는 제외)를 출력하고 그렇지 않다면 “Sad”(따옴표는 제외)를 출력한다.
문제 풀이 (틀린 방법)
위 코드에서 틀린 부분은 deque2에서 연속되어 stand와 일치하는값이 나올 수 있다는 경우의 수를 생각하지 못해서 틀린 로직을 구성하게 되었다. while문으로 stand값이 일치하는값이 존재한다면 remove를 해주어야 하는데 그부분을 놓쳤다.
import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Deque<Integer> deque1 = new ArrayDeque<>();
Deque<Integer> deque2 = new ArrayDeque<>();
br.readLine();
StringTokenizer st = new StringTokenizer(br.readLine());
while (st.hasMoreTokens()) deque1.add(Integer.parseInt(st.nextToken()));
int stand = 1;
while (!deque1.isEmpty()) {
Integer value = deque1.removeFirst();
if (value == stand) stand++;
else {
if (!deque2.isEmpty()) {
if (deque2.peekFirst() == stand) {
deque2.removeFirst();
stand++;
} else deque2.addFirst(value);
} else deque2.addFirst(value);
}
}
for (Integer temp : deque2) {
if (temp == stand) {
deque2.removeFirst();
stand++;
} else break;
}
if (deque2.isEmpty()) bw.write("Nice");
else bw.write("Sad");
bw.flush();
bw.close();
br.close();
}
}
문제 풀이 (112ms)
import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Deque<Integer> deque1 = new ArrayDeque<>();
Deque<Integer> deque2 = new ArrayDeque<>();
br.readLine();
StringTokenizer st = new StringTokenizer(br.readLine());
while (st.hasMoreTokens()) deque1.add(Integer.parseInt(st.nextToken()));
int stand = 1;
while (!deque1.isEmpty()) {
Integer value = deque1.removeFirst();
if (value == stand) {
stand++;
while (!deque2.isEmpty() && (deque2.peekFirst() == stand)) {
deque2.removeFirst();
stand++;
}
} else deque2.addFirst(value);
}
if (deque2.isEmpty()) bw.write("Nice");
else bw.write("Sad");
bw.flush();
bw.close();
br.close();
}
}
문제 해석
위 문제는 큐 두개를 사용해서 풀이를 진행 할 수 있다. 주어진 예시를 잘 보면 1번 큐에서 2번 큐로의 값 이동은 가능하지만, 2번큐에서 1번 큐로의 이동은 불가하다. 그말은 1번큐에서의 값을 꺼내서 stand와 값이 일치하는지 확인하고, 일치한다면 remove 를 하고 혹시 2번 큐에서 다음 stand 값과 일치하는 값이 존재하는지 확인한다. 연속된 일치하는 값이 존재할 수 있으므로 while 문으로 반복하여 확인한다. 사실 이 문제에서 가장 중요한 부분은 언제 1번 큐에서 2번 큐로의 값을 이동시킬것인지와, 2번큐의 값을 언제 꺼내서 확인할 것인지 로직을 구성하는게 포인트가 되는 것 같다.
-
[baekjoon] 대표값2 (백준 2587 java 풀이)
intro : Arrays.sort 메소드를 통해 오름차순으로 쉽게 정렬할 수 있다.
백준 문제링크
문제
어떤 수들이 있을 때, 그 수들을 대표하는 값으로 가장 흔하게 쓰이는 것은 평균이다. 평균은 주어진 모든 수의 합을 수의 개수로 나눈 것이다. 예를 들어 10, 40, 30, 60, 30의 평균은 (10 + 40 + 30 + 60 + 30) / 5 = 170 / 5 = 34가 된다. 평균 이외의 또 다른 대표값으로 중앙값이라는 것이 있다. 중앙값은 주어진 수를 크기 순서대로 늘어 놓았을 때 가장 중앙에 놓인 값이다. 예를 들어 10, 40, 30, 60, 30의 경우, 크기 순서대로 늘어 놓으면 10 30 30 40 60이 되고 따라서 중앙값은 30이 된다. 다섯 개의 자연수가 주어질 때 이들의 평균과 중앙값을 구하는 프로그램을 작성하시오.
입력
첫째 줄부터 다섯 번째 줄까지 한 줄에 하나씩 자연수가 주어진다. 주어지는 자연수는 100 보다 작은 10의 배수이다.
출력
첫째 줄에는 평균을 출력하고, 둘째 줄에는 중앙값을 출력한다. 평균과 중앙값은 모두 자연수이다.
문제 풀이 (100ms)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] arr = new int[5];
int sum = 0;
int avg = 0;
for (int i = 0; i < 5; i++) {
int value = Integer.parseInt(br.readLine());
sum += value;
arr[i] = value;
}
avg = sum / 5;
Arrays.sort(arr);
System.out.println(avg);
System.out.println(arr[2]);
br.close();
}
}
-
-
[baekjoon] 영화감독 숌 (백준 1436 java 풀이)
intro : 숫자가 666을 포함하는지 확인하는게 포인트
백준 문제링크
문제
666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다. 종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 수는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, …. 이다. 따라서, 숌은 첫 번째 영화의 제목은 “세상의 종말 666”, 두 번째 영화의 제목은 “세상의 종말 1666”와 같이 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 수) 와 같다. 숌이 만든 N번째 영화의 제목에 들어간 수를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.
입력
첫째 줄에 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.
문제 풀이 (264ms)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int value = Integer.parseInt(br.readLine());
int count = 0;
int index = 666;
while (value != count) {
if (Integer.toString(index).contains("666")) {
count++;
}
index++;
}
System.out.println(index - 1);
}
}
-
-
-
-
[baekjoon] 알고리즘 수업 - 알고리즘의 수행 시간 6 (백준 24267 java 풀이)
intro : 순열과 조합을 떠올려야 하는 문제인지는 몰랐다.
백준 문제링크
문제
오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.
MenOfPassion(A[], n) {
sum <- 0;
for i <- 1 to n - 2
for j <- i + 1 to n - 1
for k <- j + 1 to n
sum <- sum + A[i] × A[j] × A[k]; # 코드1
return sum;
}
입력
첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.
출력
첫째 줄에 코드1 의 수행 횟수를 출력한다. 둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(br.readLine());
System.out.println((n - 2) * (n - 1) * (n) / 6);
System.out.println(3);
}
}
문제 해석
MenOfPassion 알고리즘을 코드로 표현하면 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(br.readLine());
int count = 0;
for (int i = 1; i <= n - 2; i++) {
for (int j = i + 1; j <= n - 1; j++) {
for (int k = j + 1; k <= n; k++) {
count++;
System.out.println(i + "," + j + "," + k + ",");
}
System.out.println();
}
System.out.println();
}
System.out.println("count = " + count);
}
}
출력결과도 같이 한번 보자.
7
1,2,3,
1,2,4,
1,2,5,
1,2,6,
1,2,7,
1,3,4,
1,3,5,
1,3,6,
1,3,7,
1,4,5,
1,4,6,
1,4,7,
1,5,6,
1,5,7,
1,6,7,
2,3,4,
2,3,5,
2,3,6,
2,3,7,
2,4,5,
2,4,6,
2,4,7,
2,5,6,
2,5,7,
2,6,7,
3,4,5,
3,4,6,
3,4,7,
3,5,6,
3,5,7,
3,6,7,
4,5,6,
4,5,7,
4,6,7,
5,6,7,
count = 35
출력결과를 보니 무언가 떠오르지 않는가? 이건 순열과 조합에서 조합의 경우의 수를 보는 것과 같다. 조합의 경우의 수를 구하는 공식은 다음과 같다.
예제에서 7 이 입력값으로 주어졌을때, 35가 출력값으로 나온 이유는 다음과 같은 계산 과정을 통해 도출 할 수 있다.
계산 과정1
(7 * 6 * 5 * 4 * 3 * 2 * 1)
(4 * 3 * 2 * 1) * (3 * 2 * 1)
계산 과정2
(7 * 6 * 5)
(3 * 2 * 1)
계산 과정3
35
위 과정을 공식으로 도출하면 다음과 같다.
(n * n -1 * n - 2) / 6
여기서 6으로 나누는 이유가 궁금할 수 있는데, 문제에서 주어진 반복문의 depts는 총 3회이다. 결국 7개의 숫자 중에서 3개를 뽑는 조합의 경우의 수를 구하는 조건으로 한정시켜 바라볼 수 있기에 6으로 나눈다.
-
-
[baekjoon] 알고리즘 수업 - 알고리즘의 수행 시간 4 (백준 24265 java 풀이)
intro : 1 ~ N 까지의 합을 구하는 공식은 N(N+1)/2 이다.
백준 문제링크
문제
오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.
MenOfPassion(A[], n) {
sum <- 0;
for i <- 1 to n - 1
for j <- i + 1 to n
sum <- sum + A[i] × A[j]; # 코드1
return sum;
}
입력
첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.
출력
첫째 줄에 코드1 의 수행 횟수를 출력한다. 둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(br.readLine());
System.out.println((n - 1) * n / 2);
System.out.println(2);
}
}
문제 해석
위 문제에서 주어진 MenOfPassion 을 코드로 나타내면 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(br.readLine());
int count = 0;
for (int i = 1; i <= n - 1; i++) {
for (int j = i + 1; j <= n; j++) {
System.out.print(i + "," + j + " ");
count++;
}
System.out.println();
}
System.out.println("count = " + count);
}
}
출력결과도 같이 눈으로 보도록 하겠다.
7
1,2 1,3 1,4 1,5 1,6 1,7
2,3 2,4 2,5 2,6 2,7
3,4 3,5 3,6 3,7
4,5 4,6 4,7
5,6 5,7
6,7
count = 21
결국 우리가 구해야하는 반복횟수는 입력값이 7인 경우 6 + 5 + 4 + 3 + 2 + 1 인 값이다. 이 합 공식은 다음과 같은 공식과 굉장히 유사하다.
1 부터 10 까지의 합을 구하는 공식
공식 : n(n+1)/2
결과 : 55
위 공식을 응용한다면, 반복횟수의 합은 1부터 n-1 까지의 합을 구하는 것과 같기에 (n-1)*n/2 의 다항식을 도출할 수 있다.
-
-
-
-
[baekjoon] 요세푸스 문제 0 (백준 11866 java 풀이)
intro : 문제를 이해하는게 코드를 짜는거보다 어려운거 같다. 문제를 쉽게 해석하자면 앞에있는값을 뒤로 보내고 K번째 값을 순차적으로 뺴는 문제이다.
백준 문제링크
문제
요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4> 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
문제 풀이 (160ms)
import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Deque<Integer> deque = new ArrayDeque<>();
StringTokenizer st = new StringTokenizer(br.readLine());
int forCount1 = Integer.parseInt(st.nextToken());
int forCount2 = Integer.parseInt(st.nextToken());
for (int i = 1; i <= forCount1; i++) deque.addLast(i);
while (!deque.isEmpty()) {
for (int i = 0; i < forCount2 - 1; i++) {
Integer value = deque.removeFirst();
deque.addLast(value);
}
sb.append(deque.removeFirst()).append(", ");
}
bw.write("<" + sb.substring(0, sb.toString().length() - 2) + ">");
bw.flush();
bw.close();
}
}
-
[baekjoon] 균형잡힌 세상 (백준 4949 java 풀이)
intro : 문제에서 주어진 조건 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다. 이 말은 [ 괄호 다음에 ( , ) 가 나오면 안되고 ] 가 나와야 함을 뜻한다.
올바른 경우: [ ( ) ] → 여기서 [ ] 안에 ( )가 있으므로 괄호들이 짝을 이루고 있다.
잘못된 경우: [ ( ] ) → [ 와 ] 사이에 ( 와 )가 있는 것은 유효하지 않으므로 잘못된 괄호 쌍이다.
백준 문제링크
문제
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호(“()”) 와 대괄호(“[]”)로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호(“(“)는 오른쪽 소괄호(“)”)와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호(“[“)는 오른쪽 대괄호(“]”)와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다. 정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.
입력
각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호(“( )”), 대괄호(“[ ]”)로 이루어져 있으며, 온점(“.”)으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 온점 하나(“.”)가 들어온다.
출력
각 줄마다 해당 문자열이 균형을 이루고 있으면 “yes”를, 아니면 “no”를 출력한다.
문제 풀이 (184ms)
import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Deque<<haracter> deque = new ArrayDeque<>();
String input;
while (!(input = br.readLine()).equals(".")) {
for (int i = 0; i < input.length() - 1; i++) {
char ch = input.charAt(i);
if (ch == '[' || ch == '(') {
deque.addLast(ch);
} else if (ch == ']' || ch == ')') {
if (deque.isEmpty()) {
deque.addLast(ch);
break;
} else {
Character peekLast = deque.peekLast();
if (isMatch(peekLast, ch)) deque.removeLast();
else {
deque.addLast(ch);
break;
}
}
}
}
if (deque.isEmpty()) sb.append("yes").append("\n");
else sb.append("no").append("\n");
deque.clear();
}
bw.write(sb.toString());
bw.flush();
bw.close();
}
public static boolean isMatch(char open, char close) {
return (open == '[' && close == ']') || (open == '(' && close == ')');
}
}
-
-
-
-
-
-
[baekjoon] 제로 (백준 10773 java 풀이)
intro : Stack(LIFO)의 push 메소드는 맨앞에 값이 추가되며, pop 메소드를 통해 마지막에 들어온 값이 출력된다, Queue(FIFO)의 offer 메소드는 맨 뒤에 값이 추가되며, pool 메소드를 통해 첫번째로 들어온 값이 출력된다.
백준 문제링크
문제
나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!
입력
첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 “0” 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 “0”일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.
출력
재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 2^31 - 1보다 작거나 같은 정수이다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int forCount = Integer.parseInt(br.readLine());
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < forCount; i++) {
int input = Integer.parseInt(br.readLine());
if (input == 0) {
deque.removeLast();
} else {
deque.addLast(input);
}
}
int sum = 0;
for (Integer value : deque) {
sum += value;
}
System.out.println(sum);
}
}
-
-
[baekjoon] 베르트랑 공준 (백준 4948 java 풀이)
intro : 에라토스테네스의 기법을 통한 소수 찾기방법을 알아보자.
백준 문제링크
문제
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다 입력의 마지막에는 0이 주어진다.
출력
각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.
제한
1 ≤ n ≤ 123,456
문제 풀이1 (제곱근을 활용한 문제풀이 844ms)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int input;
while ((input = Integer.parseInt(br.readLine())) != 0) {
int count = 0;
for (int i = input + 1; i <= input * 2; i++) {
if (isPrime(i)) {
count++;
}
}
sb.append(count).append("\n");
}
System.out.println(sb);
}
public static boolean isPrime(int input) {
if (input <= 1) return false;
if (input <= 3) return true;
if (input % 2 == 0 || input % 3 == 0) return false;
for (int i = 2; i <= Math.sqrt(input); i++) {
if (input % i == 0) {
return false;
}
}
return true;
}
}
문제 풀이2 (에라토스테네스의 체 기법 사용 164ms)
import java.io.*;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
boolean[] isPrime = new boolean[123456 * 2 + 1];
Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i * i <= isPrime.length; i++) {
if (isPrime[i]) {
for (int j = i * i; j < isPrime.length; j += i) {
isPrime[j] = false;
}
}
}
int input;
while ((input = Integer.parseInt(br.readLine())) != 0) {
int count = 0;
for (int i = input + 1; i <= input * 2; i++) {
if (isPrime[i]) {
count++;
}
}
sb.append(count).append("\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
}
-
-
-
-
[baekjoon] 최소공배수 (백준 13241 java 풀이)
intro : 입력값이 10의8승까지도 나온다는 점을 눈여겨 봐야한다.
백준 문제링크
문제
정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 10은 5의 배수이다
(52 = 10) 10은 10의 배수이다 (101 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1,2,4,5,10,20의 배수이다. 2와 5의 최소공배수는 10이고, 그 이유는 2와 5보다 작은 공배수가 없기 때문이다. 10과 20의 최소공배수는 20이다. 5와 3의 최소공배수는 15이다. 당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다.
입력
한 줄에 두 정수 A와 B가 공백으로 분리되어 주어진다. 50%의 입력 중 A와 B는 1000(103)보다 작다. 다른 50%의 입력은 1000보다 크고 100000000(108)보다 작다.
추가: 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오. C/C++에서는 long long int를 사용하고, Java에서는 long을 사용하시오.
출력
A와 B의 최소공배수를 한 줄에 출력한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long first = Long.parseLong(st.nextToken());
long second = Long.parseLong(st.nextToken());
long lcm = first * second / gcd(Math.max(first, second), Math.min(first, second));
System.out.println(lcm);
}
public static long gcd(long a, long b) {
while (b != 0) {
long r = a % b;
a = b;
b = r;
}
return a;
}
}
-
[baekjoon] 최소공배수 (백준 1934 java 풀이)
intro : [최소 공배수 = a * b / 최대 공약수] 라는 공식으로 풀이한다.
백준 문제링크
문제
두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다. 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)
출력
첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int forCount = Integer.parseInt(br.readLine());
for (int i = 0; i < forCount; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int first = Integer.parseInt(st.nextToken());
int second = Integer.parseInt(st.nextToken());
int lcm = first * second / gcd(Math.max(first, second), Math.min(first, second));
System.out.println(lcm);
}
}
public static int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
}
문제 해석
LCM(Least Common Multiple 최소 공배수) 를 구하기 위해서는 주어진 자연수 A,B의 GCD(Greatest Common Divisor 최대 공약수)의 값을 구해서 A * B / GCD 의 값을 도출하는게 포인트이다. 여기서 GCD는 유클리드 호제법으로 풀이하는데, A > B 라는 조건하에 A를 B로 나누어 나머지가 0이 될때까지 반복하여 B값을 구하는 이론이다. 좀 더 설명하면 다음과 같은 순서를 거친다.
A = 18, B = 12
18 % 12 = 나머지 6
12 % 6 = 나머지 0
최대 공약수 : 6
-
[baekjoon] 서로 다른 부분 문자열의 개수 (백준 11478 java 풀이)
intro : 부분 문자열을 구하는 로직이 포인트
백준 문제링크
문제
문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오. 부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다. 예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.
입력
첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.
출력
첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Set<String> uniqueStr = new HashSet<>();
String input = br.readLine();
for (int i = 0; i < input.length(); i++) {
for (int j = i + 1; j <= input.length(); j++) {
String subStr = input.substring(i, j);
uniqueStr.add(subStr);
}
}
System.out.println(uniqueStr.size());
}
}
-
[baekjoon] 대칭 차집합 (백준 1269 java 풀이)
intro : retainAll 메소도는 교집합을 구하는데 적합하며, removeAll 메소드는 차집합을 구하는데 적합하다.
백준 문제링크
문제
자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다. 예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때, A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.
입력
첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다.
출력
첫째 줄에 대칭 차집합의 원소의 개수를 출력한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int firstValue = Integer.parseInt(st.nextToken());
int secondValue = Integer.parseInt(st.nextToken());
Set<String> firstSet = new HashSet<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < firstValue; i++) {
String value = st.nextToken();
firstSet.add(value);
}
Set<String> secondSet = new HashSet<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < secondValue; i++) {
secondSet.add(st.nextToken());
}
Set<String> retainSet = new HashSet<>(firstSet);
retainSet.retainAll(secondSet);
System.out.println((firstSet.size() - retainSet.size()) + (secondSet.size() - retainSet.size()));
}
}
-
-
[baekjoon] 슷자 카드 2 (백준 10816 java 풀이)
intro : map을 통해 문제를 푸는게 포인트인 문제.
백준 문제링크
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int inputCount = Integer.parseInt(br.readLine());
Map<Integer, Integer> inputMap = new HashMap<>();
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < inputCount; i++) {
int input = Integer.parseInt(st.nextToken());
inputMap.put(input, inputMap.getOrDefault(input, 0) + 1);
}
StringBuilder sb = new StringBuilder();
int findCount = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < findCount; i++) {
int findValue = Integer.parseInt(st.nextToken());
sb.append(inputMap.getOrDefault(findValue, 0)).append(" ");
}
System.out.println(sb);
}
}
문제 해석
문제 풀이의 포인트는 map에 존재하는 값인지 확인후 존재한다면 기존값의 value 값에 + 1를 한다는점, 만약에 없는 값이면 0으로 셋팅하여 보관하고 차후 검색하는 키값을 통해 map의 value 값을 StringBuilder를 통해 출력하는 문제 (기존에 풀었던 숫자 카드 문제와 큰 틀은 유사하다)
-
[baekjoon] 나는야 포켓몬 마스터 이다솜 (백준 1620 java 풀이)
intro : 문제가 너무길고 몰입이 안되어서 화가났다.
백준 문제링크
문제
안녕? 내 이름은 이다솜. 나의 꿈은 포켓몬 마스터야. 일단 포켓몬 마스터가 되기 위해선 포켓몬을 한 마리 잡아야겠지? 근처 숲으로 가야겠어. (뚜벅 뚜벅) 얏! 꼬렛이다. 꼬렛? 귀여운데, 나의 첫 포켓몬으로 딱 어울린데? 내가 잡고 말겠어. 가라! 몬스터볼~ (펑!) 헐랭… 왜 안 잡히지?ㅜㅜ 몬스터 볼만 던지면 되는 게 아닌가…ㅜㅠ (터벅터벅) 어? 누구지?
오박사 : 나는 태초마을의 포켓몬 박사 오민식 박사라네. 다솜아, 포켓몬을 잡을 때는, 일단 상대 포켓몬의 체력을 적당히 바닥으로 만들어놓고 몬스터 볼을 던져야 한단다. 자, 내 포켓몬 이상해꽃으로 한번 잡아보렴. 포켓몬의 기술을 쓰는 것을 보고 포켓몬을 줄지 안줄지 결정을 하겠네. 자 한번 해보아라. 다솜아.
이다솜 : 이상해꽃이라…음.. 꽃이니깐 왠지 햇빛을 받아서 공격을 할 것 같은데… 음… 이상해꽃! 햇빛공격!!!
(꼬렛이 이상해꽃에게 공격을 받아 체력이 25 감소했다.) 가라! 몬스터 볼!!! (꼬렛을 잡았습니다.) 야호! 신난다. 꼬렛을 잡았다.
오박사 : 오우!! 방금 쓴 공격은 솔라빔이라고 하네.. 어떻게 공격을 한 건가? 솔라빔이란 공격에 대해서 공부를 한 건가?
이다솜 : 꽃이니깐 왠지 햇빛을 제대로 받으면 광합성을 해서 음.. 그냥 그럴 것 같아서요 ☞☜
오박사 : 다른 아이들은 넝쿨채찍이나, 나뭇잎 공격을 하는데, 다솜이는 역시 뭔가 다르구나. 그럼 나와 함께 연구소로 가자꾸나. 내가 포켓몬을 한 마리 줄 테니, 너의 꿈을 펼쳐보아라. 꿈은 이루어진단다.
이다솜 : 네! 오박사님, 고마워요.ㅜㅜ
오박사 : 가자. 나의 연구소는 너의 옆집의 아랫집이란다. 같이 가도록하자. 지금 포켓몬을 주마.
이다솜 : 네. 야호!!
오영식 : 어? 오박사님 얘는 누구인가요?
오박사 : 얘는 너의 라이벌이 될 친구 이다솜이라고 하네. 자, 포켓몬을 한 마리 골라보도록 해봐라 다솜아. 레이디퍼스트 네가 먼저 골라봐라.
이다솜 : 저는 생각해둔 포켓몬이 있어요. 피카츄 골라도 될까요?
오박사 : 그래 여기 피카츄가 한 마리 있단다. 피카츄를 가져가거라.
오영식 : 그럼 저는 이브이를 가져가겠어요. 그럼 나중에 보자 이다솜.
이다솜 : 그럼 꼬렛을 다시 잡으러 가야겠다. 영식아, 그리고 민식박사님 빠잉!
이다솜 : 피카츄 공격!
가라 몬스터 볼!
이다솜 : 야호! 신난다. 꼬렛을 잡았다!!!!!
이다솜 : 그럼! 일단 사천왕을 이기고 오겠어!
이다솜 : 여기가 사천왕과 대결하려면 가야하는 곳인가..
경비원 : 사천왕과 대결을 하려면, 마을의 체육관 리더를 이겨서 배지를 8개를 모아야 한다네… 배지를 모아서 오도록 하게
이다솜 : 잉ㅠㅜ… 그럼 배지부터 모아야 하는구나ㅠㅜㅠㅜ 나쁘당 그냥 좀 봐주지..
<1 년 후>
그동안의 줄거리 : 이다솜은 일단 상록 숲의 체육관 리더에게 도전을 했다. 하지만 상록숲 체육관의 리더는 실종된 상태. 따라서 회색마을부터 도전하기로 했다. 체육관의 리더를 이기면서, 로켓단을 해체시키기도 하고, 여러 가지 사건도 있었다. 결국 전설의 포켓몬도 잡고, 이제 사천왕을 이기려고 도전하기로 했다. 사천왕은 모두 가볍게 이기고, 이제 마지막 라이벌 오!영!식! 이다.
오영식 : 훗. 1년 전의 그 이다솜이 사천왕을 이기고 현재 포켓몬 마스터인 나에게 덤벼? 어디 한번 덤벼보시지.
이다솜 : 헐랭… 나를 우습게보네…. 한번 두고 보시지! 그럼 대결이닷!
이다솜 : 휴… 이겼다.
오영식 : 내가 지다니 분하다. ㅜㅜ
오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네.
입력
첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어.
둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음… 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 아참! 일부 포켓몬은 마지막 문자만 대문자일 수도 있어. 포켓몬 이름의 최대 길이는 20, 최소 길이는 2야. 그 다음 줄부터 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어와. 문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, 숫자로만 들어오면, 포켓몬 번호에 해당하는 문자를 출력해야해. 입력으로 들어오는 숫자는 반드시 1보다 크거나 같고, N보다 작거나 같고, 입력으로 들어오는 문자는 반드시 도감에 있는 포켓몬의 이름만 주어져. 그럼 화이팅!!!
출력
첫째 줄부터 차례대로 M개의 줄에 각각의 문제에 대한 답을 말해줬으면 좋겠어!!!. 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 돼. 그럼 땡큐~ 이게 오박사님이 나에게 새로 주시려고 하는 도감이야. 너무 가지고 싶다ㅠㅜ. 꼭 만점을 받아줬으면 좋겠어!! 파이팅!!!
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int inputCount = Integer.parseInt(st.nextToken());
int findCount = Integer.parseInt(st.nextToken());
Map<String, Integer> inputStringMap = new HashMap<>();
Map<Integer, String> inputIntMap = new HashMap<>();
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= inputCount + findCount; i++) {
if (i <= inputCount) {
String input = br.readLine();
inputStringMap.put(input, i);
inputIntMap.put(i, input);
} else {
String findValue = br.readLine();
try {
int index = Integer.parseInt(findValue);
String name = inputIntMap.get(index);
sb.append(name).append("\n");
} catch (NumberFormatException e) {
Integer index = inputStringMap.get(findValue);
sb.append(index).append("\n");
}
}
}
System.out.println(sb);
}
}
문제 해석
문제의 내용을 정리하면 사실 간단하다. 입력값으로 들어오는 첫줄은 공백으로 구분되어있는데 공백을 기준으로 첫번째 값은 입력되는 입력받아야 할 반복문 총 횟수, 두번쨰 값은 질문 할 반복 횟수 라고 볼 수 있다. 그래서 해당 값만큼 반복문으로 입력을 받는데, 시간복잡도를 고려하여 map으로 변수를 구성한다. 그 이유는 문자열로 값이 들어오면 정수로 출력해줘야 하고, 정수로 값이 들어오면 문자열로 값을 출력해줘여 하기 때문에 map이 가장 적합한 자료구조의 타입으로 이 문제에서는 사용 될 수 있다.
추가적으로 입력되는 값이 정수인지 문자인지 판단하는 부분은 instanceof를 통해 검사할수 없다. br.readline은 string 타입으로 반환값이 고정이기 때문에 검사할수 없으니 try catch 구조로 Integer 타입으로 변환하였을때, exceptio이 발생하는지 여부에 따라 문자열인지 정수인지 판단하여 분기 로직을 구성한다. 출력은 StringBuilder를 통해 한번에 출력하는 것이 포인트, System.out.println은 병목현상을 유발하는 주된 원인이기 때문에 항상 조심해야한다. (시간적으로 거의 두배 이상의 차이가 나기도 한다.)
-
[baekjoon] 회사에 있는 사람 (백준 7785 java 풀이)
intro : 자료구조를 많이 알면 알수록 문제풀이는 쉬워진다. 또한 시간 복잡도의 계산능력이 좋아지는거 같다.
백준 문제링크
문제
상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 “enter”나 “leave”가 주어진다. “enter”인 경우는 출근, “leave”인 경우는 퇴근이다. 회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.
출력
현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.
문제 풀이1 (잘못된 풀이 - 런타임 에러 (ConcurrentModification))
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Map<String, String> map = new HashMap<>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int forCount = Integer.parseInt(br.readLine());
for (int i = 0; i < forCount; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
map.put(st.nextToken(), st.nextToken());
}
for (String key : map.keySet()) {
String status = map.get(key);
if (!status.equals("enter")) {
map.remove(key);
}
}
TreeSet<String> treeSet = new TreeSet<>(map.keySet());
Iterator<String> iterator = treeSet.descendingIterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
문제 풀이2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Set<String> set = new HashSet<>();
int forCount = Integer.parseInt(br.readLine());
for (int i = 0; i < forCount; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String name = st.nextToken();
String status = st.nextToken();
if (status.equals("enter")) {
set.add(name);
} else {
set.remove(name);
}
}
StringBuilder sb = new StringBuilder();
TreeSet<String> sortSet = new TreeSet<>(set);
Iterator<String> iterator = sortSet.descendingIterator();
while (iterator.hasNext()) {
sb.append(iterator.next());
sb.append("\n");
}
System.out.println(sb);
}
}
문제해석
문제를 보고 떠오른 아이디어는, 입출입 값을 map이나 set을 통해 관리하고 leave를 한 인원은 제외한다음, Collection 끼리의 타입 변환은 가능하기에 정렬 기능을 제공하는 자료구조인 TreeSet으로 변환 후, 역순으로 값을 출력하자가 생각이었다. (list로도 변환할수 있고, list의 역순 출력도 고려해 보았다.)
이때 자료구조는 map이 더 나아보여서 map으로 문제를 풀어보았는데, remove를 하는 시점에서 Concurrent Modification Exception이 발생하였으며, map에서는 순회하면서 remove를 하는게 예외를 발생시킨다는 점을 인지하게 되었다. 다만 set은 map과 내부 구조가 달라, 순회하면서 remove를 하여도 예외가 발생하지 않아 문제풀이 2번 방식으로 문제를 풀 수 있다는것이 포인트가 될 수 있다.
또한 시간적으로 단축시켜야 하기에 병목현상이 발생할수 있는 System.out.println을 반복문에서 사용하지않고, StringBuilder를 통해 문자열을 구성한 후, 한번에 출력하는 형식으로 로직을 구성하였다. StringBuilder를 사용하기전에는 1초가 걸리는 로직이, 후에 0.5초로 엄청난 속도 개선이 이루어 졌다.
-
-
[baekjoon] 숫자 카드 (백준 10815 java 풀이)
intro : Map을 사용할지, Set을 사용할지 고민해 보는게 좋다.
백준 문제링크
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000 000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.
문제 풀이 1 (Map을 이용한 문제풀이)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
br.readLine();
String[] getCartSplit = br.readLine().split(" ");
int findCount = Integer.parseInt(br.readLine());
int[] result = new int[findCount];
String[] findCardSplit = br.readLine().split(" ");
Map<Integer, Boolean> cardMap = new HashMap<>();
Map<Integer, Boolean> findMap = new LinkedHashMap<>();
for (String getCard : getCartSplit) cardMap.put(Integer.parseInt(getCard), true);
for (String findCard : findCardSplit) findMap.put(Integer.parseInt(findCard), true);
int index = 0;
for (Integer findKey : findMap.keySet()) {
Boolean check = cardMap.getOrDefault(findKey, false);
if (check) {
result[index] = 1;
}
index++;
}
StringBuilder sb = new StringBuilder();
for (int value : result) {
sb.append(value).append(" ");
}
System.out.println(sb);
}
}
문제 풀이 2 (Set을 이용한 문제풀이)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int getCardCount = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
Set<String> getCardSet = new HashSet<>();
for (int i = 0; i < getCardCount; i++) getCardSet.add(st.nextToken());
StringBuilder sb = new StringBuilder();
int findCardCount = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < findCardCount; i++) {
boolean check = getCardSet.contains(st.nextToken());
if (check) {
sb.append("1").append(" ");
} else {
sb.append("0").append(" ");
}
}
System.out.println(sb);
}
}
문제 해석
주어진 조건을 잘 살펴보면 N(1 ≤ N ≤ 500,000), M(1 ≤ M ≤ 500,000) 즉 N 과 M의 길이가 각각 50만씩, 이중 반복문으로 카드의 존재여부를 확인하고자 하는 로직을 구성한다면 ? 단순히 생각했을때만 해도 2500억 번의 연산횟수가 시도된다.(물론 정확하게는 아니고 대략적인 값이다.)
1억번당 1초의 연산 속도를 가정한다면 이 문제는 단순 반복문으로 풀 수 있는 문제가 아닌것을 눈치 해야한다. 그렇다면 시간 복잡도가 1에 수렴하면서 빠르게 존재여부를 확인할 수 있는 자료구조는 무엇이 있을까 ?
바로 Hash 자료구조이다. 보통 Hash 자료구조에는 크게 두가지가 있는데 Map 과 Set이 존재한다. Map.get() 메소드는 1의 시간복잡도에 수렴하며, Set.contains() 메소드 또한 1의 시간복잡도에 수렴한다 (보통 그렇다.) 이 포인트를 잘 생각하여 상근이가 가지고 있는 카드가 숫자카드에 존재하는 카드인지 체크하는 로직을 구성하는것이 문제 풀이의 옳은 방법이 된다.
초기 문제풀이1번에서는 LinkedHashMap을 통해 자료구조를 구성해서 문제풀이를 시도했는데, 문제를 풀고나니 굳이 순서를 지키면서 변수를 구성해야 될 필요도 없다는 것을 알게되었으며, 문제 조건에서 주어진 값이 중복된 값이 없다고 하였으니 Map이 아닌 Set을 통해 풀이를 구성하는게 이 문제에 더 적합하다고 생각된다.
-
[baekjoon] 세 막대 (백준 14215 java 풀이)
intro : 삼각형의 가장 큰 변의 길이를 줄여가면서 삼각형의 조건이 만족하는지 확인하고, 가장 처음으로 만족하는 변으 길이가 되었을때 둘레의 길이를 출력하는게 포인트
백준 문제링크
문제
영선이는 길이가 a, b, c인 세 막대를 가지고 있고, 각 막대의 길이를 마음대로 줄일 수 있다. 영선이는 세 막대를 이용해서 아래 조건을 만족하는 삼각형을 만들려고 한다. 각 막대의 길이는 양의 정수이다 세 막대를 이용해서 넓이가 양수인 삼각형을 만들 수 있어야 한다. 삼각형의 둘레를 최대로 해야 한다. a, b, c가 주어졌을 때, 만들 수 있는 가장 큰 둘레를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 a, b, c (1 ≤ a, b, c ≤ 100)가 주어진다.
출력
첫째 줄에 만들 수 있는 가장 큰 삼각형의 둘레를 출력한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int value1 = Integer.parseInt(st.nextToken());
int value2 = Integer.parseInt(st.nextToken());
int value3 = Integer.parseInt(st.nextToken());
int[] arr = new int[]{value1, value2, value3};
if (isTriangleCheck(arr)) {
System.out.println(value1 + value2 + value3);
} else {
int maxIndex = findMaxIndex(arr);
for (int i = arr[maxIndex] - 1; i >= 0; i--) {
arr[maxIndex] = i;
if (isTriangleCheck(arr, maxIndex)) {
System.out.println(arr[0] + arr[1] + arr[2]);
return;
}
}
}
}
public static boolean isTriangleCheck(int[] arr, int maxIndex) {
int remainSum = 0;
for (int i = 0; i < arr.length; i++) {
if (i != maxIndex) {
remainSum += arr[i];
}
}
return arr[maxIndex] < remainSum;
}
public static boolean isTriangleCheck(int[] arr) {
int maxIndex = findMaxIndex(arr);
return isTriangleCheck(arr, maxIndex);
}
public static int findMaxIndex(int[] arr) {
int maxValue = Integer.MIN_VALUE;
int maxIndex = -1;
for (int i = 0; i < arr.length; i++) {
if (maxValue < arr[i]) {
maxValue = arr[i];
maxIndex = i;
}
}
return maxIndex;
}
}
-
[baekjoon] 삼각형과 세 변 (백준 5073 java 풀이)
intro : 삼각형의 조건을 만족하는 메소드를 구성하는데 쉽게풀려다가 오래걸렸는데, 가장원초적인 방법이 가장 최적화된 방법인 것 같다.
백준 문제링크
문제
삼각형의 세 변의 길이가 주어질 때 변의 길이에 따라 다음과 같이 정의한다.
Equilateral : 세 변의 길이가 모두 같은 경우
Isosceles : 두 변의 길이만 같은 경우
Scalene : 세 변의 길이가 모두 다른 경우
단 주어진 세 변의 길이가 삼각형의 조건을 만족하지 못하는 경우에는 “Invalid” 를 출력한다. 예를 들어 6, 3, 2가 이 경우에 해당한다. 가장 긴 변의 길이보다 나머지 두 변의 길이의 합이 길지 않으면 삼각형의 조건을 만족하지 못한다. 세 변의 길이가 주어질 때 위 정의에 따른 결과를 출력하시오.
입력
각 줄에는 1,000을 넘지 않는 양의 정수 3개가 입력된다. 마지막 줄은 0 0 0이며 이 줄은 계산하지 않는다.
출력
각 입력에 맞는 결과 (Equilateral, Isosceles, Scalene, Invalid) 를 출력하시오.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
while (!(str = br.readLine()).equals("0 0 0")) {
StringTokenizer st = new StringTokenizer(str);
int value1 = Integer.parseInt(st.nextToken());
int value2 = Integer.parseInt(st.nextToken());
int value3 = Integer.parseInt(st.nextToken());
if (isTriangleCheck(value1, value2, value3)) {
if ((value1 == value2) && (value2 == value3)) {
System.out.println("Equilateral");
} else if ((value1 != value2) && (value1 != value3) && (value2 != value3)) {
System.out.println("Scalene");
} else {
System.out.println("Isosceles");
}
}
}
}
public static boolean isTriangleCheck(int value1, int value2, int value3) {
int[] arr = new int[]{value1, value2, value3};
int maxValue = Integer.MIN_VALUE;
int maxIndex = -1;
for (int i = 0; i < arr.length; i++) {
if (maxValue < arr[i]) {
maxValue = arr[i];
maxIndex = i;
}
}
int remainSum = 0;
for (int i = 0; i < arr.length; i++) {
if (i != maxIndex) {
remainSum += arr[i];
}
}
if (arr[maxIndex] < remainSum) {
return true;
} else {
System.out.println("Invalid");
return false;
}
}
}
-
-
[baekjoon] 대지 (백준 9063 java 풀이)
intro : min max를 구하는 방법은 생각보다 간단하니 꼭 숙지하자
백준 문제링크
문제
임씨는 1950 년 한국전쟁으로 많은 손해를 본 사람들 중 하나다. 전쟁 통에 손해보지 않은 사람이 어디 있을까 만은 그는 6.25 가 일어나기 전만 해도 충청도 지방에 넓은 대지를 소유한 큰 부자였다. 전쟁이 나자 임씨는 땅문서와 값 나가는 것들만 챙겨서 일본으로 피난을 가지만 피난 중에 그만 땅문서를 잃어버리고 만다. 전쟁이 끝난 후에 임씨의 땅은 이미 다른 사람들의 논밭이 되어 있었고, 임씨는 땅을 되찾으려 했지만 문서가 없으니 생떼 쓰는 것과 다를 바 없었다. 이러다가 임씨는 길바닥에 나앉게 생겼다.
이때, 임씨에게 좋은 생각이 떠올랐으니 바로 자신이 습관처럼 땅 깊숙이 뭔가 표식을 해놓았던 사실이다. 임씨는 한적할 때마다 자신의 논밭을 거닐다가 땅속 깊은 곳에 자신의 이름이 씌어진 옥구슬을 묻어놓았던 것이다. 즉, 어떤 지점에서 그의 이름이 적힌 옥구슬이 나온다면 그 지점은 예전에 임씨의 땅이었다는 것을 증명하는 것이다.
임씨는 즉시 민사소송을 통해 자신의 땅을 찾고자 했고 논리적인 근거를 들어 옥구슬이 나오는 지점이 원래 자신의 땅의 한 지점이었다는 것을 주장하여 결국 담당판사를 설득하는 데에 성공하였다. 담당판사는 다음과 같은 판결을 내렸다. “ 6.25 이전의 개인소유 대지들은 99%가 남북, 동서 방향으로 평행한 직사각형 모양이었으므로, 임씨의 이름이 새겨진 옥구슬이 나오는 모든 지점을 포함하는 가장 작은 남북, 동서 방향으로 평행한 변을 갖는 직사각형의 대지를 임씨의 소유로 인정한다.” 임씨는 많은 손해를 보는 셈이지만 더 이상을 요구할 만한 근거가 없었기 때문에 이 판결을 따르기로 했다.
임씨의 이름이 새겨진 옥구슬의 위치 N 개가 주어질 때에, 임씨에게 돌아갈 대지의 넓이를 계산하는 프로그램을 작성하시오. 단, 옥구슬의 위치는 2 차원 정수 좌표로 주어지고 옥구슬은 같은 위치에 여러 개가 발견될 수도 있으며, x 축의 양의방향을 동쪽, y 축의 양의방향을 북쪽이라고 가정한다.
예를 들어 위와 같이 (2, 1), (3, 2), (5, 2), (3, 4) 네 점에서 옥구슬을 발견하였다면, 임씨에게 돌아갈 대지는 (2, 1), (5, 1), (2, 4), (5, 4)를 네 꼭짓점으로 하는 직사각형이며, 넓이는 (5 - 2) × (4 - 1) = 9 가 된다.
입력
첫째 줄에는 점의 개수 N (1 ≤ N ≤ 100,000) 이 주어진다. 이어지는 N 줄에는 각 점의 좌표가 두 개의 정수로 한 줄에 하나씩 주어진다. 각각의 좌표는 -10,000 이상 10,000 이하의 정수이다.
출력
첫째 줄에 N 개의 점을 둘러싸는 최소 크기의 직사각형의 넓이를 출력하시오.
문제 풀이 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int count = Integer.parseInt(br.readLine());
if (count == 1) {
System.out.println(0);
return;
}
int minX = Integer.MAX_VALUE;
int maxX = Integer.MIN_VALUE;
int minY = Integer.MAX_VALUE;
int maxY = Integer.MIN_VALUE;
for (int i = 0; i < count; i++) {
String[] splitStr = br.readLine().split(" ");
int x = Integer.parseInt(splitStr[0]);
int y = Integer.parseInt(splitStr[1]);
if (x < minX) minX = x;
if (x > maxX) maxX = x;
if (y < minY) minY = y;
if (y > maxY) maxY = y;
}
System.out.println((maxX - minX) * (maxY - minY));
}
}
문제 풀이 2 (stream 풀이방식은 성능저하가 있을수있다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int count = Integer.parseInt(br.readLine());
if (count == 1) {
System.out.println(0);
return;
}
int[] xArray = new int[count];
int[] yArray = new int[count];
for (int i = 0; i < count; i++) {
String[] splitStr = br.readLine().split(" ");
xArray[i] = Integer.parseInt(splitStr[0]);
yArray[i] = Integer.parseInt(splitStr[1]);
}
int minX = Arrays.stream(xArray).min().getAsInt();
int minY = Arrays.stream(yArray).min().getAsInt();
int maxX = Arrays.stream(xArray).max().getAsInt();
int maxY = Arrays.stream(yArray).max().getAsInt();
System.out.println((maxX - minX) * (maxY - minY));
}
}
-
-
-
[baekjoon] 직사각형에서 탈출 (백준 1085 java 풀이)
intro : Math 클래스의 min 메소드를 활용해서 로직 구성이 포인트
백준 문제링크
문제
한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 x, y, w, h가 주어진다.
출력
첫째 줄에 문제의 정답을 출력한다.
제한
1 ≤ w, h ≤ 1,000
1 ≤ x ≤ w-1
1 ≤ y ≤ h-1
x, y, w, h는 정수
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int value1 = Integer.parseInt(st.nextToken());
int value2 = Integer.parseInt(st.nextToken());
int value3 = Integer.parseInt(st.nextToken());
int value4 = Integer.parseInt(st.nextToken());
int[] array = new int[4];
array[0] = value1;
array[1] = value2;
array[2] = Math.abs(value3 - value1);
array[3] = Math.abs(value4 - value2);
System.out.println(Math.min(array[0], Math.min(array[1], Math.min(array[2], array[3]))));
}
}
-
-
-
-
-
-
-
[baekjoon] 소수 (백준 2581 java 풀이)
intro : 소수를 찾고 소수의 합을 구하고, 첫번째 소수는 boolean 타입의 flag 값으로 체크하여 로직을 구성하는게 포인트
백준 문제링크
문제
자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.
입력
입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다. M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.
출력
M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
boolean isFirstPrice = false;
int firstPrice = 0;
int primeSum = 0;
int first = Integer.parseInt(br.readLine());
int second = Integer.parseInt(br.readLine());
for (int i = first; i <= second; i++) {
if (isPrime(i)) {
if (!isFirstPrice) {
firstPrice = i;
isFirstPrice = true;
}
primeSum += i;
}
}
if (primeSum == 0) {
System.out.println(-1);
} else {
System.out.println(primeSum);
System.out.println(firstPrice);
}
}
public static boolean isPrime(int number) {
if (number == 1) {
return false;
} else {
for (int i = 2; i < number; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
}
}
-
-
-
-
-
[baekjoon] 세탁소 사장 동혁 (백준 2720 java 풀이)
intro : 1달러가 100센트인점을 생각한다면, 주어지는 값이 센트단위로 들어오니, 각 값을 25,10,5,1 로 나누어 몫과 나머지를 통해 로직을 구성하는게 포인트
백준 문제링크
문제
미국으로 유학간 동혁이는 세탁소를 운영하고 있다. 동혁이는 최근에 아르바이트로 고등학생 리암을 채용했다.동혁이는 리암에게 실망했다. 리암은 거스름돈을 주는 것을 자꾸 실수한다. 심지어 $0.5달러를 줘야하는 경우에 거스름돈으로 $5달러를 주는것이다! 어쩔수 없이 뛰어난 코딩 실력을 발휘해 리암을 도와주는 프로그램을 작성하려고 하지만, 디아블로를 하느라 코딩할 시간이 없어서 이 문제를 읽고 있는 여러분이 대신 해주어야 한다.거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(Quarter, $0.25)의 개수, 다임(Dime, $0.10)의 개수, 니켈(Nickel, $0.05)의 개수, 페니(Penny, $0.01)의 개수를 구하는 프로그램을 작성하시오. 거스름돈은 항상 $5.00 이하이고, 손님이 받는 동전의 개수를 최소로 하려고 한다. 예를 들어, $1.24를 거슬러 주어야 한다면, 손님은 4쿼터, 2다임, 0니켈, 4페니를 받게 된다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 거스름돈 C를 나타내는 정수 하나로 이루어져 있다. C의 단위는 센트이다. (1달러 = 100센트) (1<=C<=500)
출력
각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int forCount = Integer.parseInt(br.readLine());
for (int i = 0; i < forCount; i++) {
int[] result = new int[4];
double doubleValue = Double.parseDouble(br.readLine());
int intValue = (int) doubleValue / 25;
result[0] = intValue;
doubleValue %= 25;
if (doubleValue != 0) {
intValue = (int) doubleValue / 10;
result[1] = intValue;
doubleValue %= 10;
if (doubleValue != 0) {
intValue = (int) doubleValue / 5;
result[2] = intValue;
doubleValue %= 5;
if (doubleValue != 0) {
result[3] = (int) doubleValue;
}
}
}
for (int value : result) {
System.out.print(value + " ");
}
System.out.println();
}
}
}
-
-
[baekjoon] 세로읽기 (백준 10798 java 풀이)
intro : 세로로 읽는법은 단순히 열을 기준으로 반복문을 구성하여 1열 에대한 반복문 처리후, 2열에 대한 반복문 처리를 반복한다.
백준 문제링크
문제
아직 글을 모르는 영석이가 벽에 걸린 칠판에 자석이 붙어있는 글자들을 붙이는 장난감을 가지고 놀고 있다. 이 장난감에 있는 글자들은 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’이다.영석이는 칠판에 글자들을 수평으로 일렬로 붙여서 단어를 만든다. 다시 그 아래쪽에 글자들을 붙여서 또 다른 단어를 만든다. 이런 식으로 다섯 개의 단어를 만든다. 아래 그림 1은 영석이가 칠판에 붙여 만든 단어들의 예이다.
A A B C D D
a f z z
0 9 1 2 1
a 8 E W g 6
P 5 h 3 k x
<그림 1>
한 줄의 단어는 글자들을 빈칸 없이 연속으로 나열해서 최대 15개의 글자들로 이루어진다. 또한 만들어진 다섯 개의 단어들의 글자 개수는 서로 다를 수 있다. 심심해진 영석이는 칠판에 만들어진 다섯 개의 단어를 세로로 읽으려 한다. 세로로 읽을 때, 각 단어의 첫 번째 글자들을 위에서 아래로 세로로 읽는다. 다음에 두 번째 글자들을 세로로 읽는다. 이런 식으로 왼쪽에서 오른쪽으로 한 자리씩 이동 하면서 동일한 자리의 글자들을 세로로 읽어 나간다. 위의 그림 1의 다섯 번째 자리를 보면 두 번째 줄의 다섯 번째 자리의 글자는 없다. 이런 경우처럼 세로로 읽을 때 해당 자리의 글자가 없으면, 읽지 않고 그 다음 글자를 계속 읽는다. 그림 1의 다섯 번째 자리를 세로로 읽으면 D1gk로 읽는다. 그림 1에서 영석이가 세로로 읽은 순서대로 글자들을 공백 없이 출력하면 다음과 같다 ‘Aa0aPAf985Bz1EhCz2W3D1gkD6x’ 칠판에 붙여진 단어들이 주어질 때, 영석이가 세로로 읽은 순서대로 글자들을 출력하는 프로그램을 작성하시오.
입력
총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’ 중 하나이다. 각 줄의 시작과 마지막에 빈칸은 없다.
출력
영석이가 세로로 읽은 순서대로 글자들을 출력한다. 이때, 글자들을 공백 없이 연속해서 출력한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
String[][] result = new String[5][15];
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < 5; i++) {
String input = br.readLine();
String[] split = input.split("");
for (int j = 0; j < split.length; j++) {
result[i][j] = split[j];
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 15; i++) {
for (int j = 0; j < 5; j++) {
String str = result[j][i];
if (str != null) {
sb.append(str);
}
}
}
System.out.println(sb);
}
}
-
-
-
[baekjoon] 너의 평점은 (백준 25206 java 풀이)
intro : P학점에 대한 처리는 미처리 한다는 점을 주의해야하며, Map을 통해 학점의 대한 점수를 관리하는 방법이 포인트
백준 문제링크
문제
인하대학교 컴퓨터공학과를 졸업하기 위해서는, 전공평점이 3.3 이상이거나 졸업고사를 통과해야 한다. 그런데 아뿔싸, 치훈이는 깜빡하고 졸업고사를 응시하지 않았다는 사실을 깨달았다! 치훈이의 전공평점을 계산해주는 프로그램을 작성해보자. 전공평점은 전공과목별 (학점 × 과목평점)의 합을 학점의 총합으로 나눈 값이다 인하대학교 컴퓨터공학과의 등급에 따른 과목평점은 다음 표와 같다.
제목
내용
A+
4.5
A0
4.0
B+
3.5
B0
3.0
C+
2.5
C0
2.0
D+
1.5
D0
1.0
F
0.0
P/F 과목의 경우 등급이 P또는 F로 표시되는데, 등급이 P인 과목은 계산에서 제외해야 한다. 과연 치훈이는 무사히 졸업할 수 있을까?
입력
20줄에 걸쳐 치훈이가 수강한 전공과목의 과목명, 학점, 등급이 공백으로 구분되어 주어진다.
출력
치훈이의 전공평점을 출력한다. 정답과의 절대오차 또는 상대오차가 $10^-4$ 이하이면 정답으로 인정한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) throws IOException {
Map<String, Double> gradeMap = new HashMap<>();
gradeMap.put("A+", 4.5);
gradeMap.put("A0", 4.0);
gradeMap.put("B+", 3.5);
gradeMap.put("B0", 3.0);
gradeMap.put("C+", 2.5);
gradeMap.put("C0", 2.0);
gradeMap.put("D+", 1.5);
gradeMap.put("D0", 1.0);
gradeMap.put("F", 0.0);
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
double specificCredit = 0;
double totalCredit = 0;
for (int i = 0; i < 20; i++) {
String[] splitStr = br.readLine().split(" ");
double credit = Double.parseDouble(splitStr[1]);
String grade = splitStr[2];
if (!grade.equals("P")) {
totalCredit += credit;
specificCredit += (gradeMap.get(grade) * credit);
}
}
System.out.println(specificCredit / totalCredit);
}
}
-
[baekjoon] 그룹 단어 체커 (백준 1316 java 풀이)
intro : char 타입의 변수 - char 타입의 변수를 통해 int형을 반환한다는 점, 기존에 출력되었던 단어인지 확인하기위한 boolean 타입의 배열이 포인트
백준 문제링크
문제
그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.
출력
첫째 줄에 그룹 단어의 개수를 출력한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int groupWordCount = 0;
for (int i = 0; i < n; i++) {
String word = br.readLine();
if (isGroupWord(word)) {
groupWordCount++;
}
}
System.out.println(groupWordCount);
}
public static boolean isGroupWord(String word) {
boolean[] visited = new boolean[26];
char prevChar = word.charAt(0);
visited[prevChar - 'a'] = true;
for (int i = 1; i < word.length(); i++) {
char currentChar = word.charAt(i);
if (prevChar != currentChar) {
if (visited[currentChar - 'a']) {
return false;
}
visited[prevChar - 'a'] = true;
}
prevChar = currentChar;
}
return true;
}
}
-
[baekjoon] 크로아티아 알파벳 (백준 2941 java 풀이)
intro : replace 메소드를 통해 단순히 크로아티아의 문자를 “ “처리하고 나중에 문자열 길이를 계산하는게 포인트
백준 문제링크
문제
예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 예를 들어, ljes=njak은 크로아티아 알파벳 6개(lj, e, š, nj, a, k)로 이루어져 있다. 단어가 주어졌을 때, 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다. dž는 무조건 하나의 알파벳으로 쓰이고, d와 ž가 분리된 것으로 보지 않는다. lj와 nj도 마찬가지이다. 위 목록에 없는 알파벳은 한 글자씩 센다.
입력
첫째 줄에 최대 100글자의 단어가 주어진다. 알파벳 소문자와 ‘-‘, ‘=’로만 이루어져 있다.단어는 크로아티아 알파벳으로 이루어져 있다. 문제 설명의 표에 나와있는 알파벳은 변경된 형태로 입력된다.
출력
입력으로 주어진 단어가 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
String[] strArray = new String[]{"c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z="};
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
for (String str : strArray) {
input = input.replaceAll(str, " ");
}
System.out.println(input.length());
}
}
-
-
[baekjoon] 바구니 뒤집기 (백준 10811 java 풀이)
intro : 지정된 범위의 값을 어떻게 역순으로 변환할것인지 로직을 구성하는게 포인트, 첫번쨰값과 마지막값을 바꾼다는 개념에서 시작해야한다는 점.
백준 문제링크
문제
도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다.바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, …, 가장 오른쪽 바구니를 N번째 바구니라고 부른다. 도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다. 도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고, 그 범위에 들어있는 바구니의 순서를 역순으로 만든다. 바구니의 순서를 어떻게 바꿀지 주어졌을 때, M번 바구니의 순서를 역순으로 만든 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다. 둘째 줄부터 M개의 줄에는 바구니의 순서를 역순으로 만드는 방법이 주어진다. 방법은 i j로 나타내고, 왼쪽으로부터 i번째 바구니부터 j번째 바구니의 순서를 역순으로 만든다는 뜻이다. (1 ≤ i ≤ j ≤ N) 도현이는 입력으로 주어진 순서대로 바구니의 순서를 바꾼다.
출력
모든 순서를 바꾼 다음에, 가장 왼쪽에 있는 바구니부터 바구니에 적혀있는 순서를 공백으로 구분해 출력한다.
문제 풀이
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
String[] inputSplit = input.split(" ");
int arrLength = Integer.parseInt(inputSplit[0]);
int forCount = Integer.parseInt(inputSplit[1]);
int[] result = new int[arrLength];
for (int i = 0; i < arrLength; i++) {
result[i] = i + 1;
}
for (int i = 0; i < forCount; i++) {
String line = sc.nextLine();
String[] lineSplit = line.split(" ");
int firstIndex = Integer.parseInt(lineSplit[0]) - 1;
int secondIndex = Integer.parseInt(lineSplit[1]) - 1;
for (int j = firstIndex; j <= secondIndex; j++) {
int temp = result[j];
result[j] = result[secondIndex];
result[secondIndex] = temp;
secondIndex--;
}
}
sc.close();
for (int m : result) {
System.out.print(m + " ");
}
}
}
-
-
-
-
[baekjoon] 킹, 퀸, 룩, 비숍, 나이트, 폰 (백준 3003 java 풀이)
intro : 존재해야하는 체스말의 값을 배열로 선언하고, 입력받은 값과 비교해서 -+ 값을 구하는 문제
백준 문제링크
문제
동혁이는 오래된 창고를 뒤지다가 낡은 체스판과 피스를 발견했다. 체스판의 먼지를 털어내고 걸레로 닦으니 그럭저럭 쓸만한 체스판이 되었다. 하지만, 검정색 피스는 모두 있었으나, 흰색 피스는 개수가 올바르지 않았다. 체스는 총 16개의 피스를 사용하며, 킹 1개, 퀸 1개, 룩 2개, 비숍 2개, 나이트 2개, 폰 8개로 구성되어 있다. 동혁이가 발견한 흰색 피스의 개수가 주어졌을 때, 몇 개를 더하거나 빼야 올바른 세트가 되는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 동혁이가 찾은 흰색 킹, 퀸, 룩, 비숍, 나이트, 폰의 개수가 주어진다. 이 값은 0보다 크거나 같고 10보다 작거나 같은 정수이다.
출력
첫째 줄에 입력에서 주어진 순서대로 몇 개의 피스를 더하거나 빼야 되는지를 출력한다. 만약 수가 양수라면 동혁이는 그 개수 만큼 피스를 더해야 하는 것이고, 음수라면 제거해야 하는 것이다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
int[] value = new int[]{1, 1, 2, 2, 2, 8};
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] splitStr = br.readLine().split(" ");
for (int i = 0; i < splitStr.length; i++) {
sb.append(value[i] - Integer.parseInt(splitStr[i])).append(" ");
}
System.out.println(sb);
}
}
-
-
-
-
-
-
-
-
-
-
-
[baekjoon] 공 넣기 (백준 10810 java 풀이)
intro : 주어진 인덱스 특정 범위에 값을 넣는것을 반복하고 공이들어있는 곳에 1값을 넣어 출력하는게 포인트
백준 문제링크
문제
도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 또, 1번부터 N번까지 번호가 적혀있는 공을 매우 많이 가지고 있다. 가장 처음 바구니에는 공이 들어있지 않으며, 바구니에는 공을 1개만 넣을 수 있다. 도현이는 앞으로 M번 공을 넣으려고 한다. 도현이는 한 번 공을 넣을 때, 공을 넣을 바구니 범위를 정하고, 정한 바구니에 모두 같은 번호가 적혀있는 공을 넣는다. 만약, 바구니에 공이 이미 있는 경우에는 들어있는 공을 빼고, 새로 공을 넣는다. 공을 넣을 바구니는 연속되어 있어야 한다. 공을 어떻게 넣을지가 주어졌을 때, M번 공을 넣은 이후에 각 바구니에 어떤 공이 들어 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐서 공을 넣는 방법이 주어진다. 각 방법은 세 정수 i j k로 이루어져 있으며, i번 바구니부터 j번 바구니까지에 k번 번호가 적혀져 있는 공을 넣는다는 뜻이다. 예를 들어, 2 5 6은 2번 바구니부터 5번 바구니까지에 6번 공을 넣는다는 뜻이다. (1 ≤ i ≤ j ≤ N, 1 ≤ k ≤ N) 도현이는 입력으로 주어진 순서대로 공을 넣는다.
출력
1번 바구니부터 N번 바구니에 들어있는 공의 번호를 공백으로 구분해 출력한다. 공이 들어있지 않은 바구니는 0을 출력한다.
문제 풀이
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
String[] inputSplit = input.split(" ");
int arrLength = Integer.parseInt(inputSplit[0]);
int forCount = Integer.parseInt(inputSplit[1]);
int[] result = new int[arrLength];
for (int i = 0; i < forCount; i++) {
input = sc.nextLine();
inputSplit = input.split(" ");
int value1 = Integer.parseInt(inputSplit[0]);
int value2 = Integer.parseInt(inputSplit[1]);
int value3 = Integer.parseInt(inputSplit[2]);
for (int j = value1 - 1; j < value2; j++) {
result[j] = value3;
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < result.length; i++) {
sb.append(result[i]);
if (!(i == (result.length - 1))) {
sb.append(" ");
}
}
System.out.println(sb);
}
}
-
-
-
[baekjoon] 영수증 (백준 25304 java 풀이)
intro : 물품의 가격과 수량의 개수를 계산한 각 라인의 총합과, 영수증의 가격을 비교해서 일치/불일치 여부를 처리하는게 포인트
백준 문제링크
문제 설명
준원이는 저번 주에 살면서 처음으로 코스트코를 가 봤다. 정말 멋졌다. 그런데, 몇 개 담지도 않았는데 수상하게 높은 금액이 나오는 것이다! 준원이는 영수증을 보면서 정확하게 계산된 것이 맞는지 확인해보려 한다 영수증에 적힌, 구매한 각 물건의 가격과 개수 구매한 물건들의 총 금액 을 보고, 구매한 물건의 가격과 개수로 계산한 총 금액이 영수증에 적힌 총 금액과 일치하는지 검사해보자.
입력
첫째 줄에는 영수증에 적힌 총 금액 X가 주어진다. 둘째 줄에는 영수증에 적힌 구매한 물건의 종류의 수 N이 주어진다. 이후 N개의 줄에는 각 물건의 가격 a와 개수 b가 공백을 사이에 두고 주어진다.
출력
구매한 물건의 가격과 개수로 계산한 총 금액이 영수증에 적힌 총 금액과 일치하면 Yes를 출력한다. 일치하지 않는다면 No를 출력한다.
제한
1 ≤ X ≤ 1,000,000,000
1 ≤ N ≤ 100
1 ≤ a ≤ 1,000,000
1 ≤ b ≤ 10
문제 풀이
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int total = sc.nextInt();
sc.nextLine();
int count = sc.nextInt();
sc.nextLine();
int checkSum = 0;
for (int i = 0 ; i < count; i++) {
String input = sc.nextLine();
String[] splitInput = input.split(" ");
checkSum += (Integer.parseInt(splitInput[0]) * Integer.parseInt(splitInput[1]));
}
if (total == checkSum) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
문제 해석
단순히 Scanner를 이용해서 값을 받아서 입력받은 값이 실제 영수증에 입력된 값과 같은지 비교하는 로직을 구성하는 문제, 중요한 포인트는 정수형 타입을 Scanner로 받은다음에 sc.nextLine을 해야한다는 점 이부분을 하지않는다면 Exception 발생
Scanner sc = new Scanner(System.in);
int total = sc.nextInt();
sc.nextLine();
int count = sc.nextInt();
sc.nextLine();
-
[programmers] 중복된 숫자 개수 (프로그래머스 java 풀이)
intro : 배열안에 값을 반복문으로 하나씩 비교해서 일치하는 개수를 찾으면 된다.
프로그래머스 문제링크
문제 설명
정수가 담긴 배열 array와 정수 n이 매개변수로 주어질 때, array에 n이 몇 개 있는 지를 return
하도록 solution 함수를 완성해보세요.
제한사항
1 ≤ array의 길이 ≤ 100
0 ≤ array의 원소 ≤ 1,000
0 ≤ n ≤ 1,000
입출력 예
array
n
result
[1, 1, 2, 3, 4, 5]
1
2
[0, 2, 3, 4]
1
0
입출력 예 설명
입출력 예 #1
[1, 1, 2, 3, 4, 5] 에는 1이 2개 있습니다.
입출력 예 #2
[0, 2, 3, 4] 에는 1이 0개 있습니다.
문제 풀이
public int solution(int[] array, int n) {
// return 할 변수 선언
int answer = 0;
// 향상된 반복문을 실행
for (int i : array) {
// 찾고자 하는 값과 같은지 if 조건문을 통해 비교
if (i == n) {
// 만약 찾고자 하는 값과 같다면 + 1
answer += 1;
}
}
// 결과값 반환
return answer;
}
// 테스트 1 통과 (0.06ms, 73.8MB)
// 테스트 2 통과 (0.02ms, 78MB)
// 테스트 3 통과 (0.02ms, 72.8MB)
// 테스트 4 통과 (0.03ms, 77.6MB)
// 테스트 5 통과 (0.01ms, 74.7MB)
// 테스트 6 통과 (0.02ms, 75.3MB)
문제 해석
배열 array를 반복문을 통해 각각의 원소에 접근하여, 매개변수 n 의 값과 동일한 값이 존재하는지 비교하고 만약, 값이 일치하는경우 answer 변수에 +1 처리 후 반복문이 종료되는 시점에서 answer 변수를 return 한다
Touch background to close
I am visible
