플러터로 데이터 구조를 재미있게 배우는 방법

게임을 만들고 컴퓨터 과학을 배워보세요.

데이터 구조는 효율적인 소프트웨어 개발의 기초를 형성하지만, 전통적인 학습 방법은 종종 추상적이고 실제 애플리케이션과 단절된 느낌을 줍니다. 이 글은 다른 접근 방식을 취합니다. 즉, 이론과 Flutter의 실습 구현을 결합하여 학습을 매력적이고 실용적으로 만듭니다.

Google의 Applied CS with Android 에서 영감을 받은 이 Flutter용 적응은 Arrays, HashSets 및 HashMaps를 이해하는 대화형 방법을 제공합니다. 단 3~4시간 만에 이러한 기본 데이터 구조에 대한 더 깊은 이해를 얻고 의미 있는 맥락에서 이를 적용할 수 있습니다.

CS 기본을 강화하려는 초보자이든, 기술을 다듬으려는 숙련된 개발자이든, 이 가이드는 필수적인 데이터 구조를 마스터하는 효율적이고 즐거운 방법을 제공합니다. 시작해 봅시다.

이 기사의 목적:

1. 사전을 사용해 데이터(이 경우 단어)를 저장하는 방법에 대해 알아보세요.
2. 해시맵을 사용하면 애너그램인 단어 그룹을 저장할 수 있습니다.
3. 대규모 데이터 세트로 작업할 때 일부 데이터 구조가 직면하는 한계를 설명할 수 있습니다.

준비:

워크숍 활동에서 몇 가지 데이터 구조를 사용하므로 Lists , HashSets 및 HashMaps를 검토하세요. Dart에서 이러한 데이터 구조를 사용하여 자신 있게 요소의 삽입, 삭제, 액세스 및 존재 여부를 확인할 수 있어야 합니다.

이는 데이터 구조인 HashSets과 HashMap에 대한 간략한 소개입니다.

작은 시작 운동 워밍업:

HashMaps를 사용하는 예시 활동으로, 3자리 국가 코드( ISO-3166 참조)를 받아서 해당 국가의 전체 이름을 반환하는 프로그램(꼭 Flutter 앱일 필요는 없음 - 명령줄도 가능)을 만들어 보겠습니다.

예를 들어:

 Input | Output ----- | ---------------------------------------------------- GBR | United Kingdom of Great Britain and Northern Ireland IDN | Indonesia IND | India

확장으로, 입력이 3글자 이상인 경우, 국가 이름으로 간주하고, 해당 3글자 코드를 반환합니다. 입력이 유효한 코드도 아니고 국가 이름도 아닌 경우 유용한 오류 메시지를 작성합니다.

시작해 보겠습니다.

애너그램

애너그램은 다른 단어의 글자를 재배열하여 형성된 단어입니다. 예를 들어, cinema는 iceman 의 애너그램입니다.

게임의 원리는 다음과 같습니다.

1. 이 게임은 사용자에게 사전에서 단어를 제공합니다.

   
   

2. 사용자는 주어진 단어의 모든 글자와 추가 글자 하나를 포함하는 가능한 한 많은 단어를 만들려고 합니다. 다른 글자를 재정렬하지 않고 시작이나 끝에 추가 글자를 추가하는 것은 무효합니다. 예를 들어, 게임에서 'ore'라는 단어를 스타터로 선택하면 사용자는 'rose' 또는 'zero'를 추측할 수 있지만 'sore'는 추측할 수 없습니다.

   
   

3. 사용자는 포기하고 자신이 맞추지 못한 단어를 볼 수도 있습니다.

우리는 10,000개 단어의 사전을 포함하고 이 게임의 UI 부분을 처리하는 시작 코드를 제공했으며, 여러분은 모든 단어 조작을 처리하는 AnagramBlocclass를 작성해야 합니다.

코드 투어

시작 코드는 세 가지 주요 다트 클래스로 구성됩니다.

anagrams_page.dart

