[자몽꿈 - 2주차] 코딩 테스트

kakao x 9oorm 구름톤 유니브 3기

 

교내 스터디 - 자몽꿈

---

#0 주제 선정과 블로그

아마 이번 주차 후기부터 후기가 몰아서 올라갈 예정이다.
블로그를 작성은 해놨지만, 오타 검수와 내용 확인을 하다 보니 내용이 조금 밀렸다.
추석 연휴에는 교내 스터디 휴식기이므로 차례대로 검수 후 차례대로 올릴 예정이다.

2주 차에는 아직도 KDT가 수강 되지 않아서 코딩 테스트 연습을 진행했다.
이는 KDT 풀스택 11회차 과정에서 매달 코딩테스트를 진행하기에 연습 겸 진행을 했다.
팀원은 코딩테스트를 한 번도 진행해 보지 않았고, 나도 오랜만에 코딩테스트를 진행하였기에 감을 살리고자 진행하였다.

---

#1 팀 회의

2주 차 회의는 만나서 진행하였다.
마침, 학교에 있던 시간이 비슷하고 늦은 시간에 회의하는 것보다 이 기회에 진행하는 게 효율적으로 느껴졌다.

2주차 회의 - 제법 MZ한 회의 사진이다.

 

코딩테스트 경험과 난이도가 다르므로 여러 부분을 조율해서 아래와 같이 규칙을 정했다.

 

강의 주제
코딩 테스트

선정 이유
KDT 강의가 8월 26일로 연기됨에 따라 학습 주제를 자체 선정하였습니다.<br>
KDT 풀스택 과정에서 매주 1회 모의 코딩 테스트를 진행하여 이에 대비하고자합니다.

학습 방법
1. 코딩 테스트는 프로그래머스로 진행

2. 프로그래머스와 깃 허브를 연동하여 자동 업로드
📌 연동 참고 자료
백준 & 프로그래머스 깃 허브 연동
    
3. 풀이 기간 : 08.20 ~ 08.24(5일간)

4. 코딩 테스트 언어
    1. 팀원 - Java (Flutter 언어 미제공)
    2. 조희우 - Kotlin

5. 코딩테스트는 각 팀원의 난이도에 맞게 풀이
    1. 팀원 - 코딩 기초 트레이닝 과정에 맞춰 문제 풀이
    2. 조희우 - level2 문제 풀이

6. 문제는 난이도 맞춰 풀이
    1. 팀원 - 5문제 이상 (코딩 기초 트레이닝 과정)
    2. 조희우 - 1문제 이상
    - 문제 난이도에 따라 풀이가 불가능 할 경우 보류 문제 및 해결 진행도를 공유

7. 자동 업로드된 코드 정리를 파일로 이동

8. ReadMe에 통합 작성하기
    1. 가장 어려웠던 문제
        1. 문제 이름
        2. 문제
        3. 본인 코드
        4. 문제 도출 과정
        5. 소감

    2. 코테 풀이 인증
        1. github 연동 목록 캡쳐
        2. 프로그래머스 기록 캡쳐
        3. 팀원 : 코딩 기초 트레이닝 캘린더 캡쳐

    3. 그 외는 팀 규칙에 맞춰서 작성

 

 

---

#2 코딩 테스트

1문제 이상으로 하였지만 시간이 나면 더 풀어보려고 했다.
하지만 level 2로 문제를 풀다 보니 문제를 풀고나면 피로감이 생겼다. 머리를 쓰고 주체적으로 학습하는 건 어려운 일이다.
결국, 원대한 목표는 어디 가고 하루에 한 문제를 학습하여 5문제를 학습했다.
아래는 풀이한 문제의 목록으로 이름과 프로그래머스 번호로 되어있다.
보통 level 2로 필터링 후 정답률이 높은 순으로 문제를 풀이하지만, 이해가 되지 않은 문제도 몇 개 건너뛰었다.
꾸준히 코딩테스트를 해야 하는데 쉽지 않다….

피보나치 수; 12945
멀리뛰기; 12914
예상 대진표; 12985
괄호 회전하기; 79502
뒷 큰 수 찾기; 154539

 

---

#3 PR

이번에 학습한 모든 코딩테스트를 풀이할 수는 없어 규칙에도 나와있듯이 어려웠던 문제를 설명해보았다.

아래는 올린 md 파일의 내용이다.

2주차 - 코딩 테스트
문제 이름 : 뒷 큰 수 찾기 (154539)

가장 어려웠던 문제
문제 설명
정수로 이루어진 배열 numbers가 있습니다. 배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다. 정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한사항
4 ≤ numbers의 길이 ≤ 1,000,0001 ≤ numbers[i] ≤ 1,000,000

입출력 예
numbersresult[2, 3, 3, 5][3, 5, 5, -1][9, 1, 5, 3, 6, 2][-1, 5, 6, 6, -1, -1]

입출력 예 설명
입출력 예 #12의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.입출력 예 #29는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.

코드

import java.util.ArrayDeque

