오늘 학습 진행 내용
알고리즘 특강 - 3
차주부터 알고리즘 코드카타
9시부터 10시까지 프로그래머스 사이트 기반으로 문제들 풀어보는 시간
진도는 본인이 체크
다음주부터 문제 해석하는 연습
1) 뼈대를 생각(solution이 되는)
2) 뼈대를 직접 작성
3) 작성한 뼈대에 로직을 하나씩 작성(로직 한번에 생각하는 행위는 지양)
4)작은 로직 하나씩 코드 안에 붙여보기
5)연습장, 필기구 활용해서 제대로 돌아가는지 검산하기(테스트 케이스)
6) 로직이 정상적인 것 같으면 다음 로직 생각해보기
7) 로직 붙이는 작업을 목표가 달성될 때까지 반복
코딩테스트에서 반드시 STL 컨테이너에대해서 알고 있어야 됨
자료 구조 선택 가이드를 참고해서
해당 문제에서 요구하는 상황에서 필요한 STL이 어떤 것일지 파악하는 것이 중요
예제 문제
문자열 내에서 각 문자가 몇 번 등장하는시 세는 프로그램을 작성하세요.
예를 들어, 문자열 'spartan'이 주어지면, 결과는 다음과 같아야 합니다: { s: 1, p: 1, a: 2, r: 1, t: 1, n: 1 }”
문자의 출연 빈도 세므로 순서 중요 X
문자(key), 빈도(Value) 형태의 조회가 필요
같은 문자에 대해 여러 개의 카운트 값 필요 X
자료구조 선택 가이드 상 해당 요건 충족하는 unordered_map을 사용
unordered_map<char, int> charCount;
문자열 순회 -> 반복문
등장 횟수 카운트 -> 조건문으로 카운트(find 사용)
if(charCount.find(currentChar) != charCount.end()) //맵 내의 키에서 발견될 시
// find 결과가 end()와 다르면 키를 찾았다는 것
최종 결과 코드
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
// 어떤걸 리턴해야되는지 알았으니 리턴 타입 기입!
unordered_map<char, int> countCharacters(string str) {
unordered_map<char, int> charCount;
for(int i = 0; i < str.length(); i++) {
char currentChar = str[i];
if(charCount.find(currentChar) != charCount.end()) {
charCount[currentChar]++;
} else {
charCount[currentChar] = 1;
}
}
return charCount;
}
int main() {
string input = "spartan";
auto result = countCharacters(input);
for(const auto& pair : result) {
cout << pair.first << ": " << pair.second << endl;
}
}연습문제
주어진 단어의 각 문자를 하나씩 뒤로 이동하여 만들어진 모든 회전된 단어 출력
예를 들어, 입력을 "abc"로 받으면 출력은 ["abc","bca","cab"]로 출력
작성 코드
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<string> solution(string str){
vector<string> answer;
string rotatewords = str;
answer.push_back(str);
for(int i = 0; i < str.length()-1; i++){
string temp = "";
for(int j = 1; j < rotatewords.length(); j++){
temp += rotatewords[j];
}
temp += rotatewords[0];
answer.push_back(temp);
rotatewords = temp;
}
return answer;
}
int main(){
string input = "abc";
vector<string> answer = solution(input);
for(auto& ele : answer){
cout<<ele<<endl;
}
}정답 해설
문자열 일부 뽑아내기 위해서 substr 문자 복사하는 함수 활용
word.substr(1) + word[0] // "bc" + "a"
word.substr(2) + word[0 ~ 1] // "c" + "ab"
word.substr(2) + word.substr(0, 2) // (word[0~1] 이란 표현이 없으므로 substr 매뉴얼의 form, to 명시 형태로 수정)
word.substr(1) + word.substr(0, 1) //word.substr(1) + word[0] // "bc" + "a" 이것도 공통된 형태로 반복문 처리 가능하게 수정#include <iostream>
#include <string>
#include <vector>
// using namespace std;를 생략하면 namespace를 붙여야 합니다!
// 아래처럼 vector -> std::vector로 vector가 어느 namespace에 있는지 지정하는거에요!
// const 참조자 형태로 매개변수를 넘기는 이유는
// 1. word 수정 방지 + 2. 불필요한 복사를 방지 하기 위함인데 저번 시간에 배우셨죠!
std::vector<std::string> rotateWord(const std::string& word) {
std::vector<std::string> rotations;
for (size_t i = 0; i < word.size(); i++) {
std::string rotated = word.substr(i) + word.substr(0, i);
rotations.push_back(rotated);
}
return rotations;
}
int main() {
std::string input = "abc";
auto result = rotateWord(input);
std::cout << "[";
for (size_t i = 0; i < result.size(); i++) {
std::cout << "\"" << result[i] << "\"";
if (i < result.size() - 1) {
std::cout << ", ";
}
}
std::cout << "]\n";
}프로그래머스 배열만들기.5
문제 설명
문자열 배열 intStrs와 정수 k, s, l가 주어집니다. intStrs의 원소는 숫자로 이루어져 있습니다.
배열 intStrs의 각 원소마다 s번 인덱스에서 시작하는 길이 l짜리 부분 문자열을 잘라내 정수로 변환합니다. 이때 변환한 정수값이 k보다 큰 값들을 담은 배열을 return 하는 solution 함수를 완성해 주세요.
제한사항
0 ≤ s < 100
1 ≤ l ≤ 8
10l - 1 ≤ k < 10l
1 ≤ intStrs의 길이 ≤ 10,000
s + l ≤ intStrs의 원소의 길이 ≤ 120
입출력 예
| intStrs | k | s | l | result |
|---|---|---|---|---|
| ["0123456789", "9876543210", "9999999999999"] | 50000 | 5 | 5 | [56789, 99999] |
통과 코드
#include <string>
#include <vector>
#include <cmath>
using namespace std;
vector<int> solution(vector<string> intStrs, int k, int s, int l) {
vector<int> answer;
for(auto& num_string : intStrs){
string nums = "";
for(int i=s; i<s+l; i++){
nums+= num_string[i];
}
int real_num = stoi(nums);
if(real_num>k){
answer.push_back(real_num);
}
}
return answer;
}다른 사람 풀이
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<string> intStrs, int k, int s, int l) {
vector<int> answer;
for(int i=0;i<intStrs.size();i++){
string a = intStrs[i].substr(s,l);
int b=stoi(a);
if(b>k) answer.push_back(b);
}
return answer;
}프로그래머스 부분 문자열 이어 붙여 문자열 만들기
문제 설명
길이가 같은 문자열 배열 my_strings와 이차원 정수 배열 parts가 매개변수로 주어집니다. parts[i]는 [s, e] 형태로, my_string[i]의 인덱스 s부터 인덱스 e까지의 부분 문자열을 의미합니다. 각 my_strings의 원소의 parts에 해당하는 부분 문자열을 순서대로 이어 붙인 문자열을 return 하는 solution 함수를 작성해 주세요.
제한사항
1 ≤ my_strings의 길이 = parts의 길이 ≤ 100
1 ≤ my_strings의 원소의 길이 ≤ 100
parts[i]를 [s, e]라 할 때, 다음을 만족합니다.
0 ≤ s ≤ e < my_strings[i]의 길이
입출력 예
| my_strings | parts | result |
|---|---|---|
| ["progressive", "hamburger", "hammer", "ahocorasick"] | [[0, 4], [1, 2], [3, 5], [7, 7]] | "programmers" |
통과 코드
#include <string>
#include <vector>
#include <iostream>
using namespace std;
string solution(vector<string> my_strings, vector<vector<int>> parts) {
string answer = "";
for(int i=0; i<my_strings.size(); i++){
int s = parts[i][0];
int e = parts[i][1];
for(int j=s; j<=e; j++){
answer+=my_strings[i][j];
}
}
return answer;
}
다른 사람 풀이
#include <string>
#include <vector>
using namespace std;
string solution(vector<string> my_strings, vector<vector<int>> parts) {
string answer = "";
for (int i=0; i<parts.size(); ++i) {
auto& p = parts[i];
answer += my_strings[i].substr(p[0], p[1]-p[0]+1);
}
return answer;
}[3번 과제] 인벤토리 시스템 구현
실습 코드(구현 중)
어제 구현했던 Inventory 관련해서 사용할 Item 객체, Weapon 객체, Potion 객체 구현해서 main.cpp에 테스트 케이스 및 동작 테스트 중
Item.h
#pragma once
#include <string>
using namespace std;
class Item {
public:
Item();
Item(string name, int price);
void PrintInfo() const;
string GetName() const;
int GetPrice() const;
private:
string name_;
int price_;
};Item.cpp
#include "Item.h"
#include <string>
#include <iostream>
using namespace std;
Item::Item() : name_(""), price_(0) {} // 기본 생성자
Item::Item(string name="", int price=0) : name_(name), price_(price) {}
void Item::PrintInfo() const {
cout << "[이름: " << name_ << ", 가격: " << price_ << "G]" << endl;
}
int Item::GetPrice() const {
return price_;
}
string Item::GetName() const {
return name_;
}Weapon.h
#pragma once
#include <string>
using namespace std;
class Weapon
{
public:
Weapon();
Weapon(const string& name, int attack = 0, int price = 0);
void PrintInfo() const;
string GetName() const;
int GetPrice() const;
private:
string name_;
int price_;
int attack_;
};Weapon.cpp
#include "Weapon.h"
#include <iostream>
using namespace std;
Weapon::Weapon() : name_(""), attack_(0), price_(0) {}
Weapon::Weapon(const string& name, int attack, int price)
: name_(name), attack_(attack), price_(price) {
}
int Weapon::GetPrice() const {
return price_;
}
string Weapon::GetName() const {
return name_;
}
void Weapon::PrintInfo() const {
cout << "[이름: " << name_ << ", 공격력: " << attack_ << ", 가격: " << price_ << "G]" << endl;
}Potion.h
#pragma once
#include <string>
using namespace std;
class Potion {
public:
Potion();
Potion(const string& name, const string& category, int heal = 0, int price = 0);
void PrintInfo() const;
string GetName() const;
int GetPrice() const;
private:
string name_;
string category_;
int price_;
int heal_;
};Potion.cpp
#include "Potion.h"
#include <iostream>
using namespace std;
Potion::Potion() : name_(""),category_(""), heal_(0), price_(0) {}
Potion::Potion(const string& name, const string& category, int heal, int price)
: name_(name), category_(category), price_(price), heal_(heal) {
}
int Potion::GetPrice() const {
return price_;
}
string Potion::GetName() const {
return name_;
}
void Potion::PrintInfo() const {
cout << "[이름: " << name_ << ", 종류: " << category_ <<", 회복량"<<heal_ << ", 가격: " << price_ << "G]" << endl;
}main.cpp
#include <iostream>
#include <string>
#include <vector>
#include "Inventory.h"
#include "Item.h"
#include "Weapon.h"
#include "Potion.h"
using namespace std;
// ====== 메뉴 출력 ======
void printInventoryMenu() {
cout << "\n";
cout << "+------------------------------------+\n";
cout << "| 일반 인벤토리 관리 시스템 |\n";
cout << "+------------------------------------+\n";
cout << "| 1. 인벤토리 목록 조회 |\n";
cout << "| 2. 인벤토리 가격 오름차순 정렬 |\n";
cout << "| 3. 인벤토리 아이템 추가 |\n";
cout << "| 4. 마지막 추가 아이템 삭제 |\n";
cout << "| 5. 무기 인벤토리 관리 시스템 |\n";
cout << "| 6. 포션 인벤토리 관리 시스템 |\n";
cout << "| 0. 나가기 |\n";
cout << "+------------------------------------+\n";
cout << " 선택 : ";
}
void printWeaponInventoryMenu() {
cout << "\n";
cout << "+------------------------------------+\n";
cout << "| 무기 인벤토리 관리 시스템 |\n";
cout << "+------------------------------------+\n";
cout << "| 1. 인벤토리 목록 조회 |\n";
cout << "| 2. 인벤토리 가격 오름차순 정렬 |\n";
cout << "| 3. 인벤토리 아이템 추가 |\n";
cout << "| 4. 마지막 추가 아이템 삭제 |\n";
cout << "| 0. 나가기 |\n";
cout << "+------------------------------------+\n";
cout << " 선택 : ";
}
void printPotionInventoryMenu() {
cout << "\n";
cout << "+------------------------------------+\n";
cout << "| 포션 인벤토리 관리 시스템 |\n";
cout << "+------------------------------------+\n";
cout << "| 1. 인벤토리 목록 조회 |\n";
cout << "| 2. 인벤토리 가격 오름차순 정렬 |\n";
cout << "| 3. 인벤토리 아이템 추가 |\n";
cout << "| 4. 마지막 추가 아이템 삭제 |\n";
cout << "| 0. 나가기 |\n";
cout << "+------------------------------------+\n";
cout << " 선택 : ";
}
// ====== 입력 유틸 ======
// 숫자 입력 (기본 검증)
int readInt(const string& prompt) {
int x;
while (true) {
cout << prompt;
if (cin >> x) {
cin.ignore(10000, '\n'); // 엔터 제거
return x;
}
cin.clear();
cin.ignore(10000, '\n');
cout << "숫자만 입력하세요.\n";
}
}
// 문자열 입력 (띄어쓰기 허용)
string readString(const string& prompt) {
string s;
while (true) {
cout << prompt;
getline(cin, s);
if (!s.empty()) return s;
cout << "빈 값은 입력할 수 없습니다.\n";
}
}
// ====== 서브 메뉴 루프들 ======
void runWeaponMenu(Inventory<Weapon>* weaponInv) {
while (true) {
printWeaponInventoryMenu();
int choice = readInt("");
if (choice == 0) return;
switch (choice) {
case 1:
cout << "현재 무기 인벤토리 (" << weaponInv->GetSize() << "/" << weaponInv->GetCapacity() << ")\n";
weaponInv->printAllItems();
break;
case 2:
weaponInv->SortItems();
cout << "정렬 완료!\n";
weaponInv->printAllItems();
break;
case 3: {
string name = readString("무기 이름: ");
int price = readInt("무기 가격: ");
int atk = readInt("공격력(예시): ");
Weapon w(name, price, atk);
weaponInv->AddItem(w);
cout << "현재 무기 인벤토리 용량: " << weaponInv->GetSize() << "/" << weaponInv->GetCapacity() << "\n";
break;
}
case 4:
weaponInv->RemoveLastItem();
cout << "현재 무기 인벤토리 용량: " << weaponInv->GetSize() << "/" << weaponInv->GetCapacity() << "\n";
break;
default:
cout << "잘못된 입력입니다.\n";
break;
}
}
}
void runPotionMenu(Inventory<Potion>* potionInv) {
while (true) {
printPotionInventoryMenu();
int choice = readInt("");
if (choice == 0) return;
switch (choice) {
case 1:
cout << "현재 포션 인벤토리 (" << potionInv->GetSize() << "/" << potionInv->GetCapacity() << ")\n";
potionInv->printAllItems();
break;
case 2:
potionInv->SortItems();
cout << "정렬 완료!\n";
potionInv->printAllItems();
break;
case 3: {
string name = readString("포션 이름: ");
string category = readString("종류: ");
int price = readInt("포션 가격: ");
int heal = readInt("회복량(예시): ");
Potion p(name,category, price, heal);
potionInv->AddItem(p);
cout << "현재 포션 인벤토리 용량: " << potionInv->GetSize() << "/" << potionInv->GetCapacity() << "\n";
break;
}
case 4:
potionInv->RemoveLastItem();
cout << "현재 포션 인벤토리 용량: " << potionInv->GetSize() << "/" << potionInv->GetCapacity() << "\n";
break;
default:
cout << "잘못된 입력입니다.\n";
break;
}
}
}
// ====== 메인(일반 인벤토리 + 서브 메뉴 연결) ======
int main() {
// 인벤토리 3개를 따로 운영 (템플릿의 정상적인 사용)
Inventory<Item>* inventory = new Inventory<Item>(4);
Inventory<Weapon>* weapon_inventory = new Inventory<Weapon>(4);
Inventory<Potion>* potion_inventory = new Inventory<Potion>(4);
// 기본 아이템
inventory->AddItem(Item("Stick", 100));
inventory->AddItem(Item("MushRoom", 150));
inventory->AddItem(Item("Gold Bar", 1000));
int select = -1;
while (true) {
printInventoryMenu();
cin >> select;
if (select == 0) {
cout << "프로그램 종료\n";
break;
}
switch (select) {
case 1:
cout << "현재 인벤토리 ("
<< inventory->GetSize() << "/"
<< inventory->GetCapacity() << ")\n";
inventory->printAllItems();
break;
case 2:
inventory->SortItems();
cout << "정렬 완료\n";
inventory->printAllItems();
break;
case 3: {
string name;
int price;
cout << "아이템 이름: ";
cin >> name;
cout << "아이템 가격: ";
cin >> price;
inventory->AddItem(Item(name, price));
break;
}
case 4:
inventory->RemoveLastItem();
break;
case 5: { // 무기 인벤토리
int w_select = -1;
while (true) {
printWeaponInventoryMenu();
cin >> w_select;
if (w_select == 0) break;
switch (w_select) {
case 1:
weapon_inventory->printAllItems();
break;
case 2:
weapon_inventory->SortItems();
weapon_inventory->printAllItems();
break;
case 3: {
string name;
int price, attack;
cout << "무기 이름: ";
cin >> name;
cout << "무기 가격: ";
cin >> price;
cout << "공격력: ";
cin >> attack;
weapon_inventory->AddItem(Weapon(name, price, attack));
break;
}
case 4:
weapon_inventory->RemoveLastItem();
break;
default:
cout << "잘못된 입력\n";
}
}
break;
}
case 6: { // 포션 인벤토리
int p_select = -1;
while (true) {
printPotionInventoryMenu();
cin >> p_select;
if (p_select == 0) break;
switch (p_select) {
case 1:
potion_inventory->printAllItems();
break;
case 2:
potion_inventory->SortItems();
potion_inventory->printAllItems();
break;
case 3: {
string name,category;
int price, heal;
cout << "포션 이름: ";
cin >> name;
cout << "종류: ";
cin >> category;
cout << "포션 가격: ";
cin >> price;
cout << "회복량: ";
cin >> heal;
potion_inventory->AddItem(Potion(name,category,price, heal));
break;
}
case 4:
potion_inventory->RemoveLastItem();
break;
default:
cout << "잘못된 입력\n";
}
}
break;
}
default:
cout << "잘못된 입력\n";
}
}
delete inventory;
delete weapon_inventory;
delete potion_inventory;
return 0;
}
개발합시다!