알고리즘

[구름 LEVEL] 장마, 0커플, (현대모비스 예선) 주차시스템

재롱2 2024. 6. 14. 13:50

 

 드디어 내일 1차 코딩테스트가 있는 날입니다. 하루에 2~3문제 꾸준히 풀고 있지만

같은 플랫폼 문제 3개씩 모아서 글을 쓰려다 보니 포스팅이 늦어지네요.

 

 크롬 익스텐션 개발한 것도 정리중인데, 양이 은근히 많아서 3월 10일에 웹스토어에 배포했는데

벌써 6월 14일..

 

아무튼 첫번째 문제는 장마입니다.

문제를 정리하면 집은 1차원 선 모양으로 1번부터 N번까지 번호가 붙여져 있습니다.

각각의 집은 정수로 표현되는 높이를 가지고 있고 이는 비가 오면 변화합니다.

주어지는 M일 동안 쉬지 않고 [Si , Ei] 구간에 비가 옵니다. 비가 오면 그 집의 높이가 1 증가합니다.

 

배수시스템은 장마가 시작하고 3일의 텀마다 작동하는데 3일의 텀 동안 그 집에 비가 한 번이라도 내렸다면

 높이가 1 감소합니다.

 

import sys
n,m = map(int,sys.stdin.readline().split())
g = list(map(int,sys.stdin.readline().split()))
rain = []
for i in range(m):
	st,end = map(int,sys.stdin.readline().split())
	for j in range(st-1,end):
		g[j] += 1
		if j not in rain: 
			rain.add(j)
	if (i+1)%3==0:
		for j in rainlist: g[j] -= 1
		rain = []
print(*g)

 

이게 처음에 작성했던 코드인데, m일 동안 비가 온 집의 높이를 증가시키고 rain 배열에 없다면 그 집 인덱스를 추가하는 방식입니다. 그런데 이렇게 작성하면 마지막 테케에서 통과를 할 수 없습니다.

9번 테케부터 시간이 엄청 오래 걸리는 것을 볼 수 있는데, 아마 중간에 이미 비가 내렸던 집인지 확인하는 탐색이 있기 때문에 최악의 경우 m(비가 오는 일 수 )*n(비가 온 집의 구간)*n(비가 온 여부를 저장하는 rain)이라 10의 11 제곱의 탐색이 있습니다. 따라서 C++로 언어를 변경하려다가

import sys
n,m = map(int,sys.stdin.readline().split())
g = list(map(int,sys.stdin.readline().split()))
rain = set()
rainlist = []
for i in range(m):
	st,end = map(int,sys.stdin.readline().split())
	for j in range(st-1,end):
		g[j] += 1
		if j not in rain: 
			rain.add(j)
			rainlist.append(j)
	if (i+1)%3==0:
		for j in rainlist: g[j] -= 1
		rain = set()
		rainlist = []
print(*g)

set을 사용하여 판별했더니 실행시간이 약 8초 정도 감소했습니다. 하지만 set은 iterable 하지 않아서 따로 rainlist로 

iterable 한 리스트를 만들어 사용했습니다. 판별에는 set을 사용하고 탐색은 배열을 사용하여 역할을 분리했습니다.

- 0 커플

0 커플은 n명의 사람이 주어지고 각각 -200,000 <= Si <= 200,000 범위의 점수를 갖습니다.

이 중 더하여 0이 되는 커플은 제외하고 나머지 사람의 점수의 합을 구하는 문제입니다.

 

우선 정렬을 하지 않으면 2중 탐색으로 찾아야 하지만 n의 범위가 10만이기 때문에 2중 for문으로는 해결할 수 없습니다.

사실 n의 범위만 보고 해결방식을 선택하면 안 되지만 간단한 문제는 도움은 받을 수 있습니다.

 

일단 정렬이 되었다고 가정을 하면 입력 예시 1에서 이런 모습으로 정렬이 되어있을 텐데, 저는 안쪽부터 탐색을 했습니다.

