손코딩 문제 유형 연습 (작성 중)
이번에 보는 손코딩 코테 시험을 대비하기 위해 연습이 더 필요할 것 같아서
손코딩에 도움될 만한 블로그 글을 찾아보았다..!
이번 글은 아래 블로그 글을 공부하는 글이당
내가 확실하게 알지 못했던 부분들을 정리해볼 예정이다.
참조 URL :
https://velog.io/@rhdguswlx/ofjwsqq0
손코딩 테스트 대비
Math.random() 함수 랜덤함수는 기본형이 Double형이기에 (int) 로 정수화시켜줘야함0~1(1은 미포함) 구간에서 부동소수점의 난수를 생성1부터의 값을 뽑고 싶다면 랜덤함수는 0부터 나오기때문에 +1을
velog.io
시작 전
손코딩 시작할 기초
아래 틀을 작성하고 시작할 것!!
이때 solution 메소드의 반환 타입과 매개변수, answer 변수의 데이터타입은 달라질 수 있음
Solution 함수
class Solution{
public int solution(int n){
int answer = 0;
return answer;
}
}
메인 함수
public class Main {
public static void main(String[] args) {
}
}4/4
배열 문제
배열의 최대값 최소값 찾기
방법 1. Arrays.stream(arr).max().getAsInt(); // Arrays.stream(arr).min().getAsInt();
int [] arr = {1,2,3,4,5};
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
System.out.println(max);
System.out.println(min);
최댓값 : int max = Arrays.stream(arr).max().getAsInt();
최솟값 : int min = Arrays.stream(arr).min().getAsInt();
알게된 점:
Q. Arrays.stream(arr).max().getAsInt(); 에서 getAsInt();를 해야하는 이유?
.max()의 반환 타입이 OptionalInt이기 때문
* 왜 OptionalInt로 반환할까?: 배열이 빈 배열일 수도 있기 때문
* OptionalInt는 "int일 수도 있고, 아닐 수도 있는 값" /
빈 배열 같은 예외 상황을 안전하게 처리하기 위한 래퍼 타입
방법 2. 반복문 활용
int[] arr = {1, 2, 3, 4, 5};
int max = arr[0];
int min = arr[0]
for(int i = 1; i< arr.length; i++){
if(arr[i] > max){
max = arr[i]
}
if(arr[i]<min){
min = arr[i]
}
}알게된 점
else if를 쓰는 건 안될까?
x → min의 검사에서 값이 max보다 크기만 하면 min의 검사를 건너뜀
중복된 값 찾기
이중 for 문 사용하기
//이중 for문으로 비교
int[] arr = { 1, 2, 3, 3, 4, 4, 5 };
for(int i = 0; i< arr.length; i++){
for(int j=i; j < arr.length; j++){
if(arr[i] == arr[j]){
System.out.println("중복된 값:" + arr[i]);
}
}
}
배열 뒤집기
//★Arrays.reverse(arr); (x) 이런 메소드 없음
//방법 1. List로 변환 후 Collections.reverse(); 사용
//방법 2. 직접 구현하기 (for문 사용)
**Arrays.asList()는 참조형에 쓰일 수 있음
String[] arr = {"apple", "banana", "cherry"};
List<String> list = Arrays.asList(arr);
for(String fruit : list) {
System.out.println(fruit);
}
방법 1.
int[] arr = { 1, 2, 3, 3, 4, 4, 5 };
List<Integer> list = Arrays.stream(arr) // IntStream
.boxed() // int → Integer
.collect(Collectors.toList()); // List<Integer>
/* 대체 가능
for (int num : arr) {
list.add(num); // int → Integer (오토박싱)
}
*/
Collections.reverse(list);
System.out.println(list); // [5, 4, 4, 3, 3, 2, 1]
알게된 것
List<String> list = Arrays.stream(arr).collect(Collectors.toList());
방법 2.
int[] arr = { 1, 2, 3, 3, 4, 4, 5 };
int left = 0; //첫 인덱스
int right = arr.length -1; //마지막 인덱스
while(left<right){
int tmp = arr[left];
arr[left] = arr[right];
arr[right]= tmp;
left++;
right--;
}
System.out.println(Arrays.toString(arr)); //배열을 출력하기 위하여 .toString으로 바꿔야 함자꾸 깜빡하는 거
배열은 출력하기 위하여 Arrays.toString()로 바꿔야 함
System.out.println(Arrays.toString(arr));
문자열 문제
문자열 뒤집기
String str = "hello";
StringBuilder sb = new StringBuilder(str).reverse().toString();
String str = "hello";
StringBuilder sb = new StringBuilder(str); //StringBuilder의 ()안에 str 바로 넣으면 변환됨
sb.reverse().toString(); //StringBuilder로 메소드 적용한 값은 .toString() 해줘야 함
System.out.println(sb);알게된 점 1
문자열을 StringBuilder로 변환하는 법
StringBuilder sb = new StringBuilder(str);
깜빡하는 점 2.
sb.reverse().toString();
StringBuilder 변수에 바로 .reverse() 메서드
끝나면 .toString()
★ 중복된 문자열 제거
//만약 String으로 전달되면 String[] arr = str.split("");
String[] arr = { "p", "e", "o", "p", "l" ,"e" };
arr = Arrays.stream(arr) // 배열을 스트림으로 변환
.distinct() //중복 제거
.toArray(String[]::new); // 다시 String[] 배열로 변환
System.out.println(Arrays.toString(arr)); //결과 출력할 땐 배열은 .toString();
String[] arr = { "p", "e", "o", "p", "l" ,"e" };
Arrays.stream(arr).distinct().toArray(String[]arr::new);
알게된 점
.distinct(); : 중복 제거
.toArray(String[]::new); : 새로운 String[] 객체로 반환
- 생성자 참조(Constructor reference)
- 자바에서 스트림(Stream)을 배열로 바꿀 때 어떤 타입의 배열을 만들지 지정
배열은 출력 시 .toString();
팰린드롬
방법 1. StringBuilder
//StringBuilder sb = new StringBuilder(str);
//.reverse() 바로
//끝나면 .toString();
public static boolean isPalindrome(String str) {
String reversed = new StringBuilder(str).reverse().toString();
return str.equals(reversed);
}
방법 2.
public static boolean isPalindrome(String str) {
int left = 0;
int right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}최대 공약수, 최소 공배수
최대 공약수 : 원래 b는 a로, a에서 b를 나눈 것은 b로 - (a에서 b나눈 것이 0이면 a 반환)
최소 공배수 : 두 수를 곱한 다음 최대공약수로 나눈 것
/* 최대 공약수
b는 a로 , a는 a%b로 넣기*/
private int gcd (int a, int b){
if(b==0){
return a;
}
return gcd(b, a%b);
}
-----------------------------------
/* 최소 공약수
두 값을 곱한 후 최대공약수로 나누기*/
private int lcm(int a, int b){
return a*b /gcd(a,b); //여기에서 최대 공약수를 호출
}4/5
소수 구하기
소수 : 1가 자기 자신으로만 나누어지는 수
★1은 소수에서 제외
이중 for문으로 돌렸을 때 i와 j 나눈 나머지가 0이면 count를 키우기
이때 count가 하나이면! -> 본인만 count되어 있으면 소수 출력
0이랑 1은 소수 아님
class Solution {
public int solution(int n) {
boolean[] isComposit = new boolean[n+1]; //소수 = false
int answer = 0;
for(int i = 2; i < isComposit.length ; i++){
if(!isComposit[i]){
answer++;
//i의 배수는 모두 true로 만들기
for(int j = i*2; j<= n ; j+=i){ //i씩 증가
isComposit[j] =true;
}
}
}
return answer;
}
}
만약 어떤 소수인지 출력? 그럼 i를 출력하기
팩토리얼 수중에 0인 것
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올떄까지 0의 개수를 구하라
뒷자리가 0이 나오는 경우 2와 5가 곱해져있을 때
소인수분해를 해서 2와 5가 나오면 뒷자리는 0으로 끝남
public class Main{
public static void main(String[]args){
Scanner sc = new Scanner(System.in);
int num = sc.nextInt(); //sc.next() = 문자열
sc.close(); // 리소스 누수 방지를 위해 Scanner 닫기
int answer = 0;
while(num>=5){
answer+=num/5;
num/=5;
}
System.out.println(answer);
}
}
숫자 중에 7의 개수
public class Main{
public static void main(String[]args){
int answer = 0;
int [] array = {7,77,17};
for(int i = 0; i < array.length;i++){
//숫자를 문자로 바꾸기
String num = Integer.toString(array[i]);
String[]arr = num.split("");
for(int j = 0; j< arr.length ; j++){
if(arr[j].equals("7")){
answer++;
}
}
}
System.out.println(answer);
}
}
알게된 것
숫자 -> 문자 변환
Integer.toString(숫자);
팩토리얼 : n! = n × (n-1) × (n-2) × ... × 1
피보나치 : f(n) = f(n-1) + f(n-2)
재귀 팩토리얼
4면 4*3*2*1
int fact(int n){
if(n==1){
return 1;
}
return n*fact(n-1);
}
★ 재귀 피보나치 수열
피보나치 = 앞의 두 수를 더해서 다음 수를 만들어나감
private int fibo(int n){
if(n<2){ //n이 2보다 작으면 1,0...
return n;
}
return fibo(n-1) + fibo(n-2);
}
로또 번호 뽑기 (Math.random());
import java.util.*;
public class Main{
public static void main(String[]args){
//랜덤 1부터 값 뽑기
//로또 뽑을 배열 6개로 생성
int[] arr= new int[6];
for(int i = 0; i< arr.length; i++){
//Math.random()은 Double형이라 int로 형변환
int lotto = (int)(Math.random());
}
}
}
구구단 출력(가로)
구구단 출력(세로)
구구단 3단에서 3의 배수 빼고 출력
구구단 3의 배수단만 출력
메모이제이션을 이용한 피보나치 수열
반복문(동적계획법) 이용한 피보나치 수열
1~100 사이 수를 크기 10인 배열 arr에 담고 각각 정렬하기
대표 알고리즘
선택 정렬
최솟값과 비교해서 더 작으면 교체
이때 i 이후에 최솟값이 있으면 (i 하나마다 j를 다 돌고 변경)
for (int i = 0; i < arr.length; i++) {
int min = i; // 현재 위치를 최소값으로 가정
// i 이후의 값 중 가장 작은 값을 찾는다
for (int j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j; // 더 작은 값이 있다면 min 인덱스 갱신
}
}
// 현재 위치(i)와 가장 작은 값(min)을 교환
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
버블 정렬
i회차씩 돌릴 때마다 큰 수가 뒤로 보내짐
다음 j는 이미 정렬된 끝의 수를 제외하고 다시 정렬
(바로 뒤와 비교해서 i보다 큰 수를 뒤로 보냄)
int[] arr = {1, 5, 6, 2, 3, 7, 8, 4, 9, 10};
// 버블 정렬 - 가장 큰 값을 오른쪽 끝으로 "거품처럼" 올린다
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
i 반복문이 필요한 이유
버블 정렬은 한 번 반복할 때마다 가장 큰 수가 맨 끝으로 가요.
- 1회차(i=0): 가장 큰 수가 맨 끝으로
- 2회차(i=1): 두 번째 큰 수가 그 앞에
- ...
- 이렇게 i가 커질수록, 비교할 범위가 점점 줄어듭니다.
i = 전체 몇 회 반복했는지 나타냄 (회차)
j = 0부터 시작해서 인접한 값을 비교 (arr[j] vs arr[j+1])
j<arr.length -1 - i = 이미 정렬된 마지막 부분은 안 봐도 됨
삽입 정렬 (거꾸로 - 더 작은 값을 왼쪽으로 이동)
앞에서부터 차례대로 정렬된 부분에 "적절한 위치"를 찾아 삽입하는 방식
- 마치 카드 게임에서 손에 카드를 한 장씩 끼워넣는 것처럼 동작
- i=1부터 시작해서 arr[0...i] 구간을 항상 정렬된 상태로 유지함.
for (int i = 1; i < arr.length; i++) { // 두 번째 요소부터 시작
for (int j = i; j > 0; j--) { // 현재 값 j와 왼쪽 값들을 비교
if (arr[j - 1] > arr[j]) { // 왼쪽이 더 크면
int tmp = arr[j]; // 오른쪽을 스와프해서 왼쪽으로 이동
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
} else break; // 아니면 멈춤(자리 찾았음)
}
}
거꾸로 -> 만약 arr[j-1]이 arr[j]보다 큰 값일 때 서로 바꾸고 ( 아니면 ) break;
이미 이전 것들은 정렬이 되었으니까 break
퀵 정렬
“중간값 하나를 고르고, 그보다 작은 건 왼쪽, 큰 건 오른쪽으로 보내면서 나눠서 정리해나가는 방법!”
제일 첫번째 수(start) 를 pivot / 작은 건 왼쪽 , 큰 건 오른 ㅉ고
public class Main {
public static void main(String[] args) {
int n = 10;
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
quickSort(arr, 0, n - 1);
System.out.println(Arrays.toString(arr)); // 정렬된 결과 출력은 여기서!
}
private static void quickSort(int[] arr, int start, int end) {
if (start >= end) return;
int pivot = start; // pivot = start
int left = start + 1; //left는 start보다 1큰 값
int right = end; //right = end
while (left <= right) { //start보다 1큰 값이 end값보다 작을 때
while (left <= end && arr[left] <= arr[pivot]) left++; //left가 end보다 작거나 같고, arr left가 arr start의 값보다 작거나 같으면 left++;
while (right > start && arr[right] >= arr[pivot]) right--; //right가 start보다 크고 / arr right가 arr start보다 크거나 같으면 right--;
if (left > right) { //만약 left와 right이 안 같으면 중앙값 기준으로 제대로 정렬 안됐다는 거니까 피벗과 작은 값 (right) 교체
int tmp = arr[pivot];
arr[pivot] = arr[right];
arr[right] = tmp;
} else { // 제대로 정렬됐다면 작은 값과 큰 값 교체
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
}
}
// 분할 이후 왼쪽과 오른쪽 정렬
quickSort(arr, start, right - 1);
quickSort(arr, right + 1, end);
}
}
start가 end보다 크면 끝냄
석차 구하기
정수를 비교해 작은 점수의 등수를 증가 시키는 방식
10명의 학생의 점수를 임의로 설정하여 각 학생별로 등수를 매기시오
스택 LIFO
.push () / .pop () / .empty() /.peek()
Stack<Integer> s = new Stack<>();
public static void main(String[] args) {
Stack<Integer> s = new Stack<>();
// 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
s.push(5);
s.push(2);
s.push(3);
s.push(7);
s.pop();
s.push(1);
s.push(4);
s.pop();
while(!s.empty()) { //비어있지 않으면
System.out.println(s.peek());//스택의 맨앞에있는거 출력
s.pop(); //하고 삭제
}
}
큐 FIFO
.offer(); / .poll()
Queue<Integer> q = new LinkedList<>():
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.offer(5); //삽입
q.offer(2);
q.offer(3);
q.offer(2);
q.poll(); //삭제
//먼저 들어온 원소부터 추출
while(!q.isEmpty()) {
System.out.println(q.poll());
}
}
}
추가
int 형 배열 내림차순 하기
1. Integer[] arr2 = Arrays.stream(arr).boxed().toArray(Integer[]::new);
2. Arrays.sort(arr2,Collections.reverseOrder());
그래프 탐색 알고리즘 : DFS/BFS
소수문제, 길찾기 문제, 숫자중에 0이나, 7의 개수, 팩토리얼 수중에 0인것, 피보나치, 완전탐색 기초적인것(DFS, BFS), 달팽이문제, 배열돌리기, 해쉬맵으로 카운트해서 정렬하기 , 이진검색트리, 타켓숫자을 주고 배열중 두수로 타켓숫자 만들기