0%

작성일 Edited on In Disqus:

Baekjoon Online Judge - 2751

Review

  • 병합 정렬로 풀었다.
  • 병합 정렬부터 조금 어려워져서 예제를 보고 풀었다.
  • 이건 참고한 동영상과 예제. 아직 갈 길이 멀다.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.util.*;

public class Main {

  private static void mergeSort(int[] arr) {
    int[] temp = new int[arr.length];
    mergeSort(arr, temp, 0, arr.length - 1);
  }

  private static void mergeSort(int[] arr, int[] temp, int start, int end) {

    //반으로 나눠서
    if(start < end) {
      int mid = (start + end) / 2;

      // 재귀 호출
      mergeSort(arr, temp, start, mid);
      mergeSort(arr, temp, mid + 1, end);

      // 쪼갠 다음에 병합
      merge(arr, temp, start, mid, end);
    }
  }

  private static void merge(int[] arr, int[] temp, int start, int mid, int end) {

    // 임시 배열에 넣음
    for (int i = start; i <= end; i++) {
      temp[i] = arr[i];
    }

    int part1 = start;
    int part2 = mid + 1;
    int index = start;

    // 두 개의 배열을 모두 돌 때까지
    while (part1 <= mid && part2 <= end) {
      // 비교해서 arr에 삽입
      if(temp[part1] <= temp[part2]) {
        arr[index] = temp[part1];
        part1++;
      } else {
        arr[index] = temp[part2];
        part2++;
      }
      index++;
    }

    // 뒤쪽 배열은 비였고, 앞쪽 배열에 데이터가 남아있는 경우
    // 앞쪽 포인터가 배열의 끝에서 남은 만큼을 돌면서
    // 최종적으로 저장할 배열에 남은 값들을 붙여줌
    for(int i = 0; i <= mid-part1; i++) {
      arr[index + i] = temp[part1 + i];
    }
  }

  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];

    for (int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
    }

    mergeSort(arr);

    for (int i = 0; i < n; i++) {
      System.out.println(arr[i]);
    }
    sc.close();
  }

}

작성일 Edited on In Disqus:

Baekjoon Online Judge - 10799

Review

  • 저번에 풀었던 괄호 9012 문제를 응용해서 풀면 쉽게 풀린다.
  • 포인트는 라인 23~27이다. ‘))’ 이렇게 중첩이 된 경우, 쇠파이프가 끊긴 거니 1을 더해주면 된다.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.util.*;

public class Main {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		String s;
		s = sc.next();

		Stack stack = new Stack();

		int cnt = 0;
		int res = 0;

		for(int j = 0; j < s.length(); j++) {
			if(s.charAt(j)=='(') {
				stack.push(1);
				cnt++;
			} else if(s.charAt(j)==')') {
				if(stack.size != 0) {
					stack.pop();
					cnt--;
					if(s.charAt(j-1)=='(') {
						res += cnt;
					} else {
						res++;
					}
				}
			}
		}
		System.out.println(res);
		sc.close();
	}

	static class Stack {
		private int size = 0;
		private SNode top = null;

		private class SNode {
			int data;
		    private SNode next;
		}

		public void push(int x) {
			SNode node = new SNode();
			node.data = x;
			node.next = top;
			top = node;
			size++;
		}

		public void pop() {
			top = top.next;
			size--;
		}
	}
}

작성일 Edited on In Disqus:

Baekjoon Online Judge - 2750

Review

  • 무슨 정렬로 풀까 하다가 선택 정렬로 풀었다.
  • 입력 부분을 작성한 다음 선택 정렬을 구현하면 된다.
  • 선택 정렬은 O(n²) 시간복잡도를 가졌다. 기억하자.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;
import java.util.Arrays;

public class Main {
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    int[] arr = new int[n];
    int i, j, temp, min;

    // 숫자 하나씩 배열에 넣기
    for (i = 0; i < n; i++) {
      int data = sc.nextInt();
      arr[i] = data;
    }

    sc.close();

    for(i = 0; i < arr.length; i++) {
      // 최솟값 초기화
      min = i;
      for(j = i+1; j < arr.length; j++) {
        // 배열에서 최솟값 찾기
        if(arr[min] > arr[j]) {
          min = j;
        }
      }

      // 값 바꾸기
      temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;

      // 출력
      System.out.println(arr[i]);
    }
  }
}

작성일 Edited on In Disqus:

Baekjoon Online Judge - 2292

Review

  • 벌집은 ‘1-7-19-37…’ 즉, 6의 배수만큼 더해저 늘어난다.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

public class Main {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		
		int input = sc.nextInt();
		int six = 0;
		int room = 1;
		int count = 1;
		sc.close();
		
		// 6의 배수씩 늘어나다 input보다 커질 경우 멈춤
		while (room < input) {
			// 6의 배수만큼 늘어남
			six += 6;
			room += six;
			
			// 6씩 늘어날 때마다 1을 더함
			count ++;	
		}
		System.out.println(count);
	}
}

작성일 Edited on In Disqus:

Baekjoon Online Judge - 9012

Review

  • 굳이 스택으로 풀지 않아도 될 것 같은데 연습 겸 일부러 저번에 했던 스택 문제를 응용해서 풀었다.
  • ‘)’ 처리가 정말 중요했던 문제. 정말 고생 많이 했다. 17~23번 라인이 핵심인데, 만약 문자가 ‘)’인 경우 스택이 비어있지 않으면 무조건 false 처리를 한다.
  • 맞왜틀일 경우 반례를 보자.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.*;

public class Main {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s;
		
		while(n-->0) {
			boolean isVPS = true;
			Stack stack = new Stack();
			s = sc.next();
			
			for(int j = 0; j < s.length(); j++) {
				if(s.charAt(j)=='(') {
					stack.push(1);
				} else if(s.charAt(j)==')') { 
					if(stack.size != 0) {
						stack.pop();
					} else {
						isVPS = false;
					}
				}
			}
			if (stack.size !=0) {
				isVPS = false;
			}
			
			if(isVPS) {
                System.out.println("YES");
            }else {
                System.out.println("NO");
            }
		}
		sc.close();
	}
	
	static class Stack {
		private int size = 0;
		private SNode top = null;
		
		private class SNode {
			int data;
		    private SNode next;
		}
		
		public void push(int x) {
			SNode node = new SNode();
			node.data = x;
			node.next = top;
			top = node;
			size++;
		}
		
		public void pop() {
			top = top.next;
			size--;
		}
	}
}