하루 한 접시 (60)
2024-08-28 01:44:57

 

문제의 조건 자체는 엄청 쉬워보였다.

일반적인 bfs문제에 그저 블록 파괴 기능만 추가하면 의외로 쉽게 풀릴 줄 알았다... 그 때는...

접근 1)  더이상 순회 불가능 시 벽 파괴해보기

우선 그래프를 순회하며 만난 벽들을 모두 리스트에 담아 기록해둔다.

이후 큐의 모든 원소를 소모하였을 때, 도착점에 도달하지 못했다면, 리스트에서 벽을 하나씩 꺼내어 해당 벽을 부수고, 다시 순회를 해 주었다.

문제 1)  너무 비효율적인 순회

접근법 자체는 빠르게 떠올렸지만, 그리 좋은 접근법은 아니었다. 입력대로 초기화 될때의 상태를 간직하는 원본 그래프를 준비하고, 순회 시 마다 복사본 그래프를 만들어 순회를 해주었는데, 이건 메모리 측면에서나, 실행시간 측면에서나 너무 비효율적이었다.

문제 2)  한번에 순회를 완료했을때 문제.

이게 가장 큰 문제였다. 예제들은 모두 한번에 순회가 불가능했기  때문에 벽을 한번 부수고 순회하는 것이 최단거리였다.

하지만  https://www.acmicpc.net/board/view/147795  이 예제대로 막힌 벽 없이 한번에 순회가 완료되면 바로 메소드가 종료되어 올바른 답을 얻을 수 없었다.

때문에 다른 접근법을 찾아보기로 했다.

보완 1)  사용하는 그래프를 2개로 제한해보기

기존에 순회할 때 마다 무한정 늘어나는 그래프의 수를 제한하고자, 벽을 부수지 않는 경우, 벽을 부수는 경우 둘로 나누어 두 그래프만 사용해보기로 했다.

두 그래프를 유기적으로 묶어, 일반 그래프가 벽을 만나면, 벽을 부수는 그래프의 값을 증가시키고, 다시 벽을 부수는 그래프가 일반 그래프에 영향을 주어 순회를 하는 방식으로 해보았다.

또한 계속해서 벽을 뚫는것을 방지하기 위해, 벽이 벽을 만나면 순회하지않고, 건너뛰기로 했다.

해당 알고리즘을 그힘으로 표현

문제 3)  벽을 한번 이상 부셔버림

알고리즘 특성상 연속된 벽은 통과 못하지만, 띄엄띄엄 존재하는 벽이라면 무한정으로 뚫고 지나가버리는 치명적인 문제점이 있었다. 따라서 벽을 몇번 뚫었는지 저장해두어야 한다는걸 깨닳았다.

문제 4) 벽을 부순건지 아닌지의 모호함

첫번째 칸이 0으로 되어있기 때문에, 첫번째 칸이 벽을 만나 벽을 부수게 되었을 때, 값이 1로 되어 벽을 부순 것인지, 벽을 부수지 않은 것인지 판별을 할 수 없는 문제가 있었다.

보완 2)  그래프를 하나로, 방문처리를 set이 아닌 배열로

그래프의 값을 변조하는 방식이 그다지 효과적이지 않다는 것을 깨달았다. 대신에, 기존에 방문처리를 해주던 HashSet 대신 bool 배열을 이용하여 해당 칸을 방문처리를 대신해 주었다. 이럼으로써 4번 문제가 깔끔히 해결되었다.

보완 3) 모든 정보를 저장해두자

지난번에 풀었던 사다리 게임 문제에서 클래스를 만들어 좌표값 , 이동한 거리, 이동할 좌표값을 저장해두었던 것에서 아이디어를 얻었다. 이번엔 튜플을 이용하여 좌표값, 벽을 부신 횟수, 이동한 거리를 저장하기로 하였다.

이 정보들을 바탕으로, 이동가능 여부, 벽 파괴 가능 여부를 판단할 수 있게 되었다.

코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
using System;
using System.Collections.Generic;
using System.Text;
 
