백준 11723 - 집합 (C++)

 

명령어가 들어왔을 때, 어떻게 처리할 것인지를 구현하는 문제이다.

집합에 있는 값을 기반으로 명령어를 처리하는 코드를 구현하면 된다.

 

 

문제 풀이

---

문제 구현은 간단하다. 그냥 명령어를 그대로 구현하면 된다.

다만, 명령어가 들어올 때 마다 자료구조의 값을 선형으로 탐색하게 되면 아마 시간초과가 뜨거나, 뜨지 않는다고 해도 어마어마한 시간이 걸릴 것이다.

 

그렇기 때문에, 본인은 배열을 이용하여 구현하였다.

입력받는 값의 범위가 1과 20 사이라는 매우 좁은 범위이기 때문에 배열을 직접 만들어서 사용하여도 무리가 없을 것 같았다.

 

먼저 사진을 보자.

 

이렇게, 1~20까지의 배열을 만든 뒤, 해당 원소를 모두 false로 설정해주자.

이 배열에서 false가 의미하는 것은 해당 숫자가 집합에 없다는 것이며, true라면 해당 숫자가 집합에 있다는 의미이다.

 

이렇게 만든 이유는 무엇이냐면, 자료구조에 1~20의 숫자를 직접 삽입하게 되면 해당 숫자를 찾기 위해 선형탐색을 해야한다. 최소는 1번이지만 최대 20번까지의 반복문을 돌아야 한다. 중간에 값을 삽입하거나 삭제하게 되면 추가적인 연산을 해야할 수도 있다.

 

하지만, 이처럼 T,F로 숫자를 관리하게 되면 인덱스 접근만으로 해당 숫자가 있는지 없는지를 판별할 수 있다.

O(n) 이었던 탐색시간이 O(1)이 된 것이다.

 

참고로, 위의 배열을 만들 때 편하게 인덱스에 접근하기 위해 배열은 20 + 1개의 원소가 들어가는 크기로 resize()하였다.

(인덱스 0은 사용하지 않고, 1~20만 사용)

 

이제 명령어를 구현해보자.

 

1. add

해당 인덱스의 값이 false라면 true로 바꿔주면 된다.

 

2.remove

해당 인덱스의 값이 true라면 false로 바꿔주면 된다.

 

3.check

해당 인덱스의 값이 true라면 1을 출력하고, false라면 0을 출력한다.

 

4.toggle

해당 인덱스의 값이 true라면 false로 false라면 true로 바꿔준다.

 

5.all

모든 원소를 true로 바꿔준다. 

 

6.empty

모든 원소를 false로 바꿔준다.

 

 

풀이 코드

---

int NumOfCommand = 0;
std::cin >> NumOfCommand;

std::vector<bool> isExist(21, false);

 

먼저 입력을 받아준 뒤, 배열을 선언하여 모두 false로 초기화 해준다.

(인덱스 접근을 편하게 하기 위해, 21의 사이즈로 resize함)

 

std::string Command = "";
int TargetNumber = 0;

std::cin >> Command;
if (Command != "all" && Command != "empty")
{
	std::cin >> TargetNumber;
}

 

이후, 반복문을 돌며 명령어를 입력받는다.

all과 empty의 경우 명령어는 입력받지만, 추가적인 숫자는 입력받지 않는다.

입력이 꼬이지 않도록 예외처리를 해주자.

 

if (Command == "add")
{
    if (isExist[TargetNumber] == false)
    {
    	isExist[TargetNumber] = true;
    }
}
else if (Command == "remove")
{
    if (isExist[TargetNumber] == true)
    {
    	isExist[TargetNumber] = false;
    }
}
else if (Command == "check")
{
    if (isExist[TargetNumber] == true)
    {
    	std::cout << 1;
    }
    else
    {
    	std::cout << 0;
    }

    std::cout << "\n";
}
else if (Command == "toggle")
{
    isExist[TargetNumber] = !isExist[TargetNumber];
}
else if (Command == "all")
{
    for (int j = 1; j <= 20; j++)
    {
    	isExist[j] = true;
    }
}
else if (Command == "empty")
{
    for (int j = 1; j <= 20; j++)
    {
    	isExist[j] = false;
    }
}

 

위에서 설명한 것과 같이 구현하면 된다.

구현 자체가 매우 간단하다.

 

위에서 설명한 것 그대로 구현하면 된다.