Do it 알고리즘 코딩테스트 하루코딩 3장 자료구조 문제

 

# 1 각 자리 숫자의 합 구하기 java

 

숫자의 개수 N

N개의 숫자의 나열

 

5

54321

 

54321/10000 == 5

54321%10000 == 4321

4321/1000 == 4

4321%1000 == 321

이런 로직으로 풀면 복잡하다. 구현하기도 어려울 것이다.

그러나, 가장 핵심적인 것은 N이 100이므로 100자리 수를 int, long 형으로 받을 수 없다는 것이다. 자료형의 범위를 벗어나기 때문에

 

그러므로 String으로 받아야한다.

문자열 "54321"의 각 자리 수를 뽑아내려면 toCharArray() 메소드 호출하여 문자형 배열로 만들어야한다.

그러고나서 문자 숫자를 숫자로 변환하기위해 '1' -> 1 아스키코드를 이용한다.

문자'1'을 숫자1로 변환

'1' - 48 또는 '1' - '0'

 

실제 코딩 테스트에서 잘못된 걸 중간에 깨달았을 때 바꾸기 쉽지 않다. 당황하고 시간이 촉박하기 때문에

그러므로 코딩 하기전 문제를 먼저 완벽히 분석하자!

 

이해만 하고 실제로 코딩해보지 않으면 안된다.

 

# 2 평균 구하기 java

일일이 하나씩 계산하지 말고, 규칙을 발견하여 하나의 공식으로 정리해서 계산한다.

 

# 3 구간합 구하기 1 java

질의 개수가 많으므로 메모리화 고려

원본 배열 고정되어 있으므로 합배열 이용하여 구간합 구하기 시간복잡도를 줄이자, 이중 반복문 X 시간복잡도 nxn

예시보고 일반적인 순서와 인덱스 차이도 주의하자

 

받는 개수가 많으므로 BufferedReader 이용

여러 개 숫자 받으므로 10만개 int형 변수 각각으로 받기 보다는 StringTokenizer 이용

크기가 크므로 습관적으로 long

 

#4 연속된 자연수의 합 구하기 java

숫자의 개수 N이 크므로 O(nlogn)도 위험, 그러므로 O(n) 시간복잡도인 투 포인터 사용하여 연속된 수의 합 표현

2n == n

 

초기화

sum = 1 // start_index와 end_index가 표현하는 수의 범위의 합, 맨 처음에는 둘다 1을 가리키므로 총합은 1

count = 1// 자기 자신 하나로만 이루어진 표현

 

투 포인터 이동 원칙 // 뭘 먼저 하는 지 순서 주의 

sum == N // count++; end_index++; sum = sum + end_index; 

sum > N // sum = sum - start_index; start_index++;

sum <N // end_index++; sum = sum + end_index;

 

end_index == N이면 start_index 빼고 end_index 한 개로만 이루어진 경우만 가능하므로 더 이상 검사할 필요가 없어져  while문의 조건식은 end_index != N이다.

 

#5 주몽의 명령

2개의 합을 크기 비교하여야 하므로 정렬과 투포인터 이용해야한다.

정렬은 시간복잡도 O(nlogn), 투 포인터는 O(n) 이므로 총 시간복잡도는 O(nlogn)

 

초기화

int i = 0; // 최솟값

int j = N-1; // 최댓값

int count = 0 // 가능한 경우의 수

 

투 포인터 이동 원칙

A[i] + A[j] == M // i++, j-- 재료는 한번 사용하면 또 사용하지 못하므로

A[i] + A[j] > M // j--

A[i] + A[j] < M // i++

 

Arrays.sort();

 

while문의 조건식은 i<j 이어야 한다. i != j 는 7, 8일때 서로 엇갈려서 안된다. 중복 검사

 

# 6 DNA 비밀번호 (1)

슬라이딩 읜도우란? 2개의 포인터로 범위를 지정한 다음 유지한 채로 이동하며 문제를 해결하는 알고리즘, O(n)

 

조건 A, C, G, T 각 문자의 최소 개수를 만족하는 부분 문자열의 경우의 수

 

ex)조건은 1, 0, 0, 1

전체 문자열은 GATA, 부분 문자열의 길이는 2

GA // T가 1개 부족, X

AT // A 1개, T 1개 O

TA // A 1개, T 1개 O

그러므로 가능한 경우의 수는 2가지이다.

 

주어진 전체 문자열의 길이인 데이터의 최대크기는 1,000,000이지만 슬라이딩 윈도우를 이용하면 시간복잡도 O(n)이다.