-5 -3 -2 -1 1 2 3 4
import sys

n = int(sys.stdin.readline())
g = list(map(int,sys.stdin.readline().split()))
g.sort()
left = n//2 -1
right = left+1
res = 0
while(1):
	if left <0 or right > n-1: break
	
	if g[left]+g[right] > 0:
		res += g[left]
		left -= 1
	elif g[left]+g[right]<0:
		res += g[right]
		right += 1
	else:
		left-= 1
		right += 1
if left>=0:
	res += sum(g[0:left+1])
if right<n:
	res += sum(g[right:n])
print(res)

 

left 변수와 right 변수를 놓고 만약에 left와 right를 더해서 0보다 크다면 left를 한 칸 왼쪽으로 옮겨 0이 되는지 판별합니다. 만약에 더해서 0보다 작다면 반대로 right를 오른쪽으로 옮깁니다. 마지막으로 0이 되면 둘 다 한 칸씩 옮깁니다. 

while 문을 나왔는데 left 랑 right가 남아있다면 더해주면 끝입니다.

문제의도는 앞쪽과 뒤쪽에서 pop이 가능한 덱으로 저는 가운데부터 탐색했지만 덱을 양 끝쪽부터 탐색해서

마지막에 덱에 남아있는 원소를 내보내면 되는 문제였습니다.

 

- [현대모비스][예선] 주차시스템

이 문제는 설명이 길긴 한데 특별한 조건은 없고 숫자 1은 벽, 0과 2는 지나갈 수 있는 그래프 탐색문제입니다.

 

  전형적인 2차원 bfs/dfs 탐색에서 점수가 다른 조건 하나만 들어갔을 뿐, bfs로 탐색가능한 각 영역의 크기를 구할 수 있다면 충분히 해결가능한 문제입니다. 백준에서 비슷한 문제로는 

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

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

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

https://www.acmicpc.net/source/68896496

매우 많지만 4개만 첨부합니다!

하지만 문제가 파이썬으로는 시간초과가 발생해서,, 최적화를 아무리 해도 해결할 수 없었습니다.

그래서 C++로 작성해서 제출하니 바로 통과를 받았습니다. 이건 아직 구름에서 언어별로 시간제한을 적절하게 주지 않은 게 문제가 아닌가..

같은 코드지만 C++ 만 통과한다면,,

#include <iostream>
#include <queue>
#define MAX 2001

using namespace std;

int N, M;
int m[MAX][MAX];
int visited[MAX][MAX] = {0};
int dist[MAX][MAX];

int x_dir[4] = {-1, 1, 0, 0};
int y_dir[4] = {0, 0, -1, 1};

queue<pair<int,int> > q;

// 미로 경로 탐색
int bfs(int start_x, int start_y){

 	visited[start_x][start_y] = 1;
    q.push(make_pair(start_x,start_y));
    dist[start_x][start_y]++;
	int c ;
	if (m[start_x][start_y]==0) c = 1;
	else c = -2;

    while (!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

        for (int i=0; i<4; ++i){
            int x_new = x + x_dir[i];
            int y_new = y + y_dir[i];
            if ( (0 <= x_new && x_new < N) && (0 <= y_new && y_new < M) 
            && !visited[x_new][y_new] && m[x_new][y_new] != 1 ){
				if (m[x_new][y_new] == 0) c += 1;
				else c -= 2;
                visited[x_new][y_new] = 1;
                q.push(make_pair(x_new, y_new));
            }
        }
    }
	return c;
}

int main(){

    cin >> N >> M;
	int Max = -1;
    for (int i=0; i<N; ++i){
     for (int j=0; j<M; ++j){
        	cin >> m[i][j];
        }
    }

	for(int i = 0; i<N; i++){
		for (int j = 0; j<M; j++){
			if (m[i][j] != 1 && visited[i][j] == 0)
				Max = max(Max, bfs(i,j));
			}
		}
	if (Max < 0) cout<<0;
	else cout<<Max;

}