merry

https://school.programmers.co.kr/learn/courses/30/lessons/42862#

테스트케이스 13번

: 배열 sort를 해주어야 한다.

이유

> 정렬하지 않으면 3번이 4번한테 빌려줘서 2번은 못받기 때문

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;
        
        Arrays.sort(lost);
        Arrays.sort(reserve);
        
        for(int i=0; i<lost.length; i++){
            for(int j=0; j<reserve.length; j++){
                if(lost[i] == reserve[j]){
                    reserve[j] = lost[i] = -1;
                    answer++;
                    break;
                } 
            }
        }
        
        for(int i=0; i<lost.length; i++){
            for(int j=0; j<reserve.length; j++){
                if((lost[i]+1) == reserve[j] || (lost[i]-1) == reserve[j]){
                    reserve[j] = -1;
                    answer++;
                    break;
                }
            }
        }
        
        return answer;
    }
}

(반복문이 많아서 리팩토링이 필요할 것 같다.)

for(int loster : lost){
            for(int j=0; j<reserve.length; j++){
                if(loster == reserve[j]+1 || loster == reserve[j]-1){
                    reserve[j] = -1;
                    answer++;
                    break;
                }
            }
        }

무릎을 탁 친 다른 분들의 풀이

이중포문을 없애줄 수 있다.

잃어버린 사람 -1 

잃어버렸지만  여분이 있는 사람 0 

빌려줄 수 있는 사람 1

public int solution(int n, int[] lost, int[] reserve) {
        int[] people = new int[n];
        
        for (int l : lost) 
            people[l-1]--;
        for (int r : reserve) 
            people[r-1]++;
 }

DP를 처음 접하는 사람에게 추천하는 문제 중 하나.

https://www.acmicpc.net/problem/2748

1. 재귀함수

: 피보나치의 수는 재귀함수로도 풀 수 있는 문제지만,

지수적 함수를 현실에서 구할 수 없다고 판단 >> DP 활용!

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 result = fibo(N);
		
		System.out.println(result);
	}

	private static int fibo(int n) {
		
		if(n<=2) {
			return 1;
		} else {
			return fibo(n-2) + fibo(n-1);
		}
	}
}

2. DP

중복 호출이 일어나 비효율적이므로 어떠한 값을 계산한 적이 있다면 그 값을 활용

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 result = fibo(N);
		
		System.out.println(result);
	}

	private static int fibo(int n) {
		
		int[] dp = new int[91];
		
		if(n==2 || n==1) {
			return 1;
		} else if(dp[n]<=0){
			dp[n] = fibo(n-2) + fibo(n-1);	//값이 없다면 재귀함수 호출
		} 

		return dp[n];
	}
}

백준 결과 >> 메모리 초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	static long[] dp;
	
	public static void main(String[] args) throws IOException  {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());	
		
		dp = new long[N + 1];

		for(int i = 0; i < N + 1; i++) {
			dp[i] = -1;
		}
		
		dp[0] = 0;
		dp[1] = 1;
		System.out.println(fibo(N));
	}

	public static long fibo(int N) {
		
		if(dp[N]==-1){
			dp[N] = fibo(N-1) + fibo(N-2);	//값이 없다면 재귀함수 호출
		} 
		return dp[N];
	}
}

>> 백준 결과

https://www.acmicpc.net/problem/2003 

1)  int Start Point, End Point 두 개의 포인터를 배열[0]에 두기

2)  S 포인터 ~ E 포인터 합 sum과 목표 숫자 M을 비교하기

3-1) 포인터를 증가시킬 때 

Start  포인터는 현재 위치의 원소를 sum에서 제거

End 포인터는 현재 위치의 원소를 sum에서 증가

# sum이 M보다 크다.

sum이 더 크니까 값을 줄여야 함. start 포인터를 1 증가시켜 현재 위치 원소 값을 sum에서 빼주기

# sum== M

cnt++;

같은 경우 후처리를 어떻게 해야하는지 블로그마다 달라 상당히 혼란스러웠는데, 다른 경우가 또 있나 찾아보아야 하기 때문에 end포인터를 1 증가시고 값을 sum에 더해줌

#  sum이 M보다 작다