가운데에 있는 데이터는 기존에 있었던 것이므로, 맨 앞과 뒤에 있는 데이터만 변하므로 이것만 검사하면 되기 때문에 시간복잡도를 줄일 수 있다.

 

1. 맨 처음 부분 문자열 검사

2. 다음부터 한 칸 씩 이동하며 검사

 

# 7 DNA 비밀번호 (2)

데이터의 최대크기가 1백만이므로 입력 받는 개수가 많으므로 BufferedReader 이용,

일일이 char형 배열 요소 한개씩 입력 받는 것이 아니라 한번에 배열 간편하게 만들기 위해 한 줄로 입력 받기 위해서

StringTokenizer 이용

 

초기화

int Result = 0; // 조건을 만족하는 즉, 비밀번호로 할 수 있는 부분 문자열의 경우의 수

int[] checkArr = new int[4]; // 부분 문자열이 만족 해야하는 조건

int[] myArr = new int[4]; // 현재 부분 문자열이 만족하는 조건

int checkSecret = 0; // 현재 부분 문자열이 만족하는 조건의 개수

char[] A; // 전체 문자열의 각 문자를 담은 배열에 대한 레퍼런스 변수

br.readLine().toCharArray() // 한 줄 문자열로 읽어서 문자열 배열로 만듦

 

Add(A[i]) // 문자열 배열 A의 i번째 요소를 슬라이딩 윈도우에 추가, 즉 검사 포함

// 순서 주의

myArr[0]++;

if(myArr[0] == checkArr[0]) checkSecret++; // if문의 조건식 주의

 

Remove(A[i]) {

// 순서 주의

if(myArr[0] == checkArr[0]) checkSecret--;

myArr[0]--;

}

 

1. 맨 처음 부분 문자열 검사

for(int i = 0; i<P; i++){

Add(A[i])

}

if(checkSecret == 4) Result++; // 만약 처음 부분 문자열이 4개의 조건을 모두 만족하면 경우의 수에 +1

2. 다음 부터 한 칸씩 이동하면 서 부분 문자열 검사

for(int i = P; i<S; i++) { // 슬라이딩 윈도우의 범위를 지정하고 있는 2개의 포인터 i, j 주의, i가 맨 뒤, j가 맨 앞
int j = i - P; 

Add(A[i]); // 이미 맨 처음 부분 문자열 검사에서 양 끝 데이터를 제외한 가운데에 있는 데이터는 검사된 상태이기 때문에,

Remove(A[j]); // 양 끝만 검사하면 된다.

if(checkSecret == 4) Result++; // 

}

 

# 8 스택으로 오름차순 수열 만들기

스택 후입선출

1. 현재 수열(스택)안에 들어있는 수 >= 입력으로 들어오는 자연수

동안 계속 push(), 마지막에 pop() 한번

2. 현재 수열(스택) 안에 들어 있는 수 < 입력으로 들어오는 자연수

동안 계속 pop()

if(현재 수열 안에 들어 있는 수> 입력으로 들어오는 자연수) 인 경우 // pop()으로 수열을 표현할 수 없으므로 NO 출력, 작은 경우에는 push()와 pop()으로 수열을 표현할 수 있다.

 

# 9 13 카드게임

1번 카드가 가장 위, N번 카드가 가장 아래

가장 마지막에 남는 카드는?

 

양쪽에서 삽입, 삭제가 일어나므로 Queue 자료구조 이용

Queue<Integer> myQueue = new LinkedList<>();

 

카드가 1개 남을 때까지 반복

 

# 10 14 절댓값 힙 구현하기

절댓값 힙이라는 자료구조는 원래 존재X, 문제에서 만든 것이다.

 

1. 절댓값이 가장 작은 값

2. 가장 작은 절댓값이 여러 개인 경우, 그 중에서 가장 작은 수 출력 // 즉, 양수 와 음수 중에서 음수를 출력

 

// 입력이 0, 0이 아닐때 로 나누어짐

입력이 0이면 출력, 그 외이면 추가

힙이 텅텅 비어있는 데, 입력이 0이면 0출력

 

지문 읽고 나서 이해후, 내가 맞게 이해한 것인지 알기 위해 예제를 보면서 검사

 

데이터의 최대크기 N이 100,000 십만이므로 BufferedReader

 

우선순위 큐의 정렬 기준 정의

PriorityQueue<Integer> myQueue = new PriorityQueue<>((o1, o2) - >{

return 이 양수이면 // 

음수이면 // 

});