사실은 연휴지만 문제는 풀어보자...
백준 1874 스택 수열 java https://www.acmicpc.net/problem/1874
1874번: 스택 수열
1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.
www.acmicpc.net
static void input() throws Exception {
int n = scan.nextInt();
// 스택의 특징을 생각해보면, 4 2 같은 수열은 죽어도 만들 수 없다.
// 1 2 5 3 4의 경우를 예로 들면
// 1 2 는 해결하고 5 까지 push한 경우라면, 이제는 4 3의 순서로 pop 할 수밖에 없다.
// 이미 지나간 수들은 stack에 저장하고있어야 순서를 지키며 뺄 수 있다.
Stack<Integer> s = new Stack<>();
int currentNum = 1;
for(int i = 1 ; i <= n; i++){
// 수열에서 현재 필요한 숫자
int number = scan.nextInt();
// 이 while문에 걸리지 않는다면, 이미 검사를 했던 수
// 따라서 이미 스택에 들어가있는 숫자를 뽑아서 써야한다.
while(currentNum <= number){
s.add(currentNum);
sb.append('+').append('\\n');
currentNum++;
}
if(s.peek()== number){
s.pop();
sb.append('-').append('\\n');
}
else{
System.out.println("NO");
return;
}
}
print();
}
백준 1021 회전하는 큐 java https://www.acmicpc.net/problem/1021
1021번: 회전하는 큐
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가
www.acmicpc.net
처음 아이디어를 deque 자료구조로 잘못 잡아서 고생했다.
처음의 아이디어는
1 2 3 4 5에서 2를 찾기 위해서
왼쪽 이동을 하면 1회만에 2를 맨 앞에 위치시킬 수 있고,
오른쪽 이동을 하면 4회만에 2를 맨앞에 위치시킬 수 있으니까.
1. deque를 앞에서부터 빼서 뒤로 넣는 연산을 큐의 길이(5개)만큼 하면서 언제 2가 가장 맨앞에 위치했는지 기록,
2. deque를 뒤에서부터 빼서 앞으로 넣는 연산을 큐의 길이(5개)만큼 하면서 언제 2가 가장 맨앞에 위치했느지 기록,
해서 앞에서부터 뺐을 때가 더 연산 횟수가 적었으므로, 1회의 연산 앞에서 빼기 연산을 수행하고 2를 pop한다.
의 반복을 하면 문제를 풀 수 있단 생각이 들었는데, 만약 문제에서 큐의 길이가 훨씬 길었다면(문제에서는 50개 제한이지만) 연산량이 너무 많아 비효율적인 풀이라는 생각이 들어서 고민하다가,
큐의 길이를 len
어떤 숫자 k를 찾기 위해 큐를 왼쪽 이동하는 연산의 횟수를 l, 큐를 오른쪽 이동하는 연산의 횟수를 r이라고 하면,
len = l+r 이라는 사실과,
왼쪽 이동해서 찾든 오른쪽 이동해서 찾든 큐의 상태는 똑같다는 사실을 깨닫고, 풀이를 수정했다.
큐의 앞에서 빼서 뒤로 넣는 연산을 반복하며 숫자 k를 찾고, 연산횟수는 l,
만약 뒤에서 빼서 앞으로 넣으며 찾았다면 수행했을 연산의 횟수를 r = len - l 과 같이 구할 수 있다.
l과 r 중 작은 값의 연산을 수행했다고 치고, 숫자 k를 pop하고 계속 진행할 수 있다.
static void input() throws Exception {
// 10개짜리 큐에서
// 2 9 5
// 초기 1 2 3 4 5 6 7 8 9 10
// 왼쪽이동 1회 + 2 뽑기
// 3 4 5 6 7 8 9 10 1
// 오른쪽 이동 3회 + 9 뽑기
// 10 1 3 4 5 6 7 8
Queue<Integer> q = new LinkedList<>();
int n = scan.nextInt();
for(int i = 1 ; i <= n ; i++)
q.add(i);
int k = scan.nextInt();
int sumOfOperation = 0;
for(int z = 0 ; z<k; z++){
int num = scan.nextInt();
int operationCount = 0;
while(q.peek() != num){
int temp = q.poll();
q.add(temp);
operationCount++;
}
// 큐의 길이가 12개, 원하는 원소가 앞에서 5번째에 있다면,
// 왼쪽 이동 연산 4번 혹은 오른쪽 이동 연산 8번으로
// 원하는 원소가 가장 앞에 있도록 할 수 있으며,
// 왼쪽 이동을 하나 오른쪽 이동을 하나 숫자의 배치는 달라지지않는다.
int minOperation = Math.min(operationCount, n - operationCount);
sumOfOperation += minOperation;
q.poll();
n--;
}
System.out.println(sumOfOperation);
}
백준 9012 괄호 https://www.acmicpc.net/problem/9012
9012번: 괄호
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고
www.acmicpc.net
단순하게 스택을 이용하여 풀었는데, 여담으로 스택에 들어가는건 여는 괄호 하나뿐이고,
닫히지 않은 여는 괄호가 몇개가 이미 몇개나 등장하였는지중요하므로 꼭 스택으로 구현해야하지는 않아도 된다는 것을 다 풀고 깨달았다.
아래는 그냥 스택을 이용한 구현
static void input() throws Exception {
// 규칙 1. 여는 괄호가 먼저 나와야함
// 규칙 2. 닫는 괄호가 여는 괄호보다 많은 순간이 있으면 안된다.
Stack<Character> s = new Stack<>();
int caseNum = scan.nextInt();
for(int z=0 ; z < caseNum ; z++){
s.clear();
String parenthesis = scan.nextLine();
boolean flag = true;
for(int i = 0 ; i < parenthesis.length(); i++){
if(parenthesis.charAt(i) == '('){
s.push('(');
}
else{
if(s.isEmpty()){
flag = false;
break;
}
s.pop();
}
}
// flag == false이면, 여는괄호보다 닫는 괄호가 많은 순간이 있었음
// stack이 비어있지 않으면, 여는괄호가 더 많음
sb.append(flag && s.isEmpty() ? "YES" : "NO").append('\\n');
}
print();
}
스택을 사용하지 않은 풀이는 아래와 같은 풀이를 생각해볼 수 있겠다.
int remainOpenCount = 0 ; // 현재 닫히지 않은 여는 괄호 수
for(int i = 0 ; i < parenthesis.length(); i++){
if(parenthesis.charAt(i) == '('){
remainOpenCount++; // 닫힞 ㅣ않은 여는 괄호 수 증가
}
else{
if(remainOpenCount == 0){ // 닫히지 않은 여는 괄호가 더이상 없다면 닫힌괄호가 나오면 안돼
flag = false;
break;
}
remainOpenCount--; // 여는 괄호 한개 감소
}
}