이것은 위에서 본 화면을 나타내는 간단한 코드입니다. 우리는 화면의 상태 관리를 위해 블록을 사용할 것입니다. 우리는 블록에 이벤트를 발생시키고 화면이 다른 게임 상태에 응답할 때 무슨 일이 일어날지 정의하여 게임을 설정하는 것으로 시작할 것입니다.

 import 'package:anagrams/anagrams/bloc/anagram_bloc.dart'; import 'package:anagrams/anagrams/domain/word.dart'; import 'package:anagrams/l10n/l10n.dart'; import 'package:bloc_presentation/bloc_presentation.dart'; import 'package:flutter/material.dart'; import 'package:flutter_bloc/flutter_bloc.dart'; class AnagramsPage extends StatelessWidget { const AnagramsPage({super.key}); @override Widget build(BuildContext context) { return BlocProvider( create: (_) => AnagramBloc() ..add( SetupAnagrams( DefaultAssetBundle.of(context), ), ), child: const AnagramsView(), ); } } class AnagramsView extends StatelessWidget { const AnagramsView({super.key}); @override Widget build(BuildContext context) { final l10n = context.l10n; return Scaffold( appBar: AppBar(title: Text(l10n.anagramAppBarTitle)), body: BlocBuilder<AnagramBloc, AnagramState>( builder: (context, state) { switch (state.status) { case AnagramGameStatus.gameError: return const Center( child: Text('An error occurred'), ); case AnagramGameStatus.loaded: return Padding( padding: const EdgeInsets.all(20), child: ListView( children: const [ _SelectedWord(), SizedBox(height: 20), _AnagramsTextField(), SizedBox(height: 10), _GuessListView(), ], ), ); case AnagramGameStatus.initial: return const Center( child: CircularProgressIndicator(), ); } }, ), floatingActionButton: const _NextWordButton(), ); } } class _SelectedWord extends StatelessWidget { const _SelectedWord(); @override Widget build(BuildContext context) { return BlocSelector<AnagramBloc, AnagramState, String>( selector: (state) => state.currentWord, builder: (context, currentWord) { return Text.rich( TextSpan( text: 'Find as many words as possible that can be ' 'formed by adding one letter to ', children: [ TextSpan( text: currentWord.toUpperCase(), style: const TextStyle(fontWeight: FontWeight.bold), ), TextSpan( text: ' (but that do not contain the substring' ' ${currentWord.toUpperCase()}).', ), ], ), ); }, ); } } class _AnagramsTextField extends StatelessWidget { const _AnagramsTextField(); @override Widget build(BuildContext context) { final controller = TextEditingController(); return TextField( controller: controller, decoration: const InputDecoration( hintText: 'Enter an anagram', border: OutlineInputBorder(), ), keyboardType: TextInputType.text, textInputAction: TextInputAction.done, onSubmitted: (value) { controller.clear(); context.read<AnagramBloc>().add(ProcessWord(value)); }, ); } } class _GuessListView extends StatelessWidget { const _GuessListView(); @override Widget build(BuildContext context) { return BlocSelector<AnagramBloc, AnagramState, List<Word>>( selector: (state) => state.guesses, builder: (context, guesses) { return Column( children: guesses.map((word) { return ListTile( minTileHeight: 0, contentPadding: EdgeInsets.zero, visualDensity: VisualDensity.compact, title: Text(word.value), leading: Icon( word.isAnagram ? Icons.check : Icons.close, color: word.isAnagram ? Colors.green : Colors.red, ), ); }).toList(), ); }, ); } } class _GameResult extends StatelessWidget { const _GameResult(this.currentWord, this.result); final List<Word> result; final String currentWord; @override Widget build(BuildContext context) { return ListView( shrinkWrap: true, children: [ const SizedBox(height: 20), Padding( padding: const EdgeInsets.symmetric( horizontal: 20, ), child: Text( 'Game Result for $currentWord', style: const TextStyle(fontSize: 20), ), ), Padding( padding: const EdgeInsets.all(20), child: SizedBox( width: double.infinity, child: DataTable( decoration: BoxDecoration( border: Border.all( color: Colors.grey.shade400, ), borderRadius: BorderRadius.circular(10), ), columns: const [ DataColumn(label: Text('Possible Anagrams')), DataColumn(label: Text('Your Guesses')), ], rows: result.map((word) { return DataRow( cells: [ DataCell(Text(word.value)), DataCell( Center( child: Icon( word.isAnagram ? Icons.check : Icons.close, color: word.isAnagram ? Colors.green : Colors.red, ), ), ), ], ); }).toList(), ), ), ), ], ); } } class _NextWordButton extends StatelessWidget { const _NextWordButton(); @override Widget build(BuildContext context) { final l10n = context.l10n; return BlocPresentationListener<AnagramBloc, AnagramPresenterEvent>( listener: (context, event) { if (event is FinishGuess) { // show a bottom sheet with the anagrams that were not guessed showModalBottomSheet<void>( context: context, useSafeArea: true, builder: (context) { return _GameResult(event.currentWord, event.result); }, ); } }, child: FloatingActionButton.extended( onPressed: () async { context.read<AnagramBloc>().add(ResetGame()); }, label: Text(l10n.nextWordButton), ), ); } }

• _SelectWord : 게임에서 애너그램을 형성하기 위해 선택된 단어를 표시합니다.

• _AnagramsTextField : 단어를 받아서 사용자가 입력한 단어를 처리하기 위한 이벤트를 발생시킵니다.

• _GuessListView : 사용자가 입력한 추측을 보여주고, 정답인지 틀렸는지 여부를 보여줍니다.

• _NextWordButton : 게임을 재설정하고 사용자에게 현재 단어의 모든 애너그램과 사용자가 추측한 애너그램을 표시합니다.

anagram_states.dart

 enum AnagramGameStatus { initial, loaded, gameError } const minNumAnagrams = 5; const defaultWordLength = 3; const maxDefaultWordLength = 7; @immutable final class AnagramState extends Equatable { factory AnagramState({ AnagramGameStatus status = AnagramGameStatus.initial, List<String> words = const [], String currentWord = '', List<String> anagrams = const [], List<Word> guesses = const [], HashSet<String>? wordSet, HashMap<String, List<String>>? anagramMap, HashMap<int, List<String>>? sizeToWords, int wordLength = defaultWordLength, }) { return AnagramState._( status: status, words: words, currentWord: currentWord, anagrams: anagrams, guesses: guesses, wordSet: wordSet ?? HashSet<String>(), anagramMap: anagramMap ?? HashMap<String, List<String>>(), sizeToWords: sizeToWords ?? HashMap<int, List<String>>(), wordLength: wordLength, ); } const AnagramState._({ required this.status, required this.words, required this.currentWord, required this.anagrams, required this.guesses, required this.wordSet, required this.anagramMap, required this.sizeToWords, this.wordLength = defaultWordLength, }); // The current status of the game final AnagramGameStatus status; // All the words in the game final List<String> words; // Currently chosen word of the game to form anagrams final String currentWord; // All the anagrams for the current word final List<String> anagrams; // All the guesses user has made final List<Word> guesses; // A set of all the words in the game final HashSet<String> wordSet; // A map of anagrams for each word final HashMap<String, List<String>> anagramMap; // Stores the words in increasing order of their length final HashMap<int, List<String>> sizeToWords; final int wordLength; AnagramState copyWith({ AnagramGameStatus? status, List<String>? words, String? currentWord, List<String>? anagrams, List<Word>? guesses, HashSet<String>? wordSet, HashMap<String, List<String>>? anagramMap, HashMap<int, List<String>>? sizeToWords, int? wordLength, }) { return AnagramState( status: status ?? this.status, words: words ?? this.words, currentWord: currentWord ?? this.currentWord, anagrams: anagrams ?? this.anagrams, guesses: guesses ?? this.guesses, wordSet: wordSet ?? this.wordSet, anagramMap: anagramMap ?? this.anagramMap, sizeToWords: sizeToWords ?? this.sizeToWords, wordLength: wordLength ?? this.wordLength, ); } @override List<Object?> get props => [ status, words, currentWord, anagrams, guesses, wordSet, anagramMap, sizeToWords, wordLength, ]; }

AnagramState는 게임을 실행하는 데 필요한 모든 상태 변수를 보관합니다.

• status : 게임이 로드 중인지(초기), 로드되었는지 또는 오류가 발생했는지 여부를 나타냅니다.
• words : word.txt 파일에서 로드된 모든 단어를 나열합니다.
• anagrams : 선택한 단어의 모든 anagrams를 담고 있습니다.
• currentword : 단어 목록에서 선택한 단어와 아나그램을 형성할 단어입니다.
• guesses : 사용자가 입력한 모든 선택 사항과 그 선택 사항이 맞는지 틀렸는지 여부입니다.

나머지 자세한 내용은 이 기사의 뒷부분에서 다루겠습니다.

anagram_bloc.dart

 import 'dart:async'; import 'dart:collection'; import 'dart:convert'; import 'package:anagrams/anagrams/domain/word.dart'; import 'package:bloc_presentation/bloc_presentation.dart'; import 'package:equatable/equatable.dart'; import 'package:flutter/widgets.dart'; import 'package:flutter_bloc/flutter_bloc.dart'; part 'anagram_events.dart'; part 'anagram_states.dart'; class AnagramBloc extends Bloc<AnagramEvent, AnagramState> with BlocPresentationMixin<AnagramState, AnagramPresenterEvent> { AnagramBloc() : super(AnagramState()) { on<SetupAnagrams>(_onSetupAnagrams); on<ProcessWord>(_onProcessWord); on<ResetGame>(_onResetGame); } Future<void> _onSetupAnagrams( SetupAnagrams event, Emitter<AnagramState> emit, ) async { try { // this should not be done here, // but for the sake of simplicity, we will do it here final wordsFile = await event.defaultAssetBundle.loadString('assets/words.txt'); // read each line in the file final words = const LineSplitter().convert(wordsFile); // change the state of the game emit( state.copyWith( status: AnagramGameStatus.loaded, words: words, ), ); // reset the game _onRestartGame(emit); } catch (e) { emit( state.copyWith( status: AnagramGameStatus.gameError, ), ); } } Future<void> _onProcessWord( ProcessWord event, Emitter<AnagramState> emit, ) async { try { final word = event.word.trim().toLowerCase(); if (word.isEmpty) { return; } if (_isGoodWord(word) && state.anagrams.contains(word)) { // remove the word from the list of anagrams // add the word to the list of guesses emit( state.copyWith( anagrams: state.anagrams..remove(word), guesses: [...state.guesses, Word(word, isAnagram: true)], ), ); // if there are no more anagrams, the game is over // call _onResetGame to reset the game if (state.anagrams.isEmpty) { add(ResetGame()); } } else { emit( state.copyWith( guesses: [...state.guesses, Word(word)], ), ); } } catch (e) { // show an error message } } FutureOr<void> _onResetGame(ResetGame event, Emitter<AnagramState> emit) { _onGameFinished(); _onRestartGame(emit); } void _onRestartGame(Emitter<AnagramState> emit) { final starterWord = _pickGoodStarterWord(emit); emit( state.copyWith( status: AnagramGameStatus.loaded, currentWord: starterWord, anagrams: _getAnagrams(starterWord), guesses: [], ), ); } void _onGameFinished() { emitPresentation(FinishGuess(_result, state.currentWord)); } List<Word> get _result { // All the anagrams that were not guessed final notGuessedAnagrams = state.anagrams.map(Word.new).toList(); // All the guesses that were made final guesses = state.guesses.where((word) => word.isAnagram).toList(); // return the list of anagrams that were not guessed return [...guesses, ...notGuessedAnagrams]; } /// create a function to find all the anagrams of the target word List<String> _getAnagrams(String targetWord) { // find all the anagrams of the target word final anagrams = <String>[]; // return the list of anagrams return anagrams; } // ignore: unused_element List<String> _getAnagramsWithOneMoreLetter(String targetWord) { final anagrams = HashSet<String>(); // return the list of anagrams return anagrams.toList(); } /// Picks a good starter word for the game. String _pickGoodStarterWord(Emitter<AnagramState> emit) { const word = 'skate'; return word; } /// Checks if the word is a good word. bool _isGoodWord(String word) { return true; } }

• onSetupAnagrams : 파일을 읽고, 단어를 분할하고, 목록에 추가합니다. 또한 현재 단어를 찾고, 선택한 단어의 애너그램을 찾고, 상태를 업데이트합니다.

• onProcessWord : 사용자가 추측을 입력하고 상태를 업데이트할 때 호출되는 핸들러입니다.
• onReset : 다음 단어 버튼을 클릭하면 호출되며 게임을 재설정합니다.
• isGoodWord : 주어진 단어가 사전에 있으며 기본 단어의 시작이나 끝에 문자를 추가하여 형성되지 않았음을 확인합니다.
• getAnagrams : 주어진 단어의 가능한 모든 애너그램 목록을 생성합니다.
• getAnagramsWithOneMoreLetter : 주어진 단어에 글자 하나를 더하면 만들어질 수 있는 모든 단어의 목록을 만듭니다.
• pickGoodStarterWord : 원하는 개수 이상의 애너그램이 있는 단어를 무작위로 선택합니다.

마일스톤 1: 필수 사항

첫 번째 마일스톤은 매우 간단한 작동 프로그램을 만드는 데 중점을 둡니다. 마일스톤 2와 3에서 구축될 기초를 구현하게 됩니다.

우리는 anagram_bloc.dart 에 관해 작업할 겁니다.

getAnagrams

문자열을 받아서 입력에서 해당 문자열의 모든 애너그램을 찾는 getAnagrams 구현합니다. 지금으로서는 간단한 전략입니다. words List의 각 문자열을 입력 단어와 비교하여 애너그램인지 확인합니다. 하지만 어떻게 해야 할까요?

두 문자열이 서로의 애너그램인지 확인하기 위해 사용할 수 있는 다양한 전략이 있습니다(예: 각 문자의 발생 횟수를 세는 것). 하지만 우리의 목적에서는 String 받아서 같은 문자가 알파벳순으로 나열된(예: "post" -> "post") 다른 String 반환하는 도우미 함수( sortLetters 라고 함)를 만들 것입니다.

두 문자열이 애너그램인지 아닌지를 판별하는 것은 간단한 문제인데, 속도를 위해 두 문자열의 길이가 같고, 두 문자열의 글자를 정렬한 결과가 같은지 확인하면 됩니다.

wordSet과 anagramMap

불행히도, 간단한 전략은 우리가 이 게임의 나머지 부분을 구현하기에는 너무 느릴 것입니다. 따라서 onSetupAnagrams 다시 살펴보고 우리의 목적에 편리한 방식으로 단어를 저장하는 데이터 구조를 찾아야 합니다. 우리는 ( words 외에도) 두 개의 새로운 데이터 구조를 만들 것입니다.

• 단어가 유효한지 여부를 빠르게(O(1)) 검증할 수 있는 HashSet ( wordSet 이라고 함)

• 애너그램을 그룹화할 수 있는 HashMap ( anagramMap 이라고 함). 문자열의 sortLetters 버전을 키로 사용하고 해당 키에 해당하는 단어의 목록을 값으로 저장하여 이를 수행합니다. 예를 들어, 다음과 같은 형식의 항목이 있을 수 있습니다. key: "opst" value: ["post", "spot", "pots", "tops", ...].

입력 단어를 처리할 때 각 단어에 대해 sortLetters 호출한 다음 anagramMap 해당 키에 대한 항목이 이미 있는지 확인합니다. 항목이 있으면 현재 단어를 해당 키의 List 에 추가합니다. 그렇지 않으면 새 단어를 만들고 단어를 추가한 다음 해당 키와 함께 HashMap 에 저장합니다.

이것을 완료하면 마일스톤 1의 끝에 도달했습니다! 이제 두 번째 마일스톤으로 넘어갈 준비가 되었는데, 여기서 프로그램에 더 많은 복잡성을 추가할 것입니다.

마일스톤 1에 대한 솔루션

마일스톤 2: 품질 추가

마일스톤 2는 선택한 단어가 애너그램 게임에 적합한지 확인하는 것입니다. 이전 마일스톤과 달리 이 마일스톤은 세 섹션으로 나뉩니다.

isGoodWord

다음 작업은 다음을 확인하는 isGoodWord 구현하는 것입니다.

• 제공된 단어는 유효한 사전 단어(즉, wordSet 에 있는 단어)이고
• 해당 단어에는 기본 단어가 하위 문자열로 포함되어 있지 않습니다.

단어가 유효한 사전 단어인지 확인하려면 wordSet 보고 해당 단어가 포함되어 있는지 확인하면 됩니다. 단어가 기본 단어를 하위 문자열로 포함하지 않는지 확인하는 것은 과제로 남습니다!

getAnagramsWithOneMoreLetter

마지막으로, 문자열을 받아서 해당 단어에 글자 하나를 더해서 만들 수 있는 모든 애너그램을 찾는 getAnagramsWithOneMoreLetter 함수를 구현합니다.

반환 값으로 새 List 인스턴스화한 다음, 주어진 단어와 알파벳의 각 문자를 하나씩 anagramMap 의 항목과 비교합니다.

또한 onRestartGame 업데이트하여 getAnagrams 대신 getAnagramsWithOneMoreLetter 호출하도록 합니다.

pickGoodStarterWord

게임이 잘 작동한다면 pickGoodStarterWord 구현하여 게임을 더 흥미롭게 만드세요. 단어 목록에서 임의의 시작점을 선택하고 배열의 각 단어를 확인하여 최소 minNumAnagrams 가진 단어를 찾으세요. 필요한 경우 배열 시작 부분으로 래핑을 처리하세요.

3분의 2가 끝났습니다! 완료하기 전에 하나의 이정표와 연장만 남았습니다.

마일스톤 2에 대한 솔루션

마일스톤 3: 리팩토링

이 시점에서 게임은 기능적이지만 긴 기본 단어로 시작하면 플레이하기가 꽤 어려울 수 있습니다. 이를 피하기 위해 onSetupGame 리팩토링하여 점점 길어지는 단어를 제공합시다.

이 리팩터링은 onSetupGame 에서 시작하는데, 여기서 word 목록을 채우는 것 외에도 각 단어를 HashMap ( sizeToWords 라고 부르자)에 저장해야 하며, 이는 단어 길이를 해당 길이의 모든 단어 List 으로 매핑합니다. 즉, 예를 들어 sizeToWords.get(4) 호출하여 사전의 모든 4글자 단어를 가져올 수 있어야 합니다.

pickGoodStarterWord 에서 검색 범위를 wordLength 길이의 단어로 제한하고, 완료되면 wordLength 증가시킵니다(이미 axWordLength 에 도달하지 않은 경우). 그러면 다음 호출 시 더 큰 단어가 반환됩니다.

마일스톤 3에 대한 솔루션

확장

이 활동(모든 미래 활동과 마찬가지로)에는 몇 가지 선택적 확장이 포함되어 있습니다. 시간이 허락한다면 아래 목록에서 하나 이상의 확장을 시도하거나 직접 고안한 확장을 시도해 보세요.

• 두 글자 모드: 사용자가 두 글자를 추가하여 애너그램을 형성할 수 있도록 전환합니다.

• 가능한 시작 단어 풀에서 충분한 애너그램이 없는 단어를 제거하여 단어 선택을 최적화합니다. 이러한 단어는 다른 단어에서 여전히 애너그램으로 사용될 수 있으므로 wordSet 에 남아 있어야 합니다.

• 두 단어 모드: 사용자가 두 단어에 한 글자를 추가하여 두 개의 새로운 유효 단어를 형성할 수 있도록 합니다.

끝까지 읽어주셔서 축하드립니다! Flutter에서 List, HashSet, HashMap이 모든 최적화된 애플리케이션에서와 마찬가지로 효율적인 데이터 처리에 어떻게 도움이 되는지 알아보았습니다. 이러한 구조를 이해하면 확장 가능하고 성능이 뛰어난 코드를 작성하는 데 유리합니다. 계속해서 자신에게 칭찬을 해주세요! 이제 이 지식을 실천에 옮기고 계속해서 놀라운 것을 만들어보세요!