[백준 BOJ] 1380번 귀걸이 (C++/cpp)

문제 설명

https://www.acmicpc.net/problem/1380

 

 

접근 방법 - 배열을 활용한 기초 연산 문제

백준의 1380번 문제는 배열을 활용하여 비교적 쉽게 해결할 수 있는 연산 문제이다.

해당 문제는, 각 테스트 케이스에 있어 여러 여학생이 귀걸이를 압수당하고 선생님이 특정 학생의 귀걸이 중 하나를 잃어버렸다고 할 때 귀걸이를 온전히 돌려받지 못한 여학생의 이름을 찾아 출력하면 되는 문제이다.

문해력이 좋지 않아 이 해설이 맞는지도 모르겠다.

 

당시 필자는 벡터에 학생의 이름을 순차 저장하고, 배열에 압수당한 각 학생의 귀걸이 개수를 저장하게끔 설정하였다.

정답을 올바르게 찾을 수 있도록, 벡터의 인덱스와 배열의 인덱스를 연결 지으며 코드를 작성해 보았다.

(예를 들어, 0번째 인덱스의 배열에 있는 귀걸이는 0번째 인덱스의 벡터에 있는 학생의 것이게끔 하였다.)

지금 생각하면 맵으로 구현하는 게 훨씬 효율적이었을 것 같다;;

자세한 설명은 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 테스트 케이스의 연번을 카운팅 하기 위해, test 변수를 0으로 초기화하여 선언해 둔다.

 

2) 무한 반복문을 작성하여, 아래의 연산을 취한다.

- test 변수에 1을 더하여, 테스트 케이스의 연번을 갱신한다.

- 학생의 수(n)를 입력받는다.

이때 0을 입력받았다면, 이 뒤의 테스트 케이스는 없음을 의미하기 때문에 break를 통하여 반복문을 탈출하도록 한다.

- 학생의 이름을 저장할 벡터(v)를 선언하고, n의 크기만큼 문자열을 입력받는 대로 v에 요소를 추가한다.

(이때, 학생의 이름에 공백이 포함될 수 있기 때문에 반드시 이를 참고하여 문자열 입력을 받도록 한다.)

- 각 학생의 귀걸이 개수를 카운팅 할 배열(cnt)을, 모든 인덱스에 대해 0으로 초기화하면서 선언해 둔다.

- 특정 귀걸이의 주인인 학생의 순번(num)과 임의의 문자(c)를 입력받는다.

필자는 c의 값과 상관없이, v의 학생 순서와 맞물리도록 cnt[num-1]에 1을 추가하여 해당 학생의 귀걸이 개수에 1을 추가해 주었다.

- cnt의 값들을 하나씩 탐색해 보며, 귀걸이가 하나뿐인 경우의 수를 찾도록 한다.

만약 현재 탐색하는 배열의 값이 1이라면, 이 경우는 귀걸이가 한 쌍을 이루고 있지 못한다는 점을 의미한다.

따라서 이 경우엔, 현재의 test 값과 이 인덱스와 맞물리는 v의 값을 함께 정답으로 출력하도록 한다.

 

3) 위 연산이 모두 완료되었다면, 프로그램을 종료하도록 한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <vector>
#include <string>
#define endl '\n'
using namespace std;

//백준 1380번 코드
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);
    
    int test = 0;
    while (true) {
        test++;

        int n;
        cin >> n;
        if (n == 0) { break; }
        cin.ignore();

        vector<string> v;
        for (int i = 0; i < n; i++) {
            string st;
            getline(cin, st);
            v.push_back(st);
        }

        int cnt[101] = { 0 };
        for (int i = 0; i < n * 2 - 1; i++) {
            int num;
            char c;
            cin >> num >> c;

            cnt[num - 1]++;
        }

        for (int i = 0; i < n; i++) {
            if (cnt[i] == 1) {
                cout << test << " " << v[i] << endl;
            }
        }
    }
}

 

제출 결과

(2023.10.28 백준 1380번 문제 제출 결과)