728x90
이 문제는 '(' 와 ')' 가 연속해서 나올 때는 레이저고, 나머지는 막대로 생각하면 된다.
그러면 입력을 세 가지로 구분할 수 있다.
1. '('가 나오는 경우: 이때는 막대인지 레이저인지 구분할 수 없다.
2. '(' 다음에 바로 ')'가 나오는 경우: 이 경우는 레이저이다.
3. ')' 다음에 ')'가 나오는 경우: 이때는 막대이며, 한 막대가 여기서 끝남을 알려준다.
1의 경우 막대인지 레이저인지 구분할 수 없으니, 일단 bar의 개수에 더한다.
2의 경우는 레이저인게 분명하다. 더해주었던 bar의 개수에서 1을 빼주고, 레이저가 있으면 막대가 두 개로 분열되는 것이니 막대의 수만큼 sum에 더해준다.
3의 경우 막대가 끝났음을 알려주는 것이니 bar에서 1씩 빼준다.
sum은 전체 막대의 개수이다.
1의 경우 일단 막대가 생성되었다고 보고 sum에 1씩 더한다.
2의 경우 막대 중 하나가 레이저이니, 막대 개수에서 1을 빼고, 동시에 sum에서도 1을 빼야 한다. 그리고 남은 bar의 개수만큼 sum에 더하면 된다.
3의 경우는 레이저 없이 그냥 막대가 끝난 것이므로 sum에 영향을 미치지 않는다.
boolean 변수 없이 stack을 활용하여도 풀 수 있지만, 복잡한 알고리즘이 아니라서 이렇게 구현해보았다
package SWEA0811;
import java.util.Scanner;
public class SWEA_5432_쇠막대 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 좌괄호가 계속되면 막대가 지속, (다음에 바로 )가 오면 그건 레이저 -> 개수를 더해줘야함
// 바로앞이 )이 아닌데 )가 나오면 막대가 하나 줄어드는 것
int T = sc.nextInt();
for (int t = 0; t < T; t++) {
String input = sc.next();
boolean prevIsLeft = false;
int sum = 0;
int bar = 0;
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if (c == '(') {
// 좌괄호는 막대 or 레이저
sum += 1;
bar++;
prevIsLeft = true;
} else if (c == ')' && prevIsLeft) {
// 레이저인 경우
sum--;
bar--; // bar의 개수를 하나 감소
// bar가 1개씩 쪼개짐 -> bar의 개수만큼 sum에 추가
sum += bar;
prevIsLeft = false;
} else {
// 막대 하나가 끝남
bar--;
prevIsLeft = false;
}
}
System.out.println("#" + (t + 1) + " " + sum);
}
}
}
728x90
'문제 풀이 > SWEA' 카테고리의 다른 글
[SWEA] 1216 - 회문 2 (자바/Java) (0) | 2022.08.12 |
---|---|
[SWEA] 1210 - Ladder (자바/Java) (0) | 2022.08.11 |
[SWEA] 6190 - 정곤이의 단조 증가하는 수 (자바/Java) (0) | 2022.08.11 |
[SWEA] 1954 - 달팽이 숫자 (자바/Java) (0) | 2022.08.10 |
[SWEA] 1208 - Flattern (자바/Java) 배열, 우선순위 큐(힙) (0) | 2022.08.09 |