프로그래머스 [2025 프로그래머스 코드챌린지 2차 예선 / 택배 상자 꺼내기](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 택배 상자 꺼내기

---

문제 링크: 문제 보기

문제 설명:

주어진 숫자 n까지 특정한 규칙에 따라 w개의 열을 가진 테이블을 채우고, 숫자 num이 있는 위치에서 연속해서 증가하는 값의 개수를 찾는 문제입니다.

---

문제 해결 코드

#include <string>
#include <vector>

using namespace std;

int arr[101][101];

int solution(int n, int w, int num) {
    int answer = 0;
    int i = 1, j = 1;
    int s = 1;
    bool check = false; // 지그재그 여부
    int ai = 0, aj = 0;

    // 테이블을 채우는 과정
    while (true) {
        if (!check) {
            arr[i][j] = s;
            if (s == num) {
                ai = i;
                aj = j;
            }
        } else {
            arr[i][w - j + 1] = s;
            if (s == num) {
                ai = i;
                aj = w - j + 1;
            }
        }
        s++;
        if (s > n) break;
        if (j == w) { // 다음 줄로 이동
            i++;
            check = !check; // 방향 전환
            j = 1;
        } else {
            j++;
        }
    }

    // 연속 증가하는 숫자 개수 세기
    while (arr[ai][aj] >= num) {
        answer++;
        ai++;
        if (ai > 100 || arr[ai][aj] == 0) break;
    }

    return answer;
}

---

코드 설명

• 핵심 알고리즘: 지그재그 패턴으로 테이블을 채운 후, 특정 숫자 num이 있는 위치에서 연속된 숫자의 개수를 찾습니다.
• 구현 세부사항:
• arr[i][j]에 숫자를 채우면서 num의 위치를 저장합니다.
• 한 줄이 끝나면 방향을 반대로 바꿔서 채우는 지그재그 패턴을 유지합니다.
• 찾은 num 위치에서 아래 방향으로 연속된 숫자의 개수를 카운트합니다.
• 시간 복잡도 분석:
• 테이블 채우기: O(n)
• 연속된 숫자 탐색: O(w)
• 총 시간 복잡도: O(n + w)

---

결과

이 코드는 지그재그 패턴으로 테이블을 채운 후, 특정 숫자가 있는 위치에서 연속된 숫자의 개수를 정확히 계산합니다. 효율적으로 문제를 해결하기 위해 두 개의 반복문을 활용합니다.

다른 접근 방식으로는 2차원 배열을 사용하지 않고, 수식으로 인덱스를 계산하여 더 빠르게 접근하는 방법도 가능합니다.