C# 백준 - 9012번 괄호, 4949번 균형잡힌 세상, 12789번 도키도키 간식드리, 18258번 큐 2, 11866번 요세푸스 문제 O
코딩테스트 : 9012번 괄호
| 1 초 | 128 MB | 236589 | 113196 | 81000 | 46.536% |
문제
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.
여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.
출력
출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야
using System;
using System.Runtime.CompilerServices;
using System.Text;
public class Solution
{
private static void Main()
{
int n = int.Parse(Console.ReadLine()!);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++)
{
Stack<char> stack = new Stack<char>();
string s = Console.ReadLine();
for (int j = 0; j < s.Length; j++)
{
if (s[j] == '(')
{
stack.Push(s[j]);
}
if (s[j] == ')')
{
if (stack.Count == 0)
{
sb.AppendLine("NO");
break;
}
char temp = stack.Pop();
if (temp != '(')
{
sb.AppendLine("NO");
break;
}
}
if (j == s.Length - 1)
{
if (stack.Count == 0)
{
sb.AppendLine("YES");
}
else
{
sb.AppendLine("NO");
}
}
}
}
Console.WriteLine(sb.ToString());
}
}stack을 밖에 선언해서 한 번, Yes를 대문자로 안 써서 한 번 틀렸다. 다들 조심하세요
다른 사람의 흥미로운 풀이
나처럼 무식하게 모든 경우의 수를 다 검사하지 않고, 또 문자를 push하지 않고 그냥 1을 push하고 팝하시는 분도 계셨다.
더해서 나는 )가 나왔을 경우 그 전의 문자가 )인지 아닌지를 검사했는데 이보다는 그냥 pop을 해 봐서 안되면 break해버릴 수 도 있다. (어제 배웠던 if(!stack.Trypop(out int b) 이런 식으로 사용)
코딩테스트 : 4949번 균형잡힌 세상
| 1 초 | 128 MB | 160431 | 54943 | 42320 | 32.936% |
문제
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
- 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
- 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
- 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
- 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
- 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.
using System;
using System.Runtime.CompilerServices;
using System.Text;
public class Solution
{
private static void Main()
{
StringBuilder sb = new StringBuilder();
bool stop = false;
while (!stop)
{
string s = Console.ReadLine();
Stack<int> stack = new Stack<int>();
for (int i = 0; i < s.Length; i++)
{
if (s[i] == '.')
{
if (i == 0)
{
stop = true;
break;
}
if (stack.Count == 0)
{
sb.AppendLine("yes");
}
else
{
sb.AppendLine("no");
}
break;
}
if (s[i] == '(') stack.Push(1);
else if (s[i] == '[') stack.Push(2);
if (s[i] == ')')
{
if (stack.Count == 0)
{
sb.AppendLine("no");
break;
}
int temp = stack.Pop();
if (temp != 1)
{
sb.AppendLine("no");
break;
}
}
else if (s[i] == ']')
{if (stack.Count == 0)
{
sb.AppendLine("no");
break;
}
int temp = stack.Pop();
if (temp != 2)
{
sb.AppendLine("no");
break;
}
}
}
}
Console.WriteLine(sb);
}
}
예외처리를 안해서 한 번 틀렸다.
TryPop을 써 보고 싶었는데 못써서 다른 분들의 코드를 관찰했다.
다른 사람의 흥미로운 풀이
Stack<char> stack = new();
foreach (char c in str)
{
if (c == '(' || c == '[') stack.Push(c);
else if (c == ')' && (!stack.TryPop(out char p) || p != '(')) return false;
else if (c == ']' && (!stack.TryPop(out char b) || b != '[')) return false;
}이런 식으로 깔끔하게 검사하고
sw.WriteLine(IsBalanced(str) ? "yes" : "no");이렇게 검사하면 된다. 코드 줄 수가 거의 절반으로 줄어든다.
TryPop(out T Result)는 T를 반환하고 Pop을 할 수 없을 경우 false를 반환하는 메서드다.
코딩테스트 : 12789번 도키도키 간식드리
| 1 초 | 128 MB | 37638 | 12952 | 10861 | 34.021% |
문제
인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다.
그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다.
사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라.
현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.
위 예제는 다음 그림과 같이 움직였을 때 모두가 순서대로 간식을 받을 수 있다..
입력
입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.
다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다.
출력
승환이가 무사히 간식을 받을 수 있으면 "Nice"(따옴표는 제외)를 출력하고 그렇지 않다면 "Sad"(따옴표는 제외)를 출력한다.
using System;
using System.Runtime.CompilerServices;
using System.Text;
public class Solution
{
private static void Main()
{
int n = int.Parse(Console.ReadLine());
int[] numbers = new int[n];
numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
Stack<int> Waiting = new();
int orderNumber = 1;
for (int i = 0; i < n; i++)
{
if (numbers[i] == orderNumber)
{
orderNumber++;
}
else
{
Waiting.Push(numbers[i]);
}
}
while (Waiting.Count > 0)
{
Waiting.TryPop(out int number);
if (number == orderNumber)
{
orderNumber++;
}
else
{
Console.WriteLine("Sad");
return;
}
}
Console.WriteLine("Nice");
}
}중간에 Stack 그러니까 Waiting에서 꺼내는걸 고려하지 않았다.
using System;
using System.Runtime.CompilerServices;
using System.Text;
public class Solution
{
private static void Main()
{
int n = int.Parse(Console.ReadLine());
int[] numbers = new int[n];
numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
Stack<int> Waiting = new();
int orderNumber = 1;
for (int i = 0; i < n; i++)
{
if (numbers[i] == orderNumber)
{
orderNumber++;
}
else if (Waiting.TryPeek(out int value))
{
if (value == orderNumber)
{
Waiting.Pop();
orderNumber++;
}
}
else
{
Waiting.Push(numbers[i]);
}
}
while (Waiting.Count > 0)
{
Waiting.TryPop(out int number);
if (number == orderNumber)
{
orderNumber++;
}
else
{
Console.WriteLine("Sad");
return;
}
}
Console.WriteLine("Nice");
}
}
왜 안되는걸까... 고민하다가 중간에 Waiting에서 하나씩 뺐을 때 또 검사해야 한다는 것
그러니까 중간에 Waiting에 올바른 순서대로 있으면 그 순서 전부를 빼야 한다는 것을 간과했다는 사실을 알았다.
using System;
using System.Runtime.CompilerServices;
using System.Text;
public class Solution
{
private static void Main()
{
int n = int.Parse(Console.ReadLine());
int[] numbers = new int[n];
numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
Stack<int> Waiting = new();
int orderNumber = 1;
for (int i = 0; i < n; i++)
{
while (Waiting.Count > 0 && Waiting.TryPeek(out int value))
{
if (value == orderNumber)
{
Waiting.Pop();
orderNumber++;
}
else break;
}
if (numbers[i] == orderNumber)
{
orderNumber++;
}
else
{
Waiting.Push(numbers[i]);
}
}
while (Waiting.Count > 0)
{
Waiting.TryPop(out int number);
if (number == orderNumber)
{
orderNumber++;
}
else
{
Console.WriteLine("Sad");
return;
}
}
Console.WriteLine("Nice");
}
}
조건 바꿔서 성공 !
다른 사람의 흥미로운 풀이
똑같은 논리지만 코드를 굉장히 짧게 바꿀 수 있다.
예를 들어 While문의 코드를
while (alley.Any() && alley.Peek() == waiting) {
waiting++;
alley.Pop();
}이런 식으로 바꾸고
마지막 검사를
Console.WriteLine(alley.Any() ? "Sad" : "Nice");다음과 같이 남아 있으면 Sad, 하나도 없으면 Nice를 출력하면 된다.
이 부분 뿐만 아니라 조건 검사도 굉장히 짧게 바꿀 수 있다.
코딩테스트 : 18258번 큐 2
| 1 초 (하단 참고) | 512 MB | 117169 | 38528 | 31141 | 32.959% |
문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
using System;
using System.Runtime.CompilerServices;
using System.Text;
public class Solution
{
private static void Main()
{
Queue<int> numbers = new Queue<int>();
int n = int.Parse(Console.ReadLine());
StringBuilder sb = new StringBuilder();
int last = 0;
for (int i = 0; i < n; i++)
{
String[] s = Console.ReadLine().Split(' ').ToArray();
string str = s[0];
if (str == "push")
{
int number = Convert.ToInt32(s[1]);
numbers.Enqueue(number);
last = number;
}
else if (str == "pop")
{
if (numbers.Count > 0)
{
int temp = numbers.Dequeue();
sb.AppendLine(temp.ToString());
if (numbers.Count == 0) last = 0;
}
else
{
sb.AppendLine("-1");
}
}
else if (str == "size")
{
sb.AppendLine(numbers.Count.ToString());
}
else if (str == "empty")
{
if (numbers.Count > 0) sb.AppendLine("0");
else sb.AppendLine("1");
}
else if (str == "front")
{
if (numbers.TryPeek(out int number))
{
sb.AppendLine(number.ToString());
}
else
{
sb.AppendLine("-1");
}
}
else if (str == "back")
{
if (last == 0) sb.AppendLine("-1");
else sb.AppendLine(last.ToString());
}
}
Console.WriteLine(sb.ToString());
}
}
좀 길긴 한데... ㅎ... 아무튼 빠르게 성공 !
다른 사람의 흥미로운 풀이
물론 훨씬 짧게 쓰신 분들이 당연히 계신다.
예를 들어 sw.WriteLine(queue.TryDequeue(out var result) == false ? -1 : result); 이런 식으로 !
코딩테스트 : 2164번 카드2
| 2 초 (추가 시간 없음) | 128 MB | 145076 | 75570 | 58639 | 50.934% |
문제
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.
출력
첫째 줄에 남게 되는 카드의 번호를 출력한다.
public class Solution
{
private static void Main()
{
int n = int.Parse(Console.ReadLine());
Queue<int> cards= new Queue<int>();
for (int i = 1; i <= n; i++)
{
cards.Enqueue(i);
}
for (int i = 0; i < n-1; i++)
{
cards.Dequeue();
int temp = cards.Dequeue();
cards.Enqueue(temp);
}
Console.WriteLine(cards.Dequeue().ToString());
}
}다른 사람의 흥미로운 풀이
그냥
queue.Dequeue();
queue.Enqueue(queue.Dequeue());temp를 쓰지 않고 이렇게 해도 되었다.
코딩테스트 : 11866번 요세푸스 문제 O
| 2 초 | 512 MB | 92841 | 53042 | 44451 | 56.714% |
문제
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
public class Solution
{
private static void Main()
{
int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
int N = input[0];
int K = input[1];
Queue<int> queue = new Queue<int>();
for (int i = 1; i <= N; i++)
{
queue.Enqueue(i);
}
StringBuilder sb = new StringBuilder();
sb.Append("<");
while (queue.Count>0)
{
for (int i = 0; i < K-1; i++)
{
queue.Enqueue(queue.Dequeue());
}
if (queue.Count != 1)
{
sb.Append(queue.Dequeue().ToString() + ", ");
}
else sb.Append(queue.Dequeue().ToString());
}
sb.Append(">");
Console.WriteLine(sb.ToString());
}
}다른 사람의 흥미로운 풀이
다른 분들 쓰신거 보면 내가 너무 더럽게 쓰나... 라는 생각이 든다.
첫 index 를 -1하고
idx = (idx + jump) % nums.Count;
josephus.Add(nums[idx]);
nums.RemoveAt(idx);
idx--;이런 식으로..하신 분도 있으시다.
굳이 큐를 쓸 필요가 없었던 ..!
하지만 연습 삼아 했다고 하자.
결국 알맞은 자료구조를 선택하는 것도 실력이니 최대한 자료구조들을 다 체험해보고 선택해서 사용하자.