배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 제거하는 것에서 PriorityQueue를 떠올렸습니다.
PriorityQueue는 add를 하면 오름차순으로 정렬이 되는 Queue입니다. PriorityQueue에 넣어서 값을 비교해서 절댓값이 작은 값을 출력하고 절댓값이 같을 때는 수의 작은 값을 출력하는 문제다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek11286 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> que = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
int a1 = Math.abs(o1);
int a2 = Math.abs(o2);
if(a1 == a2) {
return Integer.compare(o1, o2);
}
else {
return Integer.compare(a1, a2);
}
}
});
for(int i = 0 ; i < n ; i++) {
int num = Integer.parseInt(br.readLine());
if(num == 0) {
if(que.size() == 0) {
System.out.println(0);
}
else {
System.out.println(que.poll());
}
}
else {
que.add(num);
}
}
}
}
문제점
PriorityQueue에 add를 하면 PriorityQueue의 성질 때문에 add 한 순으로오름차순으로 정렬이 되는데 거기서 절댓값을 어떻게 비교 어떻게 해야될지를 떠올리지 못했다. compare를 사용해서 절댓값 문제를 해결할 수 있었다. 정렬 문제에서 compare를 이용하는 문제가 많으므로 compare를 공부를 하자.
오늘의 회고
오늘은 그동안 푼 문제 복습과 1문제 밖에 풀지 못했습니다. 알고리즘을 처음 공부하는데 이해하고 문제를 해결하는 방식을 떠올리는 것이 많이 어려운것 같습니다. 포기 하지 않고 하반기까지 실력을 향상 시키는 것을 목표로 꾸준히 달려보겠습니다.
기본적인 스택을 알고있는지 확인하는 문제라고 생각한다. 제가 조금 해맷던 부분은 BufferedReader로 받는데 push 할때는 2개의 입력을 받아야된다. 이 부분에서 고민을 하다가 전체를 String으로 받고 push라는 단어가 포함된 String에서는 split를 사용하여 자른 문자를 배열로 따로 받았다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek10828 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Integer> stack = new Stack<>();
int n = Integer.parseInt(br.readLine());
int m = 0;
String str = "";
for(int i = 0; i < n; i++) {
str = br.readLine();
if(str.contains("push")) {
String spt[] = str.split(" ");
stack.push(Integer.parseInt(spt[1]));
}
else if(str.equals("top")) {
if(stack.empty()) {
System.out.println(-1);
}
else {
System.out.println(stack.peek());
}
}
else if(str.equals("size")) {
System.out.println(stack.size());
}
else if(str.equals("empty")) {
if(stack.empty()) {
System.out.println(1);
}
else {
System.out.println(0);
}
}
else if(str.equals("pop")) {
if(stack.empty()) {
System.out.println(-1);
}
else {
System.out.println(stack.pop());
}
}
}
}
}
백준 18258번 큐 2
내가 생각한 풀이
위에 문제와 비슷한 문제이다. Queue를 이용해서 풀려고 했는데 front와 back에 대한 처리를 고민하다가 Deque로 풀었습니다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek18258 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String str = "";
Deque<Integer> que = new LinkedList<>();
StringBuffer bf = new StringBuffer();
for(int i = 0; i < n; i++) {
str = br.readLine();
if(str.contains("push")) {
String spt[] = str.split(" ");
int m = Integer.parseInt(spt[1]);
que.offer(m);
}
else if(str.equals("front")) {
if(que.isEmpty()) {
bf.append("-1\\n");
}
else {
bf.append(que.peek() + "\\n");
}
}
else if(str.equals("pop")) {
if(que.isEmpty()) {
bf.append("-1\\n");
}
else {
bf.append(que.poll() + "\\n");
}
}
else if(str.equals("size")) {
bf.append(que.size() + "\\n");
}
else if(str.equals("empty")) {
if(que.isEmpty()) {
bf.append("1\\n");
}
else {
bf.append("0\\n");
}
}
else if(str.equals("back")) {
if(que.isEmpty()) {
bf.append("-1\\n");
}
else {
bf.append(que.getLast() + "\\n");
}
}
}
System.out.println(bf.toString());
}
}
위에 문제들을 푸는데 시간을 시간을 많이 소비했다. 기본적인 것을 뭍는 문제이지만 if else 문에서 split에서만 str.contains를 사용해야된다. str.equals자리에 str.contains를 사용하면 이상한 답이 나온다.이유는 개발문서 폴더에 작성하겠습니다.
백준 9012번 괄호
내가 생각한 풀이
스택을 사용해서 푸는 문제이다. String을 문자로 변환해서 하나씩 비교하는데 ( 문자를 만나면 스택에 push하고 ) 문자를 만났을 때는 스택이 비어있는지 확인하고 비어있으면 push하고 빠져나온다. 비어있지 않으면 ( 문자이므로 pop을 합니다. for문이 끝났을 떄 스택이 비어있는지 확인하고 비어있으면 YES 비어있지 않으면 NO를 출력한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek9012 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Stack<Character> stack = new Stack<>();
for(int i = 0; i < n; i++) {
String str = br.readLine();
int len = str.length();
for(int j = 0; j < len; j++) {
char chr = str.charAt(j);
if(chr == '(') {
stack.push(chr);
}
else {
if(stack.isEmpty()) {
stack.push(chr);
break;
}
else {
stack.pop();
}
}
}
if(stack.isEmpty()) {
System.out.println("YES");
}
else {
System.out.println("NO");
}
stack.clear();
}
}
}
문제점
위에 문제를 풀때 알고리즘 논리에는 문제가 없는것 같다고 생각했지만 답이 이상한 출력이 나왔습니다. 알고리즘적 문제인 줄 알고 계속 알고리즘을 수정할려고 노력했습니다. 하지만 문제는 for문이 끝나고 stack을 초기화 시켜줘야되는데 초기화를 시켜주지 않아서 계속 잘못된 답이 나왔습니다.
오늘의 회고
오늘은 어제 배운 알고리즘의 좀 더 쉬운 기본문제를 풀었습니다. 하지만 기본 문제임에도 불구하고 오랜 시간이 걸려 4문제 밖에 풀지 못했습니다. 생각지 못한 equals와 contains 문제와 stack초기화 문제 알고리즘 문제를 풀때에 고려해야될 사항이 많다는 것을 느끼고 있습니다. 알고리즘 문제를 풀기 전에는 왜 기업들에서 알고리즘 코딩테스트를 보는지 이해를 하지 못했습니다. 너무 많은 지원자들이 있어 수준 이하 지원자들을 걸러내는 이유도 있겠지만 코드를 짜면서 고려해야될 문제와 효율적으로 작성을 할 수 있다는 점에서 코딩테스트를 보는 것 같습니다. 내일은 책에 있는 문제를 풀겠습니다.
import java.io.*;
import java.util.*;
public class Baek1874 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] arr = new int [n];
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
int [] arr2 = arr.clone();
Arrays.sort(arr2);
Stack<Integer> stack = new Stack<>();
int i = 0;
int j = 0;
//System.out.println(stack);
//stack = 1
while(j != n) {
if(stack.isEmpty()) {
stack.push(arr2[i]);
System.out.println("+");
}
if(arr[j] != stack.peek()) { //i 가 [0] 4 != 1 true
stack.push(arr2[i + 1]); // arr2[1] = 2 i = 1
System.out.println("+");
i++;
}
else if(arr[j] == stack.peek()) {
stack.pop();
System.out.println("-");
j++;
}
else {
System.out.println("NO");
}
}
}
}
내가 떠올린 풀이 해설
배열을 하나 더 만들어서 복사해서 정렬한 다음 배열 인덱스 탐색하는 i와 j를 만들어서 문제를 풀려고 했다.
peek으로 스택 최상단에 있는 수와 비교했을 때 복사한 배열의 수와 다르면 push 하고 같으면 pop을 하려고 했다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1874 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
int num = 1;
boolean result = true;
Stack<Integer> stack = new Stack<>();
StringBuffer bf = new StringBuffer();
for(int i = 0; i < n; i++) {
int su = arr[i];
if(su >= num) {
while(su >= num) {
stack.push(num++);
bf.append("+\\n");
}
stack.pop();
bf.append("-\\n");
}
else {
int k = stack.pop();
if(k < su) {
System.out.println("NO");
result = false;
break;
}
else {
bf.append("-\\n");
}
}
}
if(result) {
System.out.println(bf.toString());
}
}
}
문제점
예제 출력 1번은 내가 짠 코드로 가능했지만 예제 출력 2번은 구현하지 못했다.
인덱스로 배열을 탐색했을 때 인덱스가 다음으로 이동했을 때 비교하기 전 인덱스로 다시 돌아가는 것을 구현하지 못했다.
12번 문제 오큰수 구하기
잘못된 풀이
import java.io.*;
import java.util.*;
public class Baek17298 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Stack<Integer> stack = new Stack<>();
//int i = 1;
stack.push(arr[0]);
for(int j = 1; j < n; j++) {
for(int i = 1; i < n; i++) {
if(stack.peek() < arr[i]) {
stack.push(arr[i]);
System.out.print(arr[i] + " ");
while(stack.size() != 1) {
stack.pop();
}
stack.push(arr[i]);
}
else if(stack.peek() > arr[i]) {
}
else {
System.out.print("-1 ");
//i++;
}
}
}
br.close();
}
}
내가 떠올린 풀이 해설
위에 풀었던 문제와 비슷한 방식을 떠올렸다. 이중 for문으로 for문이 돌면서 스택에 peek으로 젤 위에 값과 배열의 다음 값을 비교하는데 배열의 값이 크면 스택에 push 했다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek17298 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] arr = new int[n]; //수열배열 생성
int [] answer = new int [n]; //정답 배열 생성
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Stack<Integer> stack = new Stack<>();
stack.push(0); // 처음에는 항상 스택이 비어 있으므로 최초 값을 push해 초기화
for(int i = 1; i < n; i++) {
//스택이 비어있지 않고 현재 수열이 스택 top 인덱스가 가리키는 수열보다 클 경우
while(!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
answer[stack.pop()] = arr[i]; // 정답 배열에 오큰수를 현재 수열로 저장하기
}
stack.push(i); //신규 데이터 push
}
while(!stack.isEmpty()) { //반복문을 다 돌고 나왔는데 스택이 비어 있지 않다면 빌 때까지
answer[stack.pop()] = -1; //스택에 쌓인 index에 -1을 넣고
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for(int i = 0; i < n; i++) {
bw.write(answer[i] + " ");
}
bw.close();
br.close();
}
}
문제점
위와 똑같은 문제가 있었다. 인덱스로 탐색을 해서 그 전으로 돌아와서 비교하는 법을 모르겠다.
그 전으로 돌아오지 못해 처음 5와 7을 잘 출력이 되는데 그 뒤로부터는 비교할 수가 없어서 -1, -1이 출력됩니다.
풀이를 보면 저번과 같이 BufferedWriter로 출력하는 것을 볼 수가 있는데 System.out.print로 출력을 할시 시간 초과가 발생합니다
13번 문제 카드 게임
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek2164 {
public static void main(String[] args) throws IOException{
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Queue<Integer> que = new LinkedList<>();
for(int i = 1; i <= n; i++) {
que.offer(i);
}
while(que.size() != 1) {
que.poll();
que.offer(que.poll());
}
System.out.println(que.poll());
}
}
내가 떠올린 풀이 해설
큐에 대한 선입 선출의 개념을 알고 있으면 쉽게 풀 수 있는 문제라고 생각한다. 카드의 개수의 최대가 500,000이므로 시간 복잡도의 제약도 크지 않다.
오늘의 회고
오늘은 자료구조의 알고리즘을 풀어봤는데 조건에 따라 구현하는 방법이 어려웠습니다. 책에 있는 문제들이 기본 문제도 있지만 많이 어려운 문제도 있어 시간이 오래 걸리는 것 같습니다. 알고리즘 공부하면서 느끼는 점은 시간이 지날수록 알고리즘 공부에 대한 방향성이 조금씩은 잡혀가고 있는 것 같습니다. 내일은 오늘 풀었던 문제 복습과 스택, 큐, 덱에 대한 오늘보단 쉬운 5문제를 풀겠습니다.
import java.io.*;
import java.util.*;
public class Baek11728 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int aSize = Integer.parseInt(st.nextToken());
int bSize = Integer.parseInt(st.nextToken());
ArrayList<Integer> list = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for(int i = 0; i < aSize; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
st = new StringTokenizer(br.readLine());
for(int i = 0; i < bSize; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
Collections.sort(list);
System.out.println(list);
}
}
잘못된 풀이
import java.io.*;
import java.util.*;
public class Baek11728 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int aSize = Integer.parseInt(st.nextToken());
int bSize = Integer.parseInt(st.nextToken());
int [] aArr = new int[aSize];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < aSize; i++) {
aArr[i] = Integer.parseInt(st.nextToken());
}
int [] bArr = new int [bSize];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < bSize; i++) {
bArr[i] = Integer.parseInt(st.nextToken());
}
int lt = 0;
int rt = 0;
ArrayList<Integer> list = new ArrayList<>();
while(rt < aSize && lt < bSize) {
if(aArr[rt] > bArr[lt]) {
list.add(bArr[lt]);
lt++;
}
else if(aArr[rt] < bArr[lt]) {
list.add(aArr[rt]);
rt++;
}
else {
lt++;
rt++;
}
}
while(rt < aSize) {
list.add(aArr[rt]);
rt++;
}
while(lt < bSize) {
list.add(bArr[lt]);
lt++;
}
System.out.println(list);
}
}
내가 생각한 풀이 해설
배열을 리스트에 담아서 출력하는 방법을 생각했다.
하지만 시간 초과가 나왔다. 다른 방식으로 투포인터 알고리즘으로 풀었는데도 시간 초과가 나왔다.(?)
계속 바꿔도 시간초과가 나왔는데 그 이유는 마지막에 정답을 출력할 때System.out.print를 사용하면 시간 초과가 나는 것이었다.
이것 때문에 시간을 많이 썼다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek11728 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int aSize = Integer.parseInt(st.nextToken());
int bSize = Integer.parseInt(st.nextToken());
ArrayList<Integer> list = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for(int i = 0; i < aSize; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
st = new StringTokenizer(br.readLine());
for(int i = 0; i < bSize; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
Collections.sort(list);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for(int i = 0; i < list.size(); i++) {
bw.write(list.get(i) + " ");
}
br.close();
bw.close();
}
}
백준 21921번 블로그
문제점
for문에서 max를 구할 때 크기만큼 달라지는 합해주는 값이 달라지는 것과 count에서 어려움을 느꼈습니다.
for문 안에서 while과 if로 처리해주는 것에 대한 이해가 필요할 것 같습니다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek21921 {
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 end = 0;
int sum = 0;
int max = 0;
int count = 1;
for(int i = 0;i < n; i++){
while((end - i < m) && end < n){
sum += arr[end];
end++;
}
if(max == sum){
count++;
}
else if(max < sum){
max = sum;
count = 1;
}
sum -= arr[i];
}
if(max == 0){
System.out.println("SAD");
return;
}
System.out.println(max);
System.out.println(count);
}
}
백준 3273번 두 수의 합
내가 생각한 풀이
어제 풀었던 투포인터 알고리즘을 사용해서 풀면 쉽게 풀리는 문제였다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek3273 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] arr = new int [n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int m = Integer.parseInt(br.readLine());
int i = 0;
int j = n - 1;
int cnt = 0;
Arrays.sort(arr);
while(i < j) {
if(arr[i] + arr[j] == m) {
cnt++;
i++;
j--;
}
else if(arr[i] + arr[j] < m) {
i++;
}
else {
j--;
}
}
System.out.println(cnt);
}
}
백준 14706번 구간 합 최대
문제점
위에 문제는 아직 해결을 하지 못했다. 고민을 많이 해봐야 될 것 같다. 또한 코드를 참고하려고 해도 아직까지 블로그에 올리신 분이 없습니다.
백준 2167번 2차원 배열의 합
내가 생각한 풀이
이와 비슷한 문제를 푼 적이 있어서 오래 걸리지는 않았다. 처음에 이 문제를 접했을 때 구간에서 다음 구간까지 더해주는 것에서 방법을 떠올리기 힘들었다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek2167 {
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 + 1][m + 1];
for(int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1; j <= m; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
int k = Integer.parseInt(br.readLine());
int sum;
for(int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
sum = 0;
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
for(int j = x1; j <= x2; j++) {
for(int t = y1; t <= y2; t++) {
sum += arr[j][t];
}
}
System.out.println(sum);
}
}
}
오늘의 회고
오늘은 시간 초과 문제로 시간을 많이 소비했습니다. 시간 초과가 났을 때 알고리즘 문제가 아니라 출력해주는 부분에도 시간초과가 날 수 있다는 것을 배웠습니다. 또한 아직도 투포인터에서 이해하지 못한 부분이 있습니다. 자료를 계속 찾아서 공부하고 이해하려고 노력해야 될 것 같습니다. 또한 오늘 해결하지 못한 문제는 내일 이어서 고민해보고 내일은 책에 연습문제 4문제를 풀겠습니다.
//답이 안나오는 풀이입니다.
import java.io.*;
import java.util.*;
public class Baek10986 {
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 cnt = 0;
int rem = 0;
int [] s = new int[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
s[i] = Integer.parseInt(st.nextToken());
}
for(int i = 0; i < n; i++) {
rem = 0;
for(int j = i; j < n; j++) {
rem += s[j];
if(rem % m == 0) {
cnt++;
}
}
}
System.out.println(cnt);
}
}
내가 떠올린 풀이 해설
첫째를 기준으로 하나씩 다 더해가면서 3으로나누고 나눠지는 수는 카운트 수 증가하고 그리고 왼쪽 배열 위치를 움직이면서 수를 하나씩 빼준다. 하지만 이렇게 풀었을 때 시간 오류가 나온다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek10986 {
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());
long cnt = 0;
long [] s = new long[n];
long [] c = new long[m];
st = new StringTokenizer(br.readLine());
s[0] = Integer.parseInt(st.nextToken());
for(int i = 1; i < n; i++) { //수열의 합 배열 만들기
s[i] = s[i - 1] + Integer.parseInt(st.nextToken());
}
for(int i = 0; i < n; i++) { //합 배열의 모든 값에 % 연산 수행하기
int rem = (int)(s[i] % m);
//0 ~ i 까지의 구간 합 자체가 0일 때 정답에 더하기
if(rem == 0) {
cnt++;
}
// 나머지가 같은 인덱스의 개수 카운트
c[rem]++;
}
for(int i = 0; i < m; i++) {
if(c[i] > 1) {
// 나머지가 같은 인덱스 중 2개를 뽑는 경우의 수를 더하
cnt = cnt + (c[i] * (c[i] - 1) / 2);
}
}
System.out.println(cnt);
}
}
문제점
시간 초과가 나온 이유는 N의 최대값이 106이라 모든 구간합을 구하기에 1초는 너무 짧다. 따라서 구간 합 배열을 이용해야 된다.
문제에서 구간 합 배열의 풀이 방법을 떠올리지 못했다. 또한 구간 합 배열의 개념이 부족했다.
나머지 합 배열 핵심 아이디어
1. (A+B)%C는 ((A%C) + (B%C))%C와 같다 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.
2. S[i] - S[j] 는 원본 배열의 j+1 부터 i 까지의 구간 합이다.
3. S[i] % M 값과 S[j] % M의 값이 같다면 (S[i] - S[j]) % M은 0이다. 즉 구간 합 배열의 원소를 M으로 나눈 나머지 값을 업데이트하고 4. S[i] 와 S[j] 가 같은 (i,j)쌍을 찾으면 원본 배열에서 j + 1부터 i 가지의 구간 합이 M으로 나누어떨어진다는 것을 알 수 있다.
6번 문제 수들의 합 5
잘못된 풀이
import java.io.*;
import java.util.*;
public class Beak2018 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int cnt = 0;
int sum = 0;
for(int i = 1; i <= n; i++) {
sum = 0;
for(int j = i; j <= n; j++) {
sum = sum + j;
if(sum == n) {
cnt++;
}
}
}
System.out.println(cnt);
}
}
내가 떠올린 풀이 해설
앞에와 비슷한 방식으로 풀었습니다. for문으로 j가 하나씩 증가 시키면서 더해주고 n이랑 같으면 cnt를 늘려주고를 15번 실시한다.
안에 있는 for문이 다 돌면 sum을 0으로 초기화 시켜주고 i의 for문이 실행된다 이를 15번 실시한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek2018 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int cnt = 1;
int sum = 1;
int start_index = 1; // 시작 인덱스 추가
int end_index = 1; // 끝 인덱스 추가
while(end_index != n) {
if(sum == n) {
cnt++;
end_index++;
sum = sum + end_index; // sum == n; end_index++; sum = sum + end_index; cnt++;
} else if(sum > n) {
sum = sum - start_index;
start_index++;
} else {
end_index++;
sum = sum + end_index;
}
}
System.out.println(cnt);
}
}
문제점
시간 초과가 나온 이유는 N의 최대값이 10,000,000으로 매우 큰 수로 잡혀있다. 이런 상황에서는 O(nlogn)의 알고리즘이 아닌 O(n)의 시간 복잡도 알고리즘을 사용해야 된다. 이런 경우 자주 사용하는 방법은 투 포인터이다.
투 포인터 핵심 아이디어
배열의 index를 탐색하는 start_index와 end_index를 만들어서 배열에서 예를 들어 sum과 n이 같으면 카운트 수 하나 증가시켜주고 end_index를 한 칸 이동하고 sum = sum + end_index를 해준다. 만약 sum이 n 보다 크면 start_index를 한칸 이동하고 sum = sum - start_index를 해준다. 만약 sumd이 n보다 작으면 end_index를 한칸 이동하고 sum = sum + end_index를 해준다.
7번 문제 주몽
정확한 풀이
import java.util.*;
import java.io.*;
public class Baek1940 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int [] arr = new int[n];
int cnt = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int i = 0;
int j = n -1;
while (i < j) {
if(arr[i] + arr[j] == m) {
i++;
j--;
cnt++;
}
else if(arr[i] + arr[j] < m) {
i++;
}
else {
j--;
}
}
System.out.println(cnt);
}
}
투 포인터 핵심 아이디어
6번 문제와 같은 투포인터 문제입니다.
n의 크기가 15,000이므로 O(nlogn)인 시간 복잡도 알고리즘을 사용해도 문제가 없다.
일반적으로 정렬 알고리즘의 시간 복잡도가 O(nlogn)입니다. 여기에서는 재료 데이터를 배열에 저장시킨 후 오름차순 정렬을 합니다.
투 포인터 i, j 를 양쪽 끝에 둔 후에 포인터 이동 원칙을 활용해 탐색한다.
투포인터 이동 원칙
while 조건 (i < j) 일 때까지 반복한다.
A [i] + A[j] > M : j--; // 번호의 합이 M보다 크므로 큰 번호 index를 내립니다.
A[i] + A[j] < M : j++; // 번호의 합이 M보다 작으므로 작은 번호 index를 올립니다.
A[i] + A[j] == M : i++; j--; count++; // 양쪽 포인터를 모두 이동시키고 count를 증가시킵니다
8번 문제 좋다
문제 해설
n의 개수가 최대 2,000이라 가정해도 좋은 수 찾는 알고리즘의 시간 복잡도는 N^2의 보다 작아야 합니다.
이 문제의 알고리즘의 시간복잡도는 최소 O(nlogn)이어야 합니다. 정렬이나 투 포인터를 사용해야 된다.
단 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안 된다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1253 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i< n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int cnt = 0;
Arrays.sort(arr);
for(int k = 0; k < n; k++) {
long find = arr[k];
int i = 0;
int j = n - 1;
while(i < j) {
if(arr[i] + arr[j] == find) {
if(i != k && j != k) {
cnt++;
break;
}
else if(i == k) {
i++;
}
else if(j == k) {
j--;
}
}
else if(arr[i] + arr[j] < find) {
i++;
} else {
j--;
}
}
}
System.out.println(cnt);
br.close();
}
}
9번 문제 DNA 비밀번호
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek12891 {
static int [] checkArr;
static int [] myArr;
static int checkInt;
static int result;
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());
char [] str = br.readLine().toCharArray();
checkArr = new int [4];
myArr = new int [4];
checkInt = 0;
result = 0;
st = new StringTokenizer(br.readLine());
for(int i = 0; i < 4; i++) {
checkArr[i] = Integer.parseInt(st.nextToken());
if(checkArr[i] == 0) {
checkInt++;
}
}
for(int i = 0; i < m; i++) {
Add(str[i]);
}
if(checkInt == 4) {
result++;
}
for(int i = m; i < n; i++) {
int j = i - m;
Add(str[i]);
Remove(str[j]);
if(checkInt == 4) {
result++;
}
}
System.out.println(result);
br.close();
}
private static void Remove(char c) {
switch(c) {
case 'A' :
if(myArr[0] == checkArr[0]) {
checkInt--;
}
myArr[0]--;
break;
case 'C' :
if(myArr[1] == checkArr[1]) {
checkInt--;
}
myArr[1]--;
break;
case 'G' :
if(myArr[2] == checkArr[2]) {
checkInt--;
}
myArr[2]--;
break;
case 'T' :
if(myArr[3] == checkArr[3]) {
checkInt--;
}
myArr[3]--;
break;
}
}
private static void Add(char c) {
switch(c) {
case 'A' :
myArr[0]++;
if(myArr[0] == checkArr[0]) {
checkInt++;
}
break;
case 'C' :
myArr[1]++;
if(myArr[1] == checkArr[1]) {
checkInt++;
}
break;
case 'G' :
myArr[2]++;
if(myArr[2] == checkArr[2]) {
checkInt++;
}
break;
case 'T' :
myArr[3]++;
if(myArr[3] == checkArr[3]) {
checkInt++;
}
break;
}
}
}
문제 해설
슬라이딩 윈도우를 이용하는 문제이다. 위의 문제는 n의 크기가 1,000,000이기 때문에 시간 복잡도 O(n)의 시간 복잡도를 이용하여 풀어야 된다. 슬라이딩 윈도우는 시간 복잡도가 O(n)입니다. 길이가 P인 윈도우를 지정하여 배열 S의 시작점에 놓습니다. 그런 다음 윈도우를 오른쪽으로 밀면서 윈도우에 잡힌 값들이 조건에 맞는지 탐색합니다. 배열의 S의 길이만큼 탐색을 진행하면 되므로 O(n)의 시간 복잡도를 가집니다.
오늘의 회고
오늘 코딩테스트를 대비하려고 코딩테스트를 한번 풀어봤습니다. 많은 시간을 투자해서 풀려고 노력했지만 답은 나왔어도 시간 초과나 풀지 못하는 문제가 있었습니다. 알고리즘은 효율적인 방식으로 해결해 나가야 되지만 풀이 방식을 떠올리는 것은 쉽지만은 않은 것 같습니다.
좌절하지 않고 천천히 하반기 공채까지 진행해보겠습니다. 내일은 오늘 부족했던 문제들 복습하고 오늘보다 난의도가 쉬운 문제 투 포인터 2문제, 구간 합 2문제, 슬라이딩 윈도우 1문제를 풀어보겠습니다.
