2504 괄호의 값
📌문제 링크
https://www.acmicpc.net/problem/2504
💡 문제 풀이
먼저 올바른 괄호열을 체크하는 알고리즘을 구현했다.
- 문자열 길이만큼 반복을 수행한다.
- 현재 문자열이 여는 괄호라면 stack push한다.
- 현재 문자열이 닫는 괄호라면 stack pop한 값이 같은 종류의 여는 괄호인지 확인한다. 맞다면 유효하고, 아니라면 유효하지 않다.
- 반복이 끝난 후 stack에 요소가 남아있으면 올바른 괄호가 아니다.
그런데 괄호의 값을 계산하는 방법을 찾는 게 어려워서 구글링했다..
분배 법칙을 사용해서 문제를 풀 수 있다. ( ( ) [ [ ] ] ) 의 경우에 2x(2+3x3)으로 계산되는데, 이는 결국 (2x2) + (2x3x3)과 같다. 왼쪽 괄호가 나오면 temp에 2나 3을 곱한 뒤 스택에 push 하고, 오른쪽 괄호가 나오면 temp를 2나 3으로 나눈 뒤 스택을 pop 한다. 이때 ( ( ) [ [ ] ] ) 표시된 괄호처럼 괄호 값이 '( )' 또는 '[ ]'일 경우에는 temp 값을 나눠주기 전에 answer에 더한다.
temp: answer에 더하기 전 중간값을 계산하기 위한 변수 (initial value: 1)
1. case ' ( '
temp에 2를 곱하고 스택에 ' ( ' 를 push
2. case ' ) '
1) 스택이 비어있거나 스택 top이 ' ( ' 가 아닌 경우
올바르지 못한 괄호열이므로 answer = 0; break;
2) 이전 문자열이 ' ( ' 일 경우
괄호 값이 '( )' 이므로 계산된 temp 값을 answer에 더해주고 temp를 2로 나눈다. 스택을 pop 한다.
3) 이전 문자열이 ' ( ' 가 아닐 경우
제일 안쪽 괄호, 즉 '( )' 형태가 아니므로 이미 answer에 값이 더해져 있는 상태이다. 따라서 answer에 값을 더하지 않고 temp를 2로 나누고 스택 pop을 한다.
3, 4. case ' [ ', ' ] '
1, 2와 유사하게 처리한다.
마지막으로 만약 문자열을 다 읽었는데 스택이 비어있지 않다면, 올바르지 못한 괄호열이므로 answer = 0을 대입한다.
출처 : https://mjmjmj98.tistory.com/70
위 풀이를 참고해서 풀었다.
📋코드
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 닫는 괄호 - 여는 괄호 쌍을 쉽게 검색하기 위해 Map 사용
// 닫는 괄호를 만났을 때 stack pop한 값이 여는 괄호인지를 검사하므로 닫는 괄호를 key, 여는 괄호를 value로 설정
Map<String, String> hm = new HashMap<String, String>();
hm.put(")", "(");
hm.put("]", "[");
// 괄호의 값을 쉽게 계산하기 위해 Map 사용
Map<String, Integer> val = new HashMap<>();
val.put("(", 2);
val.put(")", 2);
val.put("[", 3);
val.put("]", 3);
int answer = 0; // 정답을 출력할 변수
String[] arr = sc.nextLine().split(""); // 괄호열 입력
// 올바른 괄호를 검사하기 위한 stack
Stack<String> stack = new Stack<>();
// i-1번째와 비교해야 하므로 0번째를 stack push하고 1부터 반복문 수행
stack.push(arr[0]);
int tmp = val.get(arr[0]); // 값을 계산하기 위한 변수
for (int i = 1, size = arr.length; i < size; i++) {
// 여는 괄호라면 stack push
if (hm.containsValue(arr[i])) {
stack.push(arr[i]);
// 괄호의 값만큼 곱함
tmp *= val.get(arr[i]);
}
// 닫는 괄호일 때
else if (hm.containsKey(arr[i])) {
// stack의 top의 값이 같은 괄호의 여는 괄호가 아니면 유효하지 않음
// 여기서 stack.isEmpty 조건 추가 안하면 런타임 에러난다.. (닫는 괄호만 들어왔을 때 에러)
if (stack.isEmpty() || !hm.get(arr[i]).equals(stack.pop())) {
answer = 0;
break;
} else if (hm.containsValue(arr[i-1])) { // 이전 문자열이 여는 괄호라면
answer += tmp; // (), []의 형태 -> 계산된 값을 더해줌
tmp /= val.get(arr[i]); // 괄호의 값을 나눠줌
} else if (hm.containsKey(arr[i-1])) { // 이전 문자열이 닫는 괄호라면
tmp /= val.get(arr[i]); // 이미 이전 문자열이 여는 괄호일 때 값을 더해줬으므로 값을 더하지 않고 괄호의 값만큼 나눠줌
}
}
}
// 올바른 괄호가 아닐 때
if (answer == 0 || !stack.isEmpty()) {
System.out.println(0);
} else { // 올바른 괄호일 때
System.out.println(answer);
}
}
}⏱ 시간 복잡도
입력받은 문자열 길이만큼 반복하므로 O(N)
1874 스택 수열
📌문제 링크
https://www.acmicpc.net/problem/1874
💡 문제 풀이
- 1부터 n을 차례대로 stack에 push한다고 했으므로 반복문을 돌며 현재 값 i를 stack에 값을 넣는다. (+출력)
- 만약 i가 입력된 수열의 첫 번째 숫자와 같다면 stack을 pop하고 수열의 다음 숫자로 넘어간다. (-출력) 수열의 숫자가 stack top의 숫자보다 커질 때까지 반복한다.
-> 수열의 숫자와 stack top 값이 같지 않으면 불가능한 경우이므로 NO를 출력하고 종료한다.
📋코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
Stack<Integer> stack = new Stack<>();
StringBuilder sb = new StringBuilder(10);
// 수열 입력
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
int idx = 0; // 수열의 index
// 1부터 N까지 오름차순으로 stack push
for (int i = 1; i <= N; i++) {
stack.push(i);
sb.append("+\n");
// 수열의 idx번째 값이 i값보다 작거나 같으면
while(idx < N && arr[idx] <= i) {
// stack을 pop하고 idx 다음으로 옮김
if(stack.pop() != arr[idx++]) {
// 같지 않으면 불가능한 경우
System.out.println("NO");
System.exit(0);
} else {
// 같으면 - 출력
sb.append("-\n");
}
}
}
System.out.print(sb);
}
}⏱ 시간 복잡도
1부터 N까지 for문에서 반복을 수행하고 그 안에서 while문에서 반복을 수행한다.
최대 반복 횟수가 push N번 (for문), pop N번 (while문)이므로 2N번 반복한다.
-> 시간복잡도 : O(N)
1966 프린터 큐
📌문제 링크
https://www.acmicpc.net/problem/1966
💡 문제 풀이
📋코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
// 테스트 케이스만큼 반복
for (int i = 0; i < T; i++) {
Queue<int[]> queue = new ArrayDeque<int[]>();
stk = new StringTokenizer(br.readLine());
int N = Integer.parseInt(stk.nextToken());
int M = Integer.parseInt(stk.nextToken());
// 가장 높은 중요도를 찾기 위한 중요도 배열
int[] prior = new int[N];
// 입력
stk = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
int num = Integer.parseInt(stk.nextToken());
prior[j] = num; // 중요도 배열에 입력
// Queue에 {중요도, 궁금한 문서 여부} enqueue
// 궁금한 문서라면 두 번째 원소를 1로, 아니라면 0으로 함
if (j == M) queue.offer(new int[] {num, 1});
else queue.offer(new int[] {num, 0});
}
// 중요도 배열 오름차순 정렬
Arrays.sort(prior);
int cnt = 0; // 인쇄된 문서 개수 count
while(!queue.isEmpty()) {
int[] cur = queue.poll();
// 현재 문서의 중요도가 가장 높다면
if (cur[0] == prior[N-1]) {
// 궁금한 문서일 경우
if (cur[1] == 1) {
sb.append(++cnt).append("\n");
break;
} else { // 아닐 경우
N--; // 현재 가장 높은 중요도 갱신 (prior의 index 갱신)
cnt++;
}
} else { // 아니라면 다시 queue에 넣음
queue.offer(cur);
}
}
}
System.out.print(sb);
}
}⏱ 시간 복잡도
입력 : O(N)
정렬 : O(NlogN)
탐색 : 1부터 100까지 순서대로 문서가 들어가있고, 궁금한 문서의 중요도가 1인 최악의 경우 N번 인쇄하고 그 때마다 queue에서 문서를 빼고 넣는 것을 N번 반복 -> O(N^2)
-> 시간복잡도 : O(N^2)
2075 N번째 큰 수
📌문제 링크
https://www.acmicpc.net/problem/2075
💡 문제 풀이
우선순위 큐로 구현했다.
우선순위 큐는 숫자를 오름차순으로 정렬하므로 -1을 곱한 값으로 queue에 넣고, N번만큼 dequeue한 뒤 다시 -1을 곱해 답을 구했다.
📋코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
PriorityQueue<Integer> queue = new PriorityQueue<>();
StringTokenizer stk;
// 우선순위 큐에 넣음
for (int i = 0; i < N; i++) {
stk = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
queue.offer(-Integer.parseInt(stk.nextToken()));
}
}
// N-1번 dequeue
for (int i = 0; i < N-1; i++) {
queue.poll();
}
// N번째 수 dequeue
System.out.println(-queue.poll());
}
}⏱ 시간 복잡도
입력 : O(N*N)
N번째 큰 수 구하기 : O(N)
-> 시간복잡도 : O(N*N)
14425 문자열 집합
📌문제 링크
https://www.acmicpc.net/problem/14425
💡 문제 풀이
문제 그대로.. 직관적으로 문자열 집합을 만들어서 구현했다.
📋코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
int N = Integer.parseInt(stk.nextToken());
int M = Integer.parseInt(stk.nextToken());
// 집합에 문자열 추가
Set<String> S = new HashSet<>();
for (int i = 0; i < N; i++) {
S.add(br.readLine());
}
// 읽은 문자열이 집합에 포함되어 있으면 +1
int ans = 0;
for (int i = 0; i < M; i++) {
if (S.contains(br.readLine())) ans++;
}
System.out.println(ans);
}
}⏱ 시간 복잡도
입력 : O(N) (HashSet add 시간복잡도 : O(1))
포함 개수 세기 : O(M) (HashSet contains 시간복잡도 : O(1))
-> 시간복잡도 : O(NM)
11286 절댓값 힙
📌문제 링크
https://www.acmicpc.net/problem/11286
💡 문제 풀이
우선순위 큐로 힙을 사용했다.
힙에 {절댓값, 원래 값} 쌍을 넣었고, 이 값을 비교해주기 위해 comparator를 사용했다.
📋코드
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder(10);
PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
// 절댓값 순으로 오름차순 정렬, 절댓값이 같으면 원래 값 순으로 오름차순 정렬
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];
}
});
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int tmp = sc.nextInt();
// 0을 입력받으면 출력
if (tmp == 0) {
if (queue.isEmpty()) sb.append(0).append("\n");
else sb.append(queue.poll()[1]).append("\n");
} else {
queue.offer(new int[] { Math.abs(tmp), tmp });
}
}
System.out.print(sb);
}
}⏱ 시간 복잡도
입력 : O(N)
(PriorityQueue offer 시간복잡도 : O(logN), poll 시간복잡도 O(logN))
-> 시간복잡도 : O(N)
2800 괄호 제거
📌문제 링크
https://www.acmicpc.net/problem/2800
💡 문제 풀이
괄호의 쌍을 HashMap으로 묶고, key값을 대상으로 부분집합을 구했다.
이 때 부분집합이 달라도 결과 식이 똑같이 나오는 경우가 있으므로, 식을 배열에 담고 정렬한 다음 서로 다른 값만 출력했다.
📋코드
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;
public class Main {
static int N;
static String[] str;
static boolean[] isSelected;
static Map<Integer, Integer> pair = new HashMap<Integer, Integer>();
static List<String> ans = new ArrayList<String>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
str = sc.next().split("");
Stack<Integer> stack = new Stack<>();
N = str.length;
isSelected = new boolean[N];
for (int i = 0; i < N; i++) {
// 여는 괄호라면 stack push
if (str[i].equals("(")) stack.push(i);
// 닫는 괄호라면 괄호 값 쌍에 맞춰 hashmap에 넣음
// 올바른 괄호열이 입력으로 주어지므로 괄호 검사 필요없음
else if (str[i].equals(")")) {
pair.put(stack.pop(), i);
} else isSelected[i] = true; // 괄호가 아닐 경우 이미 선택한 것으로 함
}
subset(0, 0); // 부분집합 구하기
Collections.sort(ans); // 결과 식 정렬
StringBuilder sb = new StringBuilder();
// i-1번째와 비교하여 중복을 제거하기 위해 0번째 값 먼저 넣어줌
sb.append(ans.get(0)).append("\n");
// 중복 제거
for (int i = 1, size = ans.size(); i < size; i++) {
if (!ans.get(i).equals(ans.get(i-1)))
sb.append(ans.get(i)).append("\n");
}
System.out.print(sb);
}
// 부분집합 구하기
private static void subset(int cnt, int selected) {
if(cnt == N) {
// 모두 선택했을 때 원래 수식과 같으므로 포함하지 않음
if (selected == pair.size()) return;
StringBuilder sb = new StringBuilder();
// 선택한 것만 append
for (int i = 0; i < N; i++) {
if (isSelected[i]) sb.append(str[i]);
}
ans.add(sb.toString());
return;
}
// 괄호 문자열만 대상으로 부분집합 구함
if (pair.containsKey(cnt)) {
// 괄호 쌍을 맞춰서 제거해야 하므로 hashmap 이용
// 선택하는 경우
isSelected[cnt] = true;
isSelected[pair.get(cnt)] = true;
subset(cnt+1, selected+1);
// 선택하지 않는 경우
isSelected[cnt] = false;
isSelected[pair.get(cnt)] = false;
subset(cnt+1, selected);
} else {
subset(cnt+1, selected);
}
}
}⏱ 시간 복잡도
입력 : O(N)
부분집합 구하기 : O(2^M) (M : 괄호 쌍의 개수)
출력 : O(2^M)