class Solution {
    fun solution(numbers: IntArray): IntArray {
        
        val len = numbers.size
        val answer = IntArray(len)
        val stack = ArrayDeque<Int>()

        for (i in numbers.indices) {
            while (stack.isNotEmpty() && numbers[stack.peekLast()] < numbers[i]) {
                answer[stack.removeLast()] = numbers[i]
            }
            stack.addLast(i)
        }

        while (stack.isNotEmpty()) {
            answer[stack.removeLast()] = -1
        }

        return answer
    }
}​

문제 풀이 도출 과정
1. 문제 분석주
어진 numbers를 순회하면서 현재 위치보다 뒤에 있는 수를 확인한다.
현재 위치보다 뒤에 있는 수 중에 현 위치의 수보다 가장 가까운 수를 answer에 넣는다.
그러기 위해서는 현재 위치의 index 값을 확인한다.

2. 아이디어
스택 구조로 문제를 확인할 수 있을 것이라 생각한다.
현재 위치에서 뒤에 있는 숫자를 확인하는 것이 아닌, 현재 숫자를 기점으로 앞에 숫자들을 비교하는 방식을 사용한다.
스택의 구조를 활용하여 큰 숫자를 찾지 못한 수들의 index 값을 기억하고 현재 숫자와 비교하여 이 숫자가 클 경우 숫자를 기입한다.

3. 구현 방법
배열을 순회하면서 각 숫자에 대해 뒷 큰수를 찾는다.
스택을 사용하여 아직 뒷 큰수를 찾지 못한 인덱스를 저장하고, 현재 숫자가 스택의 마지막 인덱스가 가리키는 숫자보다 크면, 해당 인덱스의 결과를 현재 숫자로 대체한다.
모든 숫자를 순회한 후, 스택에 남아 있는 인덱스들에 대해서는 뒷 큰수가 없으므로 -1을 기입한다.

4. 문제점과 해결 방법
문제에 나와있는 대로 stack을 사용하여 현재 위치를 기반으로 뒤에 있는 숫자들을 순회하려고 하였으나, 그러면 시간 복잡도가 커지는 것을 확인했다.
Deque라는 기능을 발견하였고, 문제 접근 방식을 바꿔 문제를 해결하였다.

소감
문제 접근 방식을 현재 위치를 중점으로 뒤에 있는 수들과 비교하는 방식으로 하니 시간 복잡도가 많이 들어 애를 먹었다.
다른 문제들에 비해 시간이 많이 들었지만, Deque라는 새로운 방식을 알게되어 많은 공부가 되었다.

 

---

#4 Deque

이번 코딩테스트를 하며 Deque를 처음 알았다.Deque의 개념과 특징은 다음과 같다.

 

Deque
Deque (Double-Ended Queue)는 양쪽 끝에서 삽입과 삭제가 가능한 큐이다.

Deque의 특징
양쪽 끝에서의 연산Deque는 양쪽 끝에서 요소를 추가하거나 삭제할 수 있어 큐와 스택의 기능을 모두 사용 가능하다.

빠른 삽입과 삭제Deque는 양쪽 끝에서의 삽입과 삭제를 (O(1)) 시간 복잡도로 수행할 수 있어 매우 효율적이다.

다양한 활용Deque는 큐와 스택의 기능을 모두 제공하여 유용하게 사용할 수 있다.

메모리 효율성ArrayDeque는 내부적으로 동적 배열을 사용하여 메모리 효율성이 좋으며, LinkedList보다 메모리 오버헤드가 적다.

---

#5 코드 리뷰

2주 차에는 팀원이 많은 양의 코딩테스트를 진행하였기에 세세한 리뷰는 어려웠다. PR에서 Issue를 연결해야 다른 내용들에 확인이 용이하기에 관련 이슈를 # 묶는 것을 선호한다. 이번에 팀원이 관련 이슈를 기재하지 않아 수정을 요청하였지만, Re-request를 하지 않고 바로 Merge를 진행하였다. 이런 경우를 막고자 PR Merge시에 규칙을 추가하였다.

블로그를 작성하는 시점에도 남아있는 Re-request 요청이다.
지금 보니 Assinees도 설정되어 있지 않아 캡처 후 설정을 해줬다….

---

 

#6 후기 및 PR 링크

코딩테스트는 풀어도 풀어도 적응이 안 되는 기분이다.
문제의 유형이 너무나 다양하고 접근 방식도 다양하다 보니 무엇이 더 좋고 효율적인 코딩일지 고민하는 것이 어렵다.
역시 많이 풀어보는 수밖에 없는 거 같다.
그래도 풀 수록 이번처럼 다양한 기술과 개념을 학습할 수 있어서 좋다.
이번에 학습한 Deque도 꼭 블로그에 작성해야겠다.
항상 블로그에 작성만 다짐하고 작성을 못 한 내용들이 많아 한 번 리스트로 정리하여서 작성을 해봐야겠다.

 

[Mobile/Full-Stack] 2week/huiwoo-jo by huiwoo-jo · Pull Request #8 · 9oormthon-univ-dmu/GFD-Mobile