<div id="readability-page-1" class="page"><div>
  
  <p><span>27 Jun 2021</span></p><p>위상 정렬 연습용으로 찾은 문제 <a href="https://leetcode.com/problems/course-schedule-ii/">210. Course Schedule II</a>.</p>

<pre><code>typedef struct pr {
    int subjectCode;
    struct pr *next;
} COURSELIST;

typedef struct st {
    int NumPrerequisites;
    COURSELIST* after;
} COURSES;

COURSES *courses;
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findOrder(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int* returnSize){
    int classTaken = 0;
    int *ret = calloc(numCourses, sizeof(int));
    courses = calloc(numCourses, sizeof(COURSES));
    for(int idx=0; idx&lt;prerequisitesSize; idx++){
        int courseIdx = prerequisites[idx][0]; 
        int preIdx = prerequisites[idx][1];

        courses[courseIdx].NumPrerequisites += 1; //선수강과목 갯수 더해주고
        
        COURSELIST *newNext = calloc(1, sizeof(COURSELIST));  // 선수강과목의 '들으면 수강 할 수 있는 강의 리스트'에 추가해줌
        newNext-&gt;subjectCode = courseIdx;
        newNext-&gt;next = courses[preIdx].after;
        courses[preIdx].after = newNext;
    }
    int *preZeroIdxQueue = calloc(numCourses, sizeof(int));
    int pushPtr = 0;
    int popPtr = 0;
    for(int idx=0; idx &lt; numCourses; idx++) {  // 선수강과목이 없는 과목들을 먼저 큐에 넣음
        if(courses[idx].NumPrerequisites == 0)
        {
            preZeroIdxQueue[pushPtr++] = idx;
        }
    }
    
    while(pushPtr &gt; popPtr) {
        int courseIdx = preZeroIdxQueue[popPtr++];  // courseIdx를 수강했다.
        ret[classTaken++] = courseIdx;  // 큐에서 하나씩 빼서 정답에 담기
        COURSELIST *courList = courses[courseIdx].after;
        while(courList != 0){  // '들으면 수강할 수 있는 과목 리스트'를 돌면서
            int subJectIdx = courList-&gt;subjectCode;
            courses[subJectIdx].NumPrerequisites--;  // 선수강 과목 갯수를 -1 해줌 (하나 들었으니까)
            if(courses[subJectIdx].NumPrerequisites == 0) {  //선수강과목이 없어진 과목이 있다면
                preZeroIdxQueue[pushPtr++] = subJectIdx;  // 큐에 넣어준다
            }
            courList = courList-&gt;next;
        }
        
    }
    free(courses);
    free(preZeroIdxQueue);
    
    if(classTaken != numCourses) {
        *returnSize = 0;
    } else {
        *returnSize = classTaken;
    }
    
    return ret;
}
/*
0-&gt;1
0-&gt;2
1-&gt;3
2-&gt;3

0 : no pre -&gt; 0 should have idx of 1, 2
1 : 0
2 : 0
3 : 1, 2

0
0 : -1
1 : no pre
2 : no pre
3 : 1, 2

1, 2
0: -1
1 : -1
2: -1
3 : 0

3

3
[[1,0],[1,2],[0,1]]
0-&gt;1
2-&gt;1
1-&gt;0
*/
</code></pre>

<p>위상 정렬도 queue를 사용해서 풀다보니 보통 자료구조 지원하는 언어 코드가 많았다.
생각해보니 linked list 순회해가며 free 해줬어야 하는데 안해도 통과되었다… 너그러운 리트코드…</p>

</div></div>

Annular Eclipse

Gayuna

위상 정렬 연습용으로 찾은 문제 210. Course Schedule II.
typedef struct pr {
    int subjectCode;
    struct pr *next;
} COURSELIST;
typedef struct st {
    int NumPrerequisites;
    COURSELIST* after;
} COURSES;
COURSES *courses;
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findOrder(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int* returnSize){
    int classTaken = 0;
    int *ret = calloc(numCourses, sizeof(int));
    courses = calloc(numCourses, sizeof(COURSES));
    for(int idx=0; idx<prerequisitesSize; idx++){
        int courseIdx = prerequisites[idx][0]; 
        int preIdx = prerequisites[idx][1];
        courses[courseIdx].NumPrerequisites += 1; //선수강과목 갯수 더해주고
        
        COURSELIST *newNext = calloc(1, sizeof(COURSELIST));  // 선수강과목의 '들으면 수강 할 수 있는 강의 리스트'에 추가해줌
        newNext->subjectCode = courseIdx;
        newNext->next = courses[preIdx].after;
        courses[preIdx].after = newNext;
    }
    int *preZeroIdxQueue = calloc(numCourses, sizeof(int));
    int pushPtr = 0;
    int popPtr = 0;
    for(int idx=0; idx < numCourses; idx++) {  // 선수강과목이 없는 과목들을 먼저 큐에 넣음
        if(courses[idx].NumPrerequisites == 0)
        {
            preZeroIdxQueue[pushPtr++] = idx;
        }
    }
    
    while(pushPtr > popPtr) {
        int courseIdx = preZeroIdxQueue[popPtr++];  // courseIdx를 수강했다.
        ret[classTaken++] = courseIdx;  // 큐에서 하나씩 빼서 정답에 담기
        COURSELIST *courList = courses[courseIdx].after;
        while(courList != 0){  // '들으면 수강할 수 있는 과목 리스트'를 돌면서
            int subJectIdx = courList->subjectCode;
            courses[subJectIdx].NumPrerequisites--;  // 선수강 과목 갯수를 -1 해줌 (하나 들었으니까)
            if(courses[subJectIdx].NumPrerequisites == 0) {  //선수강과목이 없어진 과목이 있다면
                preZeroIdxQueue[pushPtr++] = subJectIdx;  // 큐에 넣어준다
            }
            courList = courList->next;
        }
        
    }
    free(courses);
    free(preZeroIdxQueue);
    
    if(classTaken != numCourses) {
        *returnSize = 0;
    } else {
        *returnSize = classTaken;
    }
    
    return ret;
}
/*
0->1
0->2
1->3
2->3
0 : no pre -> 0 should have idx of 1, 2
1 : 0
2 : 0
3 : 1, 2
0
0 : -1
1 : no pre
2 : no pre
3 : 1, 2
1, 2
0: -1
1 : -1
2: -1
3 : 0
3
3
[[1,0],[1,2],[0,1]]
0->1
2->1
1->0
*/
위상 정렬도 queue를 사용해서 풀다보니 보통 자료구조 지원하는 언어 코드가 많았다.
생각해보니 linked list 순회해가며 free 해줬어야 하는데 안해도 통과되었다… 너그러운 리트코드…

leetcode 210. Course Schedule II

댓글