namespace real연습
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader reader = new StreamReader(Console.OpenStandardInput());
            int[] arr = Array.ConvertAll(reader.ReadLine().Trim().Split(), int.Parse);
            Graph g = new Graph(arr[0], arr[1]);
            for (int i = 0; i < arr[0]; i++)
            {
                string str = reader.ReadLine();
                foreach (var a in str)
                {
                    g.graph[i].Add(a - '0');
                }
            }
            Console.WriteLine(g.bfs());
        }
    }
    class Graph
    {
        int width;
        int height;
        public List<List<int>> graph;
        public Graph(int h, int w)
        {
            this.height = h;
            this.width = w;
            graph = new List<List<int>>();
            for (int i = 0; i < height; i++)
            {
                graph.Add(new List<int>());
            }
        }
        public int bfs()
        {
            int[] deltaY = { 10-10 };
            int[] deltaX = { 010-1 };
 
            bool[,,] visited = new bool[height, width,2];
            Queue<Tuple<intintintint>> qu = new Queue<Tuple<intintintint>>();
            qu.Enqueue(new Tuple<intintintint>(0001));
            // y, x, 벽 부순 횟수, 거리
            visited[000= true;
            while(qu.Count!= 0)
            {
                Tuple<intintintint> current = qu.Dequeue();
                if (current.Item1 == height - 1 && current.Item2 == width - 1)
                {
                    return current.Item4;
                }
                for (int i = 0; i < deltaX.Length; i++)
                {
                    int movedY = current.Item1 + deltaY[i];
                    int movedX = current.Item2 + deltaX[i];
                    if (movedY < 0 || movedY >= height || movedX < 0 || movedX >= width)
                    {
                        continue;
                    }
                    if (visited[movedY, movedX, current.Item3] == true)
                    {
                        continue;
                    }
                    if (graph[movedY][movedX] == 0)
                    {
                        qu.Enqueue(new Tuple<intintintint>(movedY, movedX, current.Item3, current.Item4 + 1));
                        visited[movedY, movedX, current.Item3] = true;
                    }
                    else if (current.Item3 == 0 && graph[movedY][movedX] == 1)
                    {
                        qu.Enqueue(new Tuple<intintintint>(movedY, movedX, current.Item3 + 1, current.Item4 + 1));
                        visited[movedY, movedX, current.Item3 + 1= true;
 
                    }
                }
            }
 
            return -1;
        }
 
    }
}
 
cs

 

2024-06-27 00:41:58

 

dfs던 bfs던 아무 그래프 순회 알고리즘을 사용하여 1번 정점으로부터 방문 가능한 모든 정점의 개수를 요구하는 문제이다.

주의해야 할 점은 '1번 컴퓨터' 로 부터 감염될 수 있는 컴퓨터의 수를 구하는 문제이기 때문에, 1번 정점은 빼주고 개수를 구해주어야 한다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
using System.Collections.Generic;
 
namespace real연습
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int edges = int.Parse(Console.ReadLine());
            int linkes = int.Parse(Console.ReadLine());
            Graph graph = new Graph(edges);
 
            for (int i = 0; i < linkes; i++)
            {
                int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                graph.graph[input[0]].Add(input[1]);
                graph.graph[input[1]].Add(input[0]);
            }
            int result = 0;
            result = dfs_search(graph);
            Console.WriteLine(result);
        }
        static int dfs_search(Graph graph)
        {
            int result = 0;
 
            Stack<int> stack = new Stack<int>();
            stack.Push(1);
            List<int> visited = new List<int>();
            
            while (stack.Count != 0)
            {
                int current = stack.Pop();
 
                if (visited.Contains(current) == false)
                {
                    if (current != 1)
                    {
                        result++;
                    }
                    visited.Add(current);
                }
                for (int i = graph.graph[current].Count - 1; i >= 0; i--)
                {
                    if (visited.Contains(graph.graph[current][i]) == false)
                    {
                        stack.Push(graph.graph[current][i]);
                    }
                }
            }
 
            return result;
        }
        private class Graph
        {
            int _size;
            public List<int>[] graph;
            public Graph(int size)
            {
                this._size = size;
                this.graph = new List<int>[_size + 1];
                for (int i = 1; i <= _size; i++)
                {
                    graph[i] = new List<int>();
                }
            }
        }
    }
}
 
