uk's study

#유형 : 시뮬레이션

# 규칙을 찾는데 시간이 오래 걸렸고, 메모리 생각안하고 전체 소용돌이 출력하다가 메모리 초과가 났다. 따라서 소용돌이 중 범위에 해당하는 부분만 구해서 출력을 했더니 해결하였다.

소용돌이 규칙

1. 시작 방향은 오른쪽, 진행 방향은 오른쪽->위쪽->왼쪽->아래->오른쪽.. 반복이다

2. 회전을 두 번 할 때마다 전진하는 길이가 늘어난다. 결국은 오른쪽과 왼쪽으로 이동 시에 길이가 1개씩 늘어나는 셈이다.

3. 소용돌이 전체를 구하면 메모리 초과가 난다. 따라서 구간에 속하는 부분만 구한다.

4. 띄어쓰기는 가장 큰 숫자의 자리수에서 해당하는 숫자의 자리수의 차이를 구한 만큼 공백을 더해줘서 출력한다.

예시)

1(오른쪽,1칸)->2(위쪽,1칸)->3(왼쪽,2칸)->5(아래쪽,2칸)->7(오른쪽,3칸)->10(위쪽,3칸)->13(왼쪽,4칸)->17...

# 유형 : 탐색 

# 난이도 : Gold V

# 쉽게 볼 수 있는 DFS 문제.. 동서남북 방문 안한 곳을 갈 때마다 확률 값을 곱해줘서 매개변수로 넘겨주면서 카운트와 이동 횟수가 일치할 때 합을 해주면 된다. 아무리 풀어도 틀리길래.. 잘 못 풀은 줄 알았는데 확률값이 동/서/남/북 순서로 들어오는데 이걸 안 보고 계속 왜 틀리지 생각했다.. 문제를 꼼꼼히 읽자....

#유형 : 시뮬레이션 

# 토너먼트가 진행할때마다 홀수인 경우에는 num/2 + 1 짝수일 경우에는 num/2 로 진행된다. 그러면 타겟끼리 같은 그룹인지 어떻게 체크하냐면 예를들어 1 2 3 이런 경우에 +1하고 /2를 해주면 그룹핑이 가능해진다.

#유형 : 탐색

# 많이 어려웠던 문제... 풀다가 메모리초과, 시간초과 때문에 도저히 모르겠어서 백준님 슬라이드를 통해 이해하고 풀었다.

https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019

우선 시작 숫자와 마지막 숫자의 일의 자리수를 0과 9로 맞춘다.

쉽게 설명하자면 만약 10에서 29사이의 사용된 0~9 숫자를 구하면 다음과 같다.

일의 자리만 보면 된다. 0~9사이가 2개씩 나왔다. (2-1+1)*1 => 2

다른 예로, 일의 자리 기준으로 생각해보자.  1350 ~ 8739 는 (873-135+1)*1 . 따라서 arr[0~9] 에는 873-135+1 를 더할수 있다.

그 다음에는 십의 자리를 구해보면 된다. 각 숫자를 10으로 나눠준다. 135 ~ 873 를 각각  ++, -- 를 통해 140 ~ 869로 만들어준다.

140 ~ 869 는 86 - 14 + 1 을 더할수 있다. 이 때 지금 구하고 있는 숫자는 십의 자리이므로  * 10을 해줘야 한다.

아래의 경우에 숫자들 뒤에 0~9가 붙어있는 것이다. 따라서 10을 곱해줘야한다.

이렇게 곱하는 숫자를 10씩 곱해주고, 시작숫자와 마지막 숫자를 10으로 나눠가면서 구하면 된다.

# 유형 : 투포인터

# upper bound, lower bound 한가지 방법과 추가로 새롭게 hashMap 을 써서 풀어보았다.

배열 사이즈가 최대 1000이라서 n^2으로 합을 다 구하고 투포인터를 사용하면 된다.

# 유형 : 탐색, DFS

# dfs 쉬운 문제중 하나, 인덱스만 잘 설정해서 탐색돌리면 해결가능

#유형 : DFS

#전형적인 dfs , 백트래킹 문제

# 유형 : 이분 탐색, LIS

# 가장 긴증가하는 부분 수열 3에서 역추적하는 배열 또는 변수를 추가하여 계산하면 된다.

테스트케이스로 

7

1 6 2 4 5 3 7 가 들어온다면 정답은 1 2 4 5 7 을 출력해야한다.

필자의 경우에는 기존의 리스트와 별개로 arraylist를 point형으로 한개 더 만들어서 index값과 저장되는 값을 아래와 같이 쌍으로 리스트에 넣었다.

0/1/1/2/3/2/4 

1/6/2/4/5/3/7 

이제 뒤에서부터 역추적을 해보자. 가장 maxIndex는 4이고 4->3->2->1->0(7->5->4->2->1) 순으로 maxIndex를 감소해가며 추적하는데 이 때 스택을 사용해서 push한 다음 pop하여 출력하면 편하게 결과값을 출력할 수 있다. 

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;

public class p14002 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int arr[] = new int[N];
		ArrayList arrList = new ArrayList<>();
		ArrayList tmp = new ArrayList<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		
		for(int i=0; i<N; i++) {
			int next = arr[i];
			if(arrList.isEmpty() || arrList.get(arrList.size()-1) < next) {
				arrList.add(next);
				tmp.add(new Point(arrList.size()-1,next));
			}else {
				int left = 0;
				int right = arrList.size()-1;
				while(left<right) {
					int middle =(left+right)/2;
					if(arrList.get(middle) < next)
						left = middle + 1;
					else
						right = middle;
				}
				arrList.set(right, next);
				tmp.add(new Point(right,next));
			}
			
		}
		
		int last = -1;
		for(int i=0; i<tmp.size(); i++) {
			last = Math.max(last, tmp.get(i).x);
		}
		
		Stack stack = new Stack<>();
		
		for(int i=tmp.size()-1; i>=0; i--) {
			if(last == tmp.get(i).x) {
				stack.add(tmp.get(i).y);
				last--;
			}
		}
		
		System.out.println(arrList.size());
		
		while(!stack.isEmpty())
			System.out.print(stack.pop()+" ");
		
	}
}