sum이 더 작으니까 값을 늘려주어야 함. end 포인터를 1 증가시켜 end 인덱스의 값을 sum에 더해준다.

 * E 포인터가 끝 점에 도달했다면, start  포인터를 1 증가

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 N = Integer.parseInt(st.nextToken());	//수열 요소 개수
		int M = Integer.parseInt(st.nextToken());	//목표
		
		int[] arr = new int[N];
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int start = 0, end = 0, sum = 0, cnt = 0;
		
		while(true) {
			if(sum>M) {
				sum-=arr[start++];
			} else if(end==N) {
				break;
			} else {
				sum+=arr[end++];
			}
			
			if(sum == M) 
				cnt++;
		}
		
		System.out.println(cnt);
	}
}

ref. 코딩 테스트 & 알고리즘 대회 핵심 노트 - 투 포인터(Two Pointers), 구간 합(Prefix Sum)

https://youtu.be/rI8NRQsAS_s

for (byte val : br.readLine().getBytes()) {
				
	//내용 삽입
}

입력받은 문자열 길이만큼 반복하여 변수 val 저장

비밀번호는 맞는데 계속 git not authorized라고 떠서 찾아보니

깃허브에서 인증방식을 토큰 방식으로 변경했다고 한다.

결론 : password에 개인 토큰 키를 넣어주면 된다.

 편-안

import java.io.*;
import java.net.*;
import java.util.*;

public class ServerEx {
    public static void main(String[] args) {
        BufferedReader in = null;
        BufferedWriter out = null;
        ServerSocket listener = null;
        Socket socket = null;
        Scanner scanner = new Scanner(System.in); // 키보드에서 읽을 scanner 객체 생성

        try {
            listener = new ServerSocket(9999);
            System.out.println("연결을 기다리고 있습니다...");
            socket = listener.accept();
            System.out.println("연결되었습니다.");
            in = new BufferedReader(new InputStreamReader(socket.getInputStream()));
            out = new BufferedWriter(new OutputStreamWriter(socket.getOutputStream()));
            while (true) {
                String inputMessage = in.readLine();
                if (inputMessage.equalsIgnoreCase("bye")){
                System.out.println("클라이언트에서 bye로 연결을 종료하였음");
                break;
            }

            System.out.println("클라이언트 : " + inputMessage);
            System.out.println("보내기>>");
            String outputMessage = scanner.nextLine();
            out.write(outputMessage + "/n");
            out.flush();
        }

    } catch (IOException e) {
            System.out.println(e.getMessage());
        } finally {
            try {
                scanner.close(); // scanner 닫기
                socket.close(); // 통신용 소켓 닫기
                listener.close(); // 서버 소켓 닫기
            } catch (IOException e) {
                System.out.println("클라이언트와 채팅 중 오류가 발생하였습니다.");
            }
        }
    }
}

import java.io.*;
import java.net.*;
import java.util.*;

public class ClientEx {
	public static void main(String[] args) {
		BufferedReader in = null;
		BufferedWriter out = null;
		Socket socket = null;
		Scanner scanner = new Scanner(System.in); // Ű키보드에서 읽을 scanner 객체 생성
		try {
			socket = new Socket("localhost", 9999); // Ŭ클라이언트 소캣 생성, 서버에 연결
			in = new BufferedReader(new InputStreamReader(socket.getInputStream())); // 소켓 입력 스트림
			out = new BufferedWriter(new OutputStreamWriter(socket.getOutputStream())); // 소켓 출력 스트림
			while (true) {
				System.out.print("보내기>>"); // 프롬포트
				String outputMessage = scanner.nextLine(); // Ű키보드에서 한 행 읽기
				if (outputMessage.equalsIgnoreCase("bye")) { 
					out.write(outputMessage+"\n"); // "bye" 문자열 전송
					out.flush();
					break; // 사용자가 "bye"를 입력한 경우 서버로 전송 후 실행 종료
				}
				out.write(outputMessage + "\n"); // Ű키보드에서 읽은 문자열 전송
				out.flush(); // out의 스트림 버퍼에 있는 모든 문자열 전송
				String inputMessage = in.readLine();  // 서버로부터 한행 수신
				System.out.println("서버 : " + inputMessage);  // 서버로부터 받은 메시지를 화면에 출력
			}
		} catch (IOException e) {
			System.out.println(e.getMessage());
		} finally {
			try {
				scanner.close();
				if(socket != null) socket.close(); // 크라이언트 소켓 닫기
			} catch (IOException e) {
				System.out.println("서버와 채팅 중 오류가 발생했습니다.");
			}
		}
	}
}