[swexpert] Intermediate / Stack1 / 1217, 1218, 1219

🅰 1217. 거듭제곱

​

✏️ 문제 풀이

- 재귀호출을 이용하여 주어지는 입력값을 통해 거듭제곱 값을 구하는 문제이다.

- Function(N,M) 함수를 만들어 M만큼 N을 곱해야 하므로

- Function(N, M-1)을 통해 재귀호출을 구현하였다.

​

✏️ 소스코드

package stack1;

import java.util.*;

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

		for (int test_case = 1; test_case <= 10; test_case++) {
			int T = sc.nextInt();
			int N = sc.nextInt();
			int M = sc.nextInt();

			System.out.println("#"+test_case+" "+Function(N, M));
		}

	}

	public static int Function(int N, int M) {
		if (M == 1)
			return N;
		else
			return Function(N, M - 1) * N;
	}
}

 

✅ 후기

​

재귀함수에 대해 직접 구현해보니 설명으로만 들었던 것과는 달리 더 자세하게 알게되었다.

---

🅰 1218. 괄호 짝짓기

​

✏️ 문제 풀이

- 입력값에는 문장의 길이와, 괄호 문장이 들어온다.

- Java의 Stack 클래스를 이용하여 문제를 풀었다.

- 여는 괄호가 들어오면 stack.add()를 이용하여 입력을 해주었고, (stack.push()도 사용 가능하다.)

- 닫는 괄호가 들어오면 stack.peek()를 이용하여 닫는 괄호와 stack의 top값이 같으면 stack.pop()을 이용하여 여는 괄호를 삭제해주었다.

- 만약 닫는 괄호와 stack의 top 값이 다르면 Loop1 break; 를 통해서 반복과정을 종료하여 유효하지 않은 문자열임을 알려주었다.

- 또한 모든 문자열을 탐색하였을때에 stack.isEmpty()를 이용하여 stack에 값이 남아있으면 유효하지 않은 문자열임을 알려주었다.

- 모든 문자열을 탐색하였을 때 stack.isEmpty()를 이용하여 값이 true이면 result = 1;을 하여 유효한 문자열임을 알려주었다.

​

✏️ 소스코드

package stack1;

import java.util.*;

public class Sw1218 {
	public static void main(String[] args) {
		Stack<String> s = new Stack<>();
		Scanner sc = new Scanner(System.in);

		for (int test_case = 1; test_case <= 10; test_case++) {
			int T = sc.nextInt();
			char[] bracket = new char[T];
			String str = sc.next();
			int result = 0;

			Loop1: for (int i = 0; i < bracket.length; i++) {
				bracket[i] = str.charAt(i);

				switch (bracket[i]) {
				case '{':
					s.add("{");
					break;
				case '[':
					s.add("[");
					break;
				case '(':
					s.add("(");
					break;
				case '<':
					s.add("<");
					break;

				case '}':
					if (s.peek() == "{") {
						s.pop();
						break;
					} else {
						s.clear();
						break Loop1;
					}
				case ']':
					if (s.peek() == "[") {
						s.pop();
						break;
					} else {
						s.clear();
						break Loop1;
					}
				case ')':
					if (s.peek() == "(") {
						s.pop();
						break;
					} else {
						s.clear();
						break Loop1;
					}
				case '>':
					if (s.peek() == "<") {
						s.pop();
						break;
					} else {
						s.clear();
						break Loop1;
					}
				}
				if (i == bracket.length - 1 && s.empty() == true)
					result = 1;
			}
			System.out.printf("#%d %d \n", test_case, result);
		}
	}
}

✅ 후기

​

Stack을 배열을 이용하여 직접 구현하려고 했으나, Java에서 제공하는 Stack 클래스를 이용하니 훨씬 쉽고 빠르게 top값을 찾아내고, 비교할 수 있었다.

---

🅰 1219. 길찾기

​

✏️ 문제 풀이

​

- 출발점은 0, 도착점은 99로 표시되는 길찾기 문제이다.

-문제에 나온 것처럼 size[100] 배열 2개를 선언하여 각 정점의 번호를 주소로 사용하고, 저장되는 데이터는 각 정점에서 도착하는 정점의 번호를 저장하였다.

- 데이터 입력 시 순서쌍의 길이 만큼 반복하였으며, i가 짝수 or 홀수인지를 비교하여 2개의 배열에 데이터가 들어가도록 하였다.

- 지금와서 생각해보니 0 1, 1 4, 0 2순서로 데이터가 들어오면 같은 배열에 데이터가 중복으로 들어가는 문제가 있네,, 근데 어떻게 통과했지 데이터 입력받는 부분은 다시한번 생각해 봐야겠다..........

- Stack을 이용하여 DFS를 구현하였다.

- 출발지인 0을 Stack에 넣고 들어간 값을 pop한뒤 자식노드를 찾아 stack에 push 하였다.

- 마찬가지로 stack에 top에 있는 값을 pop하여서 그 값의 자식노드를 찾아 stack에 push 하였다.

- 노드가 stack에 중복하여 들어가지 않도록 boolean visited 함수를 이용하여 방문 했는지 안했는지를 확인했다.

- stack이 자식노드를 찾아 돌다가 99의 값이 pop되면 result = 1을 하여 도착지로 가는 길이 존재함을 표현했다.

​

✏️ 소스코드

package stack1;

import java.util.*;

public class Sw1219 {

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

		for (int test_case = 1; test_case <= 10; test_case++) {

		Stack<Integer> stack = new Stack<>();
		int[] S1 = new int[100];
		int[] S2 = new int[100];

		int T = 0;
		int N = 0;
		int addr = 0;
		int result = 0;
		T = sc.nextInt();
		N = sc.nextInt();

		boolean[] visited = new boolean[100];

		// 데이터 입력
		for (int i = 0; i < N; i++) {
			addr = sc.nextInt();
			if (i % 2 == 0) {
				S1[addr] = sc.nextInt();
			} else {
				S2[addr] = sc.nextInt();
			}
		}

		stack.push(0);
		while (!stack.isEmpty() == true) {
			int v = stack.pop();
			if (v == 99) {
				result = 1;
			}
			if (S1[v] > 0 && visited[S1[v]] == false) {
				stack.push(S1[v]);
				visited[S1[v]] = true;
			}
			if (S2[v] > 0 && visited[S2[v]] == false) {
				stack.push(S2[v]);
				visited[S2[v]] = true;
			}
		}
		System.out.printf("\n#%d %d", test_case, result);
	}
	}
}

✅ 후기

​

처음 구현을 할때에는 되게 쉽겠다 생각을 했었는데 막상 구현해보니 생각대로 되지를 않았다.

그래서 찾아보던 중 DFS를 이용하여 완전탐색을 하는 기법을 알게되었고, 그 방법대로 구현을 하니 정답이 나왔다.

DFS와 BFS에대해 더 자세히 공부하고 완벽하게 익혀서 변형문제가 나오더라도 잘 적용할 수 있도록 공부해야겠다,