cs

 

2024-06-27 00:07:45

이런식으로 서로 간선으로 연결되어있는 정점들의 집합을 하나의 연결 요소라고 한다.

이 주어진 그래프를 토대로 몇개의 연결 요소가 나오는지 구하는 문제이다.

 

문제에서 주어지는 정점의 개수는 1000개이다. 이를 일반적인 인접행렬로 표현하려면 1000 * 1000의 배열이 필요하므로, 메모리도 아끼고 실행 시간도 줄일 겸 각 정점이 어느 정점과 연결되어있는지 표현하는 인접행렬로 구현하였다.

 

문제를 풀기 위해서 dfs를 사용하여 순회하지 않았던 연결 요소라면 true를 반환하여 결과값에 1을 더하고, 순회하였던 연결 요소라면 false를 반환하도록 해주었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
namespace real연습
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int edge = input[0];
            int linkes = input[1];
 
            Graph graph = new Graph(edge);
 
            for (int i = 0; i < linkes; i++)
            {
                int[] link = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                graph.graph[link[0]].Add(link[1]);
                graph.graph[link[1]].Add(link[0]);
            }
            HashSet<int> visited = new HashSet<int>();
 
            int result = 0;
            for (int i = 1; i <= edge; i++) // 1번 정점부터 순회 시작
            {
                if (dfs_search(i, visited, graph) == true) // 순회한적 없다면
                {
                    result += 1; // 결과값 1 증가
                }
            }
            Console.WriteLine(result);
 
        }
        static bool dfs_search(int start, HashSet<int> visited, Graph graph)
        {
            bool result = false;
            Stack<int> stack = new Stack<int>();
            if (visited.Contains(start) == false) // 방문하지 않았던 정점일때만 실행
            {
               stack.Push(start); // stack에 순회를 시작하는 값을 미리 넣어둠
 
                while (stack.Count != 0)
                {
                    int current = stack.Pop(); // 스택의 맨 뒤에있는 값을 뽑아 사용
                    if (visited.Contains(current) == false) // 해당 정점을 방문하지 않았다면
                    {
                       visited.Add(current); // 방문처리
                    }
                    for (int vertex = graph.graph[current].Count - 1; vertex >= 0 ; vertex--)
                   { // 스택을 맨 위의 값부터 뽑아서 쓰기 때문에, 마지막 index부터 첫번쨰 index까지 역순회
                        if (visited.Contains(graph.graph[current][vertex]) == false)
                       {
                            stack.Push(graph.graph[current][vertex]);
                        }
                    }
 
                }
                result = true;
            }
 
 
            return result;
        }
        private class Graph=
        {
            int _size;
            public List<int>[] graph;
            public Graph(int size)
            {
                this._size = size;
                this.graph = new List<int>[size + 1];
                for (int i = 1; i < size + 1; i++)
                {
                    graph[i] = new List<int>();
                }
            }
        }
 
    }
    
}
 
cs

 

 

