백준 1453번 [피시방 알바](C++) -yes6686- 티스토리

백준 문제 풀이: 1453 (피시방 알바)

---

문제 링크: https://www.acmicpc.net/problem/1453

문제 설명:

피시방에 손님이 방문하여 자리를 요청합니다. 각 손님은 고유 번호를 가지고 있으며, 특정 자리를 지정합니다. 자리가 비어 있으면 사용 가능하지만, 이미 다른 손님이 사용 중이라면 해당 손님은 거절됩니다.
주어진 손님들의 자리 요청 리스트를 바탕으로 거절된 손님 수를 출력하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int visited[101]; // 자리 번호는 1~100 사이로 제한됨

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 손님의 수
    cin >> n;
    int cnt = 0; // 거절된 손님의 수

    for (int i = 0; i < n; i++) {
        int x; // 손님이 요청한 자리 번호
        cin >> x;

        // 이미 사용 중인 자리인 경우
        if (visited[x] == 1) {
            cnt++; // 거절된 손님 수 증가
        }
        // 비어 있는 자리인 경우
        else {
            visited[x] = 1; // 자리 사용 표시
        }
    }

    cout << cnt << '\n'; // 거절된 손님 수 출력
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 배열을 사용하여 자리의 사용 여부를 확인하는 방식으로, 각 요청에 대해 O(1)의 시간 복잡도로 처리합니다.
• 구현 세부사항:
  • visited[101] 배열: 자리 번호가 1~100이므로 101 크기의 배열을 선언하여 자리 사용 여부를 저장합니다.
  • 자리 요청이 들어올 때, 해당 자리 번호를 배열에서 확인하고 이미 사용 중이면 거절(cnt++), 비어 있으면 사용 표시(visited[x] = 1)를 합니다.
• 시간 복잡도 분석:
  • 입력 크기가 n일 때, 요청 처리 루프는 O(n)입니다.
  • 각 요청에 대한 배열 접근은 O(1)이므로 전체 시간 복잡도는 O(n)입니다.

---

결과

주어진 자리 요청 리스트에 대해 거절된 손님의 수를 정확히 계산합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!