[2023 알고리즘 스터디] 5조 #3주차 - 스택, 큐

FOSCAR 알고리즘 스터디 2주차 5조 블로깅

 

뱀 - 코드 리뷰 이진호

• 문제 링크

https://www.acmicpc.net/problem/3190

2138번: 전구와 스위치

 

• 풀이

구현에 이용된 자료구조는 큐입니다.

맵을 탐색할 때는 뱀이 현재 진행하는 방향으로 탐색하는것이 중요합니다.

큐에서 머리의 좌표를 꺼낼 때마다 시간을 비교하여 방향을 변환하고 자신의 몸이나 벽을 만나면 시간을 반환합니다.

 

import sys
from collections import deque
input = sys.stdin.readline

def solve(stage, controls):
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    que = deque()
    que.append((0, 0))
    n = len(stage)
    direction = 0
    i = 0
    time = 0
    x, command = controls[i]
    while True:
        if time == int(x):
            if command == 'D':
                direction = (direction + 1) % 4
            else:
                direction = (direction - 1) % 4
            i += 1
            if i < len(controls):
                x, command = controls[i]
        r, c = que.pop()
        que.append((r, c))
        nr, nc = r + dx[direction], c + dy[direction]
        if (0 <= nr < n) and (0 <= nc < n):
            if stage[nr][nc] == 2:
                break
            elif stage[nr][nc] == 0:
                r, c = que.popleft()
                stage[r][c] = 0
            que.append((nr, nc))
            stage[nr][nc] = 2
            time += 1
        else:
            break
    print(time+1)

if __name__ == '__main__':
    n = int(input().rstrip())
    stage = [[0 for _ in range(n)] for __ in range(n)]
    stage[0][0] = 2
    k = int(input().rstrip())
    for _ in range(k):
        r, c = map(int, input().rstrip().split())
        stage[r-1][c-1] = 1
    l = int(input().rstrip())
    controls = [tuple(map(str, input().rstrip().split())) for _ in range(l)]
    solve(stage, controls)

 

 

 

쇠막대기 - 코드 리뷰 이승찬

• 문제 링크

https://www.acmicpc.net/problem/10799

2138번: 전구와 스위치

• 풀이

스택을 이용하여 구현한다.

열린괄호는 넣어주고 닫힌 괄호가 나왔을 때 앞의 괄호가 열린괄호면 제일 긴 조각을 추가

닫힌괄호면 1을 더한다.

 

bar = input()
stk = []
ans = 0
for i in range(len(bar)):
    if bar[i] == '(':
        stk.append('(')
    # stk에 열린 괄호 계속 넣어주기
    else: # 닫힌 괄호가 나오면
        if bar[i-1] == '(':
            stk.pop()
            ans += len(stk)
        # 앞에 괄호가 닫힌 괄호이면 닫힌괄호 pop시키고 젤 긴 조각 길이 추가
        else:
            stk.pop()
            ans += 1
        # 닫힌 괄호가 계속 나오면서 내림차순으로 막대의 길이를 더해줌
print(ans)

 

 

 

탑 - 코드 리뷰 박병규

• 문제 링크

https://www.acmicpc.net/problem/2493

2138번: 전구와 스위치

• 풀이

stack에 다 저장을하면 stack과 list를 다 확인하는데 시간초과가 나온다.

k번째 입력이 들어오면 스택에는 1~k-1번째 입력중에서 k번쨰 입력보다 작은 입력값은

stack에서 제거를 해두어야한다.

 

#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <bitset>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <stack>
using namespace std;

int n, k;
// int arr[500001];
stack<pair<int,int>> st;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> k;

        while(!st.empty()){
            if(st.top().second > k){
                cout << st.top().first << ' ';
                break;
            }
            st.pop();
        }
        if(st.empty()) cout << 0 << ' ';

        st.push({i,k});
    }
    
    return 0;
}

 

 

 

별 찍기 - 10 - 코드 리뷰 박준석

• 문제 링크

https://www.acmicpc.net/problem/2447

2138번: 전구와 스위치

• 풀이

N은 3의 거듭제곱 입니다.

N = 3 일 때 빈칸 - (1,1)

N= 9 일 때 빈칸 - (1,1), (1,4) , (1,7), (4,1), (4,4),(4,7), (7,1),(7,4),(7,7)

이 규칙을 만족 시키기 위한 조건은

(x좌표)%3 == 1 && (y좌표)%3 == 1 이다

또한 N = 9일 때 가운데 빈칸

:(3,3) (3,4) (3,5) (4,3) (4,4) (4,5) (5,3) (5,4) (5,5)

이 규칙을 만족 시키기 위한 조건은

(x좌표/ 3) % 3 == 1 && (y좌표 / 3 ) % 3 == 1이다.

이 도형은 프렉탈 구조로 재귀적으로 반복하면 풀 수 있다.

N = 3 일 때 빈칸 - (1,1)

N= 9 일 때 빈칸 - (1,1), (1,4) , (1,7), (4,1), (4,4),(4,7), (7,1),(7,4),(7,7)

이 규칙을 만족 시키기 위한 조건은

(x좌표)%3 == 1 && (y좌표)%3 == 1 이다

또한 N = 9일 때 가운데 빈칸

:(3,3) (3,4) (3,5) (4,3) (4,4) (4,5) (5,3) (5,4) (5,5)

이 규칙을 만족 시키기 위한 조건은

(x좌표/ 3) % 3 == 1 && (y좌표 / 3 ) % 3 == 1 이다.

이 도형은 프렉탈 구조로 재귀적으로 반복하면 풀 수 있다.

 

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

void recur(int i, int j, int N) {
	if ((i / N) % 3 == 1 && (j / N) % 3 == 1) {
		cout << ' ';
	}
	else {
		if (N / 3 == 0) {
			cout << "*";
		}
		else {
			recur(i, j, N / 3);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//입력
	int N;
	cin >> N;
	
	//x좌표
	for (int i = 0; i < N; i++) {
		//y좌표
		for (int j = 0; j < N; j++) {
			recur(i, j, N);
		}
		cout << "\n";
	}
}