프로그래머스 Lv 2. 42586 c++ 기능개발 (시간 초과에 빠지는 경우 참고 사항) **추가학습 필요**

https://school.programmers.co.kr/learn/courses/30/lessons/42586

 

처음에 작성한 코드를 첨부해보겠다. 아래의 코드의 경우 시간초과가 뜨는 예제케이스가 있어서 통과하지 못했다. 

//잘못된 풀이
#include <bits/stdc++.h>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> q;
    queue<int> qt;
    for(auto tc: progresses) q.push(tc);
    for(auto tc: speeds) qt.push(tc);
    int t=0;
    while(true){
        int p=0;
        t++;
        
        while(q.front()+t*qt.front()>=100){
            p++;
            q.pop();
            qt.pop();
        }
        if (p!=0) answer.push_back(p);
        if(q.empty()) break;
    }
    
    return answer;
}

하루죙일 도대체 뭐가 잘못됐을까 생각했는데, 확실하게 찾아내지 못했는데, 그래서 다른 사람의 풀이에서 이와 같은 상황을 만난 사람은 없을까 찾았을때, 나와 같은 상황을 3년전에 질문한 사람이 있었는데, 답장이 달리지 않아서 이유를 알아내지 못하였다. 그러다가 다른 사람의 풀이를 찾아볼때, 코드의 형태는 다르지만, 그래도 로직은 결국 나와 비슷한 사람의 코드에서, while(q.front()+t*qt.front()>=100) 형태로 작성된 것이 아니라 !q.empty() && 까지 같이 붙어있는것을 발견하고, 나도 그와 같이 !q.empty() &&을 붙인 코드를 제출하였으며 그 코드로 시간초과 없이 통과하였다. 

 

해당 코드는

#include <bits/stdc++.h>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> q;
    queue<int> qt;
    for(auto tc: progresses) q.push(tc);
    for(auto tc: speeds) qt.push(tc);
    int t=0;
    while(true){
        int p=0;
        t++;
        
        while(!q.empty() && q.front()+t*qt.front()>=100){
            p++;
            q.pop();
            qt.pop();
        }
        if (p!=0) answer.push_back(p);
        if(q.empty()) break;
    }
    
    return answer;
}

위의 코드와 !q.empty() && 만 다르고 전부 똑같다. 

 

이때에 위의 코드에서, 다른 예제에서 통과하는 경우도 존재하고, 그리고 내 맥에서 프로그램을 만들어서 돌려보았을때도 통과를 하는 상황이었고, 도대체 뭐가 잘못되었을까 찾아보기 위해 이런저런 실험을 해보았다. 

 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    queue<int> q;
    queue<int> qt;
    /* 블락 1
    // q.push(1);
    // qt.push(2);
    // q.pop();
    // qt.pop();
    */
    if(q.empty()) cout<<"q is empty"<<'\n';
    if(qt.empty()) cout<<"qt is empty too"<<'\n';
    cout<<q.front()<<" :empty q value"<<'\n';
    cout<<qt.front()<<" :empty qt value"<<'\n';
    int t=5;
    while(qt.front()+t*q.front()<100){
        cout<<q.front()<<'\n';
        cout<<qt.front()<<'\n';
        cout<<qt.front()+t*q.front()<<'\n';
        break;
    }
}

일단 애초부터 세그멘테이션 폴트가 나면서 정상적으로 동작하지 않아야 하는것 아닌가 하고 위와 같은 코드를 만들어서 시도해보니, 

첫번째. 블락1을 주석처리 하지 않고 queue인 q와 qt에 원소를 넣었다가 빼낸 경우, 분명 empty()인데 q.front(), qt.front()를 출력해보면 0이라는 값이 나오게 된다. 

두번째. 블락1을 주석처리 하고 queue인 q와 qt에 원소를 넣었다가 빼내지 않은 경우, 분명 empty()이고, q.front(), qt.front()를 출력해보면 세그멘테이션 폴트가 발생한다. 

아래는 현재 내 설정도 같이 출력되는 상황에서의 두가지 케이스의 결과물에 대한 이미지 캡쳐본이다.

이렇듯 queue에 값을 넣었다가 빼면, empty()여도 front()에 접근했을때 segmentation fault가 발생하지 않는다. 

그리고 segmentation fault 또한 위의 코드들이 실행되어서 출력물을 보여주다가 발생하게 된다. 

 

아주아주 골치아픈 상황이 아닐 수 없다. 단순하게 나는 segmentation fault 가 발생해서 쉽게 문제점을 찾아낼 수 있을것이라고 생각했는데, 그렇지가 않았다. 위와 같은 상황들에 대해서 관련되어 있을 만한 내용들을 gpt에서 정보를 얻을 수 있었다. 

 

"정의되지 않은 동작(Undefined Behavior)"은 프로그래밍 언어와 런타임 환경의 규격에서 정확하게 정의되지 않은 상황에서 발생하는 동작을 나타냅니다. 이것은 프로그램이 논리적으로 예측할 수 없는 결과를 가질 수 있음을 의미합니다. 정의되지 않은 동작은 주로 다음과 같은 경우에 나타납니다:

