인프런 커뮤니티 질문&답변
작성한 질문수
3-K 시간초과 & 학습 방법 고민있어요
작성
·
287
·
수정됨
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요. 강의 잘 듣고 있습니다.
강의를 참고하여 풀었는데. 시간초과가 뜹니다
#include <bits/stdc++.h>
using namespace std;
int R, C;
vector<vector<char>> lake;
queue<vector<int>> candidates_Swan, candidates_SwanTemp;
queue<vector<int>> candidates_Water, candidates_WaterTemp;
vector<vector<int>> delta = {{-1,0},{1,0},{0,-1},{0,1}};
vector<vector<int>> visitedSwan, visitedWater;
bool moveSwan(){
while(candidates_Swan.size()){
vector<int> now = candidates_Swan.front(); candidates_Swan.pop();
for(auto d : delta){
int next_i = now[0]+d[0];
int next_j = now[1]+d[1];
if (next_i >= 0 && next_j >= 0 && next_i < R && next_j < C){
if (visitedSwan[next_i][next_j] == 0){
visitedSwan[next_i][next_j] = 1;
if (lake[next_i][next_j] == '.'){
candidates_Swan.push({next_i, next_j});
}
else if (lake[next_i][next_j] == 'X'){
candidates_SwanTemp.push({next_i, next_j});
}
else if (lake[next_i][next_j] == 'L') return true;
}
}
}
}
return false;
}
void waterMelting(){
while(candidates_Water.size()){
vector<int> now = candidates_Water.front(); candidates_Water.pop();
for(auto d : delta){
int next_i = now[0] + d[0];
int next_j = now[1] + d[1];
if (next_i >= 0 && next_j >= 0 && next_i < R && next_j < C){
if (visitedWater[next_i][next_j] == 0){
if (lake[next_i][next_j] == 'X'){
candidates_WaterTemp.push({next_i, next_j});
visitedWater[next_i][next_j] = 1;
lake[next_i][next_j] = '.';
}
}
}
}
}
return;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> R >> C;
lake = vector<vector<char>>(R, vector<char>(C));
visitedSwan = vector<vector<int>>(R, vector<int>(C,0));
visitedWater = vector<vector<int>>(R, vector<int>(C,0));
for(int i = 0 ; i < R ; ++i){
string s;
cin >> s;
for(int j = 0 ; j < C; ++j){
lake[i][j] = s[j];
if (lake[i][j] == 'L' && candidates_Swan.empty()){
candidates_Swan.push({i,j}); // 백조는 한마리 위치에서만 시작
visitedSwan[i][j] = 1;
}
if (lake[i][j] == 'L' || lake[i][j] == '.'){
candidates_Water.push({i,j});
visitedWater[i][j] = 1;
}
}
}
int day = 0;
while(true){
if (moveSwan()) break;
waterMelting();
// cout << endl;
// for(auto ll : lake){
// for(auto l : ll) cout << l;
// cout << endl;
// }
// cout << endl;
candidates_Swan = candidates_SwanTemp;
candidates_Water = candidates_WaterTemp;
candidates_WaterTemp = queue<vector<int>>();
candidates_SwanTemp = queue<vector<int>>();
day++;
}
cout << day << "\n";
return 0;
} 강의를 듣기 전에 먼저 문제를 풀고 강의를 듣는 방식을 고수하고 있는데, 한 문제를 푸는데 점점 시간이 늘어나 두시간 정도를 써야 겨우 한문제를 풀고 있습니다.
이런 방식을 고수하는것이 좋을지,
어떻게 해야하나 질문드려요.
감사합니다. ^^
답변 2
0
안녕하세요 성욱님 ㅎㅎ
코드에서, vector<int> now; 의 선언을 while 문 밖에 빼면 시간초과가 뜨지 않네요...
>> 이 문제 자체가 시간초과가 좀 타이트해서 그렇습니다. 로직상은 문제 없습니다.
vector<int> now; // <<<<<<<
while(candidates_Swan.size()){
now = candidates_Swan.front(); candidates_Swan.pop();
이부분에 대해 설명을 드리면요. 별차이는 없습니다만...
메모리 할당에서 좀 더 이득이긴 합니다.
첫 번째 코드에서는 now 변수가 while 루프의 각 반복마다 새로 선언되고, 이에 따라 벡터의 메모리 할당과 해제가 반복적으로 이루어집니다.
반면에 두 번째 코드에서는 now 변수가 루프 밖에서 한 번만 선언되고, 루프 내에서 값만 갱신되므로 메모리 할당과 해제가 루프의 반복에 따라 발생하지 않습니다.
이로 인해 두 번째 코드가 메모리 할당과 해제 측면에서 더 효율적일 수 있습니다. 하지만.. 그 차이가 그렇게 크지는 않습니다만.. 이 문제 자체가 시간초과가 너무 타이트해서 이부분 까지도 효율적으로 만들어야 한다고 넘어가시면 될 것 같습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
안녕하세요 ㅎㅎ 아 제가 이거 답변을 빼먹었네요 ㅠㅠ
강의를 듣기 전에 먼저 문제를 풀고 강의를 듣는 방식을 고수하고 있는데, 한 문제를 푸는데 점점 시간이 늘어나 두시간 정도를 써야 겨우 한문제를 풀고 있습니다.
>> 1 ~ 2시간은 지극히 정상적입니다. 고수해주세요.
0
코드에서, vector<int> now; 의 선언을 while 문 밖에 빼면 시간초과가 뜨지 않네요...
bool moveSwan(){
vector<int> now; // <<<<<<<
while(candidates_Swan.size()){
now = candidates_Swan.front(); candidates_Swan.pop();
void waterMelting(){
vector<int> now; // <<<<<<<
while(candidates_Water.size()){
now = candidates_Water.front(); candidates_Water.pop();
답변 감사합니다.
본 게시글에 2번 질문도 도움 주실수 있으신가요?