2024-05-23 23:28:52

 

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _2504_boj boj = new _2504_boj();
 
            boj.boj_2504();
 
        }
    }
    internal class _2504_boj
    {
        public void boj_2504()
        {
            string input = Console.ReadLine();
            int result = 0;
            int temp = 1;
            Stack<char> stack = new Stack<char>();
 
            for (int i = 0; i < input.Length; i++)
            {
                if (input[i] == '[' || input[i] == '(')
                {
                    temp *= input[i] == '[' ? 3 : 2;
                    stack.Push(input[i]);
                    continue;
                }
                if (input[i] == ']')
                {
                    if (stack.Count > 0 && stack.Peek() == '[')
                    {
                        if (i > 0 && input[i - 1== '[')
                        {
                            result += temp;
                            temp /= 3;
                            stack.Pop();
                        }
                        else
                        {
                            temp /= 3;
                            stack.Pop();
                        }
                    }
                    else
                    {
                        result = 0;
                        break;
                    }
                }
                if (input[i] == ')')
                {
                    if (stack.Count > 0 && stack.Peek() == '(')
                    {
                        if (i > 0 && input[i - 1== '(')
                        {
                            result += temp;
                            temp /= 2;
                            stack.Pop();
                        }
                        else
                        {
                            temp /= 2;
                            stack.Pop();
                        }
                    }
                    else
                    {
                        result = 0;
                        break;
                    }
                }
            }
            Console.WriteLine(stack.Count > 0 ? 0 : result);
        }
    }
}
 
 
cs

 

 

2024-05-22 23:51:52

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _17298_boj boj = new _17298_boj();
 
            boj.boj_17298();
 
        }
    }
    internal class _17298_boj
    {
        public void boj_17298()
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            StringBuilder sb = new StringBuilder();
            int n = int.Parse(reader.ReadLine());
            int[] input = Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
 
            int[] result = new int[n];
 
            Stack<int> stack = new Stack<int>();
 
            for (int i = n - 1; i >= 0; i--)
            {
                while (stack.Count > 0 && input[i] >= stack.Peek())
                {
                    stack.Pop();
                }
                if (stack.Count == 0)
                    result[i] = -1;
                else
                    result[i] = stack.Peek();
                stack.Push(input[i]);
            }
            foreach (var _ in result)
                sb.Append(_ + " ");
 
            if (sb[sb.Length - 1== ' ')
                sb.Remove(sb.Length - 11);
            Console.Write(sb);
        }
    }
}
 
 
cs

 

이번에는 너무 귀찮아서 스택을 직접 구현하지 않았다.

스택 관련해서 푼 문제중 의외로 제일 쉬웠다.

아파트 문제를 탑 문제처럼 풀었더니 아주 쉽게 풀 수 있었다.

다만 입력이 너무 많았던 것을 고려하지 못하여 시간초과가 났는데,

StreamReader와 StringBuilder를 사용하니 바로 해결되었다.

 

2024-05-22 22:12:01

며칠전 올린 탑 문제와 비슷한 문제이다.

탑 문제는 가장 가까운 신호를 수신하는 탑의 번호를 출력하는 거라면

이번 문제는 한 탑보다 큰 탑이 올때 까지의 모든 탑(아파트) 의 개수를 구해서 더하여 출력하는 문제이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _6198_boj boj = new _6198_boj();
 
            boj.boj_6198();
 
        }
    }
        internal class _6198_boj
    {
        public void boj_6198()
        {
            int n = int.Parse(Console.ReadLine());
            Stack stack = new Stack(n);
 
            string[] input = new string[n];
            for (int i = 0; i < n; i++)
                input[i] = Console.ReadLine();
 
            long result = 0;
 
            for (int i = 0; i < n; i ++)
            {
                while (stack.top >= 0 && int.Parse(input[int.Parse(stack.Peek())]) <= int.Parse(input[i]))
                {
                    stack.Pop();
                }
 
                result += stack.size;
                stack.Push(i.ToString());
 
            }
            Console.WriteLine(result);
        }
    }
    public class Stack
    {
        public string[] stack;
        public int top = -1;
        public int size = 0;
        public Stack(int n)
        {
            stack = new string[n];
        }
        public void Push(string data)
        {
            if (top != stack.Length - 1)
            {
                top += 1;
                stack[top] = data;
                size++;
            }
        }
        public string Pop()
        {
            string result = null;
            if (top != -1)
            {
                result = stack[top];
                stack[top--= null;
                size--;
            }
 
            return result;
        }
        public string Peek()
        {
            string result = null;
            if (top != -1)
                result = stack[top];
 
            return result;
        }
    }
}
 
 
cs

 

입력받은 배열의 0번지부터 n - 1번지까지 돌아가며 스택의 맨 위값과 비교하여 같거나 작다면 자신보다 작은 값이 나올때까지 계속 pop해주었다.

pop을 모두 수행 한 이후 (stack이 모두 비게됨 / stack의 맨 위값이 현재 배열의 값보다 큼)

남은 스택의 원소 만큼 결과값에 넣어 주었다. (여기서는 stack.size로 따로 변수를 만들어 주었으나, stack.top + 1을 사용하면 좋을 듯 하다.)

(이 과정은 현재 아파트의 옥상을 볼 수 있는 아파트의 수를 구하는 과정이다.)

마지막으로 현재 아파트의 높이를 가리키는 주소를 스택에 넣어주고 다음 회차로 진행해 주었다.