1. **배열 경계를 벗어나는 접근**: 배열의 유효하지 않은 인덱스에 접근하거나, 배열의 범위를 벗어나는 메모리를 읽거나 쓸 때. 이로 인해 메모리 손상 또는 예기치 않은 동작이 발생할 수 있습니다.

2. **초기화되지 않은 변수 사용**: 변수를 초기화하지 않고 사용할 때, 해당 변수의 내용이 무작위로 나올 수 있습니다.

3. **포인터 오버플로우 또는 언더플로우**: 메모리를 할당하거나 해제하지 않고 포인터를 조작할 때 발생할 수 있습니다. 이로 인해 메모리 손상이나 비정상적인 프로그램 동작이 발생할 수 있습니다.

4. **무한 루프**: 무한 루프를 만들거나, 탈출 조건을 지정하지 않은 루프에서 런타임 환경에 따라 예상치 못한 동작이 발생할 수 있습니다.

정의되지 않은 동작은 프로그램에서 피해야 하며, 이로 인한 예기치 못한 동작을 방지하기 위해 프로그램을 신중하게 작성해야 합니다. 또한 다른 컴파일러나 플랫폼에서는 정의되지 않은 동작이 다를 수 있으므로 이에 대한 주의가 필요합니다. C++와 C 언어는 다양한 상황에서 정의되지 않은 동작을 가질 수 있는 언어로, C/C++ 프로그래머는 이를 피하기 위해 엄격한 규칙을 따라야 합니다.

 

 

C++의 표준 라이브러리(queue 포함)는 보통 일부 함수에서 "정의되지 않은 동작(undefined behavior)"을 피하도록 설계되어 있습니다. 이는 queue의 `front()` 함수 역시 해당합니다. 

만약 큐가 비어있는 상태에서 `q.front()`나 `qt.front()`를 호출하면 정의되지 않은 동작이 발생할 것으로 생각될 수 있지만, C++ 표준 라이브러리의 구현체는 이러한 상황에서 예외를 던지거나(throw), 또는 기본적으로 0 또는 빈 값을 반환하도록 설계되어 있습니다. 

따라서 `q.front()`와 `qt.front()`를 호출하면 큐가 비어있는 경우에도 segmentation fault가 발생하지 않고 0의 값을 반환하게 됩니다. 그렇기 때문에 이러한 코드에서는 segmentation fault가 발생하지 않고 0의 값이 출력되었습니다. 

그러나 이러한 동작은 C++ 표준에 명시적으로 정의된 것이 아니라, 표준 라이브러리 구현체에 따라 다를 수 있으므로 다른 환경에서는 정의되지 않은 동작이 발생할 수 있으므니다. 따라서 코드를 작성할 때 큐가 비어있는지 항상 확인하고 접근하는 것이 좋습니다.

 

위의 내용들을 통해 유츄해보자면, 내가 현재 돌리고 있는 상황에서는 queue에 원소를 아무것도 넣지 않은 상황에서는 q.front()를 했을때 segmentation fault를 내보내고, 넣었다가 뺀 상황에서의 queue에서는 0을 반환하게 라이브러리가 구현되어 있는 상황이라는 얘기가 되는것 같다. 그리고 이런 상황이라 넣었다 뺀 상황에서의 queue의 원소에 대한 접근을 하니까 0이 되고, 해당 값들을 통해서 연산한 것이 while문에서 true가 아니게 되니까 정상적으로 동작한것으로 보여진다. 

그런데 프로그래머스의 컴파일환경에서는 나와 같은 결과물이 나오지 않은 설정이라 내 맥에서 구동한것과 같지 않은 결과물이 나온것이 아닐까 싶다. 그리고 정의되지 않은 동작이 발생해서 정말 예상하기 쉽지 않은 결과물이 나오는 상황이 내가 만든 코드에서 발생하는것이라고 예상된다. 

 

일단 애초부터 empty()가 되었을 텐데 원소에 접근하는 것 자체가 내가 작성한 코드에서 일단 문제점이 있다. 

 

이번 일을 통해서 queue나 stack등의 자료구조에서 empty()일때에 원소에 접근하는 형태의 코드를 절대로 작성하지 말도록 하고, 확실하게 !q.empty() && 등으로 empty() 일때를 제외한 상황에서의 제어를 할 수 있도록 만들자. 

 

그리고 이 부분에 대해서는 추가적으로 더욱 학습을 통해서 어떤식으로 내부 구현이 되어있고, 왜 0을 반환하는지 등에 대해서 더욱 공부해볼 여지가 있을것 같다. 현재 상황에서는 이 문제를 붙잡고 이러한 문제점을 발견하는데 하루를 다 보냈기 때문에 이만 마무리 짓겠다. 

 

누군가 나와 같이 자신이 잘 작성했다고 생각하고, 많은 예제에서 제대로 통과하는데, 몇몇 예제에서 시간초과가 발생하는 형태의 코드를 작성했는데 문제점을 발견하지 못하고 있다면 도움이 되길 바란다.