5주차_백준 문제풀이

목차

1. 문제 9012

2. 문제 1158

3. 문제 2743

---

1. 문제 9012

풀이

package etc;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class baekjoon9012 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i=0; i < T; i++) {
			sb.append(solve(br.readLine())).append('\n');
		}
		System.out.println(sb);
	}
	
	public static String solve(String s) {
		Stack<Character> stack = new Stack<>();
		
		for(int i = 0; i<s.length(); i++) {
			char c = s.charAt(i);
			
			if(c == '(') {
				stack.push(c);
			}
			
			else if(stack.empty()) {
				return "NO";
			}
			else {
				stack.pop();
			}
		}
		if(stack.empty()) {
			return "YES";
		}
		else {
			return "NO";
		}
	}
}

기본설명

1. 여는 괄호와 닫는 괄호가 올바른 경우

Ex: ( ( ) ( ) ) ( ( ( ) ) )

완전한 수식인 경우 최종적으로 스택에 아무 것도 없어야 한다.

2. 괄호가 남는 경우 (= 여는 괄호가 많은 경우)

예시 : ( ( ( ( ) ( ) ) ( )

모든 괄호를 검사한 후 스택에 괄호가 남는 경우는 여는 괄호가 많은 경우라는 의미다. 즉, 이는 온전한 수식이 아니라는 것이다.

3. 괄호가 부족한 경우 (= 닫는 괄호가 많은 경우)

예시 : ( ( ) ) ( ) )

보면 알겠지만, 이미 6번째 단계에서 pop 을 하면 스택은 비어버리게 된다. 스택이 비었다는 것은 현재 단계까지는 완전한 수식이라는 것이다. 근데 그 다음 단계에서도 닫는 괄호가 나온다면 이미 비어있는 상태에서 더이상 pop 할 요소가 없기 때문에 이는 잘못 된 참조가 되어버리게 된다.

 

즉, 다른 말로 하자면 이는 닫는 괄호가 더 많다는 것이다.

코드설명

public static String solve(String s) {
		Stack<Character> stack = new Stack<>(); //괄호를 넣을 stack를 만들어준다.
		
		for(int i = 0; i<s.length(); i++) {
			char c = s.charAt(i); //하나씩 괄호를 꺼낸다.
			
			if(c == '(') { //만약 여는 괄호일 경우 stack에 push한다.
				stack.push(c);
			}
			
			else if(stack.empty()) { //닫는 괄호를 입력받았으나 pop할 원소가 없는 경우
				return "NO";
			}
			else { //그 외의 경우 즉, 닫는 괄호일 경우 pop한다.
				stack.pop();
			}
		}
		if(stack.empty()) {
			return "YES"; //for문이 끝난 후 최종적으로 empty면 yes
		}
		else {
			return "NO"; //for문이 끝난 후 최종적으로 (가 남아 있으면 No
		}
	}

---

2. 문제 1158

풀이

import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class baekjoon1185 {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		int temp;
		Queue<Integer> Q = new LinkedList<>();
		for(int i = 1; i<=n; i++)
			Q.add(i);
		
		sb.append("<");
		 while(Q.size() != 1) {
	     // K - 1번째까지는 처음에 있던 값을 맨 뒤로 보낸다.
		for (int i = 0; i < k - 1; i++) {
	          Q.offer(Q.poll());
	        }
	            // K번째 값은 poll한 후 출력한다.
	       sb.append(Q.poll() + ", ");
	    }
		sb.append(Q.poll() + ">");;
		System.out.println(sb);
		bf.close();
	}
}

기본설명

(N, K)가 주어질 때 (7, 3) 이면 숫자가 [1, 2, 3, 4, 5, 6, 7]로 나열된다.

 

| 숫자 | -> 다음 K 번째 숫자 제거

 

[1, 2, |3|, 4, 5, 6, 7] -> <3>

[1, 2, 4, 5, |6|, 7] -> <3, 6>

[1, |2|, 4, 5, 7] -> <3, 6, 2>

[1, 4, 5, |7|] -> <3, 6, 2, 7>

[1, 4, |5|] -> <3, 6, 2, 7, 5>

[|1|, 4] -> <3, 6, 2, 7, 5, 1>

[|4|] -> <3, 6, 2, 7, 5, 1, 4>

 

다음 K번째 까지 가는데 실제 이동은 K-1만큼 이동한다.

그렇기 때문에 삭제가 용이한 연결리스트인 Linked List를 활용하기로 했다.

Queue를 이용해서 K -1번째까지 첫 번째 값을 맨 뒤로 보내고

K번째 일 때는 poll로 출력한다.

Queue 사이즈가 1일 때 까지 반복한다. (Queue가 1개면 그것만 빼서 출력하면 되기 때문)

코드설명

int temp;
Queue<Integer> Q = new LinkedList<>(); //Queue 인터페이스로 LinkedList를 생성
for(int i = 1; i<=n; i++)
	Q.add(i); // 받은 N만큼 숫자를 add한다.
		
sb.append("<");

 

1부터 N까지 Queue에 add한다.

while(Q.size() != 1) {
      // K - 1번째까지는 처음에 있던 값을 맨 뒤로 보낸다.
      for (int i = 0; i < k - 1; i++) {
          Q.offer(Q.poll()); //k-1까지 값을 poll해서 다시 offer하여 순환한다.
      }
      // for문을 나온 K번째 값은 poll한 후 출력한다.
      sb.append(Q.poll() + ", ");
     }

---

3. 문제 2743

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class baekjoon2743 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		
		System.out.println(str.length());
	}
}

코드 설명

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();//str로 String 문자열을 받는다.
		
		System.out.println(str.length()); //str의 길이를 출력한다.