또한 주어지는 결과값이 매우 크기때문에 (단적인 예로 799,999 + 799,998 + 799,997 .... + 1) 결과를 저장할 변수를 int형으로 하면 오버플로우로 인한 오류가 난다.

그렇기 때문에 long형을 사용해야 한다.

'하루 한 접시' 카테고리의 다른 글

[백준] 2504번 : 괄호의 값 [C#]  (0) 2024.05.23
[백준] 17298번 : 오큰수 [C#]  (0) 2024.05.22
[백준] 10799번 : 쇠막대기 [C#]  (0) 2024.05.21
[백준] 10845번 : 큐 [C#]  (0) 2024.05.21
[백준] 28279번: 덱 2 [C#]  (0) 2024.05.20
2024-05-21 01:09:29

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _10799_boj boj = new _10799_boj();
 
            boj.boj_10799();
 
        }
    }
        internal class _10799_boj
    {
        public void boj_10799()
        {
            string sticks = Console.ReadLine();
            Stack stack = new Stack();
            
            stack.stack = new string[sticks.Length];
 
            int result = 0;
 
            for (int i = 0; i < sticks.Length; i++)
            {
                if (sticks[i] == '(')
                {
                    stack.Push("(");
                    continue;
                }
                if (sticks[i] == ')' && i >= 1)
                {
                    if (sticks[i - 1== '(')
                    {
                        stack.Pop();
                        result += stack.size;
                        continue;
                    }
                    else
                    {
                        stack.Pop();
                        result++;
                        continue;
                    }
                }
            }
            Console.WriteLine(result);
        }
    }
    public class Stack
    {
        public int size;
        public string[] stack;
        public int top = -1;
        public void Push(string data)
        {
            if (IsStackFull())
                return;
            stack[++top] = data;
            size++;
        }
        public string Pop()
        {
            string res = null;
            if (IsStackEmpty())
                return res;
            res = stack[top--];
            size--;
            return res;
        }
        public bool IsStackFull()
        {
            bool res = false;
            if (top == stack.Length - 1)
                res = true;
            return res;
        }
        public bool IsStackEmpty()
        {
            bool res = false;
            if (top == -1)
                res = true;
            return res;
        }
 
    }
}
 
 
cs

 

입력받은 문자열을 하나씩 되짚어가며

여는 괄호 " ( " 를 만나면 일단 스택에 저장한다.

이후 닫는 괄호 " ) " 를 만나게 되면       (0번 인덱스에 오는 닫는 괄호는 의미 없으니 거르는 코드를 추가해 주었다)

바로 직전 괄호가 여는 괄호인 경우 : 스택에서 해당 괄호를 제거 해 주고 스택에 남은 여는 괄호만큼 결과값에 추가

직전 괄호가 여는 괄호가 아닐 경우 : 스택에서 가장 앞에 있는 여는 괄호를 제거해주고, 결과값에 1 추가

이런식으로 진행해 주었더니 한번에 정답을 얻을 수 있었다

 

 

'하루 한 접시' 카테고리의 다른 글

[백준] 17298번 : 오큰수 [C#]  (0) 2024.05.22
[백준] 6198번 : 옥상 정원 꾸미기 [C#]  (0) 2024.05.22
[백준] 10845번 : 큐 [C#]  (0) 2024.05.21
[백준] 28279번: 덱 2 [C#]  (0) 2024.05.20
[백준] 2493번 : 탑 [C#]  (0) 2024.05.20
2024-05-21 00:21:16

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _10845_boj boj = new _10845_boj();
 
            boj.boj_10845();
 
        }
    }
        internal class _10845_boj
    {
        public void boj_10845()
        {
            StringBuilder sb = new StringBuilder();
            Queue queue = new Queue();
            queue.n = int.Parse(Console.ReadLine());
            queue.queue = new string[queue.n];
 
            for (int i = 0; i < queue.n; i++)
            {
                string[] input = Console.ReadLine().Split();
                switch(input[0])
                {
                    case "push":
                        queue.Push(input[1]);
                        break;
                    case "pop":
                        sb.Append(queue.Pop() + "\n");
                        break;
                    case "size":
                        sb.Append(queue.size + "\n");
                        break;
                    case "empty":
                        sb.Append(queue.IsQueueEmpty() ? "1\n" : "0\n");
                        break;
                    case "front":
                        
                        sb.Append(queue.Front() + "\n");
                        break;
                    case "back":
                        sb.Append(queue.Back() + "\n");
                        break;
                }
            }
            if (sb.Length >= 1 && sb[sb.Length - 1== '\n')
                sb.Remove(sb.Length - 11);
            Console.WriteLine(sb);
        }
    }
    public class Queue
    {
        public int n;
        public int front = -1;
        public int rear = -1;
        public string[] queue;
        public int size = 0;
        public void Push(string data)
        {
            if (IsQueueFull())
                return;
            rear++;
            queue[rear] = data;
            size++;
        }
        public string Pop()
        {
            string res = "-1";
            if (IsQueueEmpty())
                return res;
            front++;
            res = queue[front];
            queue[front] = null;
            size--;
            return res;
        }
        public bool IsQueueEmpty()
        {
            bool res = false;
            if (rear == front)
                res = true;
            return res;
        }
        public bool IsQueueFull()
        {
            bool res = false;
            if (rear == n - 1)
                res = true;
            return res;
        }
        public string Front()
        {
            string res = "-1";
            if (IsQueueEmpty())
                return res;
            res = queue[front + 1];
            return res;
        }
        public string Back()
        {
            string res = "-1";
            if (IsQueueEmpty())
                return res;
            res = queue[rear];
            return res;
        }
    }
}
 
 
cs

 

출력값들을 StringBuilder형 변수에 넣고 출력하는 과정에서 마지막에 생기는 공백을 없애기 위한 코드인

if (sb[sb.Length - 1== '\n')

이 코드가 sb의 길이가 0인 경우 (n번의 입력동안 push만 한 경우) indexOufOfRange 에러가 나는 실수를 했다.

2024-05-20 23:51:33

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _28279_boj boj = new _28279_boj();
 
            boj.boj_28279();
 
        }
    }
        internal class _28279_boj
    {
        public void boj_28279()
        {
            StringBuilder sb = new StringBuilder();
            Deque deque = new Deque();
            deque.n = int.Parse(Console.ReadLine()) + 1; // 덱이 가득 찼는지 판별
하기 위해 빈공간을 하나 사용하므로 하나만큼 공간을 더 주었다. (n번동안 push만 할 경우 에러 방지)
 
            deque.deque = new string[deque.n];
 
            for (int i = 0;i < deque.n - 1; i++)
            {
                string[] input = Console.ReadLine().Split();
                switch(input[0])
                {
                    case "1":
                        deque.PushFront(input[1]);
                        break;
                    case "2":
                        deque.PushBack(input[1]);
                        break;
                    case "3":
                        sb.Append(deque.PopFront() + "\n");
                        break;
                    case "4":
                        sb.Append(deque.PopBack() + "\n");
                        break;
                    case "5":
                        sb.Append(deque.size + "\n");
                        break;
                    case "6":
                        sb.Append(deque.IsDequeEmpty() ? "1\n" : "0\n");
                        break;
                    case "7":
                        sb.Append(deque.Bottom() + "\n");
                        break;
                    case "8":
                        sb.Append(deque.peek() + "\n");
                        break;
                }
            }
            Console.Write(sb);
        }
 
 
    }
    public class Deque
    {
        public int n; // 덱의 크기를 결정하는 변수
        public string[] deque; // 덱을 구현할 배열
        public int back = -1; // 가장 뒤에있는 숫자의 주소를 가리킬 변수
        public int front = 0; // 가장 앞에있는 숫자의 주소를 가리킬 변수
        public int size = 0; // 덱의 원소의 수를 저장하는 변수
        public void PushFront(string data)
        {
            if (IsDequeFull())
                return;
            front = (front - 1 + n) % n; // 0 - 1 + n을 n으로 나누면 n - 1이 나온다 (다음 회차엔 n - 2, n - 3 ...)
            deque[front] = data;
            size++;
        }
        public void PushBack(string data)
        {
            if (IsDequeFull())
                return;
            back = (back + 1) % n;
            deque[back] = data;
            size++;
        }
        public bool IsDequeEmpty()
        {
            bool res = false;
            if ((back + 1) % n == front)
                res = true;
            return res;
        }
        public bool IsDequeFull()
        {
            bool res = false;
            if ((back + 2) % n == front)
                res = true;
            return res;
        }
        public string PopFront()
        {
            string res = "-1";
            if (IsDequeEmpty())
                return res;
            res = deque[front];
            deque[front] = null;
            front = (front + 1) % n;
            size--;
            return res;
        }
        public string PopBack()
        {
            string res = "-1";
            if (IsDequeEmpty())
                return res;
            if (back == -1) // 이 코드가 없으면 PushBack 메소드를 진행하지 않고 PopBack 메소드를 실행할 때 에러가 남
                back = n - 1; // 어차피 PushBack을 실행한 적이 없다면 가장 뒤에있는 원소의 주소는 n - 1
            res = deque[back];
            deque[back] = null;
            back = (back - 1 + n) % n;
            size--;
            return res;
        }
        public string Bottom()
        {
            string res = "-1";
            if (IsDequeEmpty())
                return res;
            res = deque[front];
            return res;
        }
        public string peek()
        {
            string res = "-1";
            if (IsDequeEmpty())
                return res;
            if (back == -1)
            {
                res = deque[n - 1];
                return res;
            }
            res = deque[back];
            return res;
        }
    }
}
 
 
cs

은근히 어려웠다...

덱을 구현하기 위해 원형 큐를 응용한 것까지는 좋았지만, 큐처럼 front는 항상 빈공간(null)을 가리키려고 해서 더욱 헷갈렸던 것 같다.

 

 

'하루 한 접시' 카테고리의 다른 글

[백준] 10799번 : 쇠막대기 [C#]  (0) 2024.05.21
[백준] 10845번 : 큐 [C#]  (0) 2024.05.21
[백준] 2493번 : 탑 [C#]  (0) 2024.05.20
[백준] 1874번 : 스택 수열 [C#]  (0) 2024.05.16
[백준] 요세푸스 문제 0 [C#]  (0) 2024.05.14
2024-05-20 18:59:53

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _2493_boj boj = new _2493_boj();
 
            boj.boj_2493();
 
        }
    }
    internal class _2493_boj
    {
        public void boj_2493()
        {
            var reader = new StreamReader(Console.OpenStandardInput());
            var print = new StreamWriter(Console.OpenStandardOutput());
            var sb = new StringBuilder();
            Stack tower = new Stack();
            tower.size = int.Parse(reader.ReadLine());
            tower.stack = new string[tower.size];
 
            string[] input = reader.ReadLine().Split();
            string[] result = new string[tower.size];
 
            for (int i = 0; i < tower.size; i++)
            {
                while (tower.top != -1 && int.Parse(input[i]) > int.Parse(input[int.Parse(tower.peek())]))
                {
                    tower.pop();
                }
                sb.Append(tower.top == -1 ? "0" : (int.Parse(tower.peek()) + 1).ToString());
                if (i != tower.size - 1)
                    sb.Append(' ');
                tower.push(i.ToString());
            }
 
            print.Write(sb);
            print.Flush();
 
        }
    }
    public class Stack
    {
        public int top = -1;
        public string[] stack;
        public int size;
 
        public void push(string data)
        {
            stack[++top] = data;
        }
        public string pop()
        {
            string res = null;
            if (top != -1)
            {
                res = stack[top];
                stack[top--= null;
            }
 
            return res;
        }
        public string peek()
        {
            string res = null;
            if (top != -1)
                res = stack[top];
            return res;
        }
 
    }
}
 
 
cs

 

 

 

'하루 한 접시' 카테고리의 다른 글

[백준] 10845번 : 큐 [C#]  (0) 2024.05.21
[백준] 28279번: 덱 2 [C#]  (0) 2024.05.20
[백준] 1874번 : 스택 수열 [C#]  (0) 2024.05.16
[백준] 요세푸스 문제 0 [C#]  (0) 2024.05.14
[백준] 2164번: 카드2 [C#]  (0) 2024.05.14