Doxygen - Could Not Find Flex (Missing: Flex_Executable)

I know there are very similar worded questions on here, but I could not find an answer to my question there, so here we go:
I'm trying to see which of my C++ methods are called by others so I found Doxygen after googling.
On their page the installation seems pretty straightforward:

If you have the necessary build tools installed (i.e. g++, python, cmake, flex, bison), you should do the following to get the initial copy of the repository:

git clone
cd doxygen
mkdir build
cd build
cmake -G "Unix Makefiles" ..
make

Until cmake -G "Unix Makefiles" .. everything goes well, then on that command following error occurs:

test@test-VirtualBox:~/doxygen/build$ cmake -G "Unix Makefiles" ..
CMake Error at /usr/share/cmake-3.5/Modules/FindPackageHandleStandardArgs.cmake:148 (message):
  Could NOT find FLEX (missing: FLEX_EXECUTABLE)
Call Stack (most recent call first):
  /usr/share/cmake-3.5/Modules/FindPackageHandleStandardArgs.cmake:388 (_FPHSA_FAILURE_MESSAGE)
  /usr/share/cmake-3.5/Modules/FindFLEX.cmake:230 (FIND_PACKAGE_HANDLE_STANDARD_ARGS)
  CMakeLists.txt:84 (find_package)

I thought: No big deal, why should anything work out of the box...seems I have to install flex.
So I do:
sudo apt-get update
sudo apt-get install flex
sudo apt autoremove (because after installation the command line recommended me to do this)

Now it seems to me that flex has been installed, I try cmake -G "Unix Makefiles" .. again...same error. I close the command line, start it up again, try it again - same error...
So now I'm slowly gettin' pissed and turn to Stack Overflow for help :D
What am I doing wrong???

And because I saw someone asking this in the other question's comment, here's the output of flex:

test@test-VirtualBox:~/doxygen/build$ flex
The program 'flex' can be found in the following packages:
 * flex
 * flex-old
Try: sudo apt install <selected package>