멍개발

a. 문제 설명

ex) 

b. 의사 코드

1. 우선 주어진 graph를 인접리스트인 unordered_map 에 넣어서 관리하자.
2. BFS는 stack(재귀)의 특성을 가졌으니, 재귀함수를 이용하자.

c. 문제 풀이

#include <vector>
#include <iostream>
#include <unordered_map>
#include <unordered_set>

using namespace std;

unordered_set<char> visit;
unordered_set<char> visit2;

void dfs(unordered_map<char, vector<char>>& graph, char start, unordered_set<char>& visit)
{
	cout << start << " ";
	visit.insert(start);

	for (auto& e : graph[start])
	{
		if (visit.find(e) == visit.end()) dfs(graph, e, visit);
	}
}

void solution(vector<pair<char, char>> graph, char start, unordered_set<char>& visit)
{
	unordered_map<char, vector<char>> um;

	for (auto& e : graph)
	{
		auto first = e.first;
		auto second = e.second;

		um[first].push_back(second);
	}

	dfs(um, start, visit);
}

int main()
{
	vector<pair<char, char>> graph = { {'A','B'},{'B','C'},{'C','D'},{'D','E'}};
	vector<pair<char, char>> graph2 = { {'A','B'},{'A','C'},{'B','D'},{'B','E'},{'C','F'} ,{'E','F'} };

	solution(graph, 'A', visit);
	cout << endl;
	solution(graph2, 'A', visit2);
}

d. 문제 후기

• DFS의 기본 구현 문제이다. 보기보다 쉬워서 안보고 DFS를 구현할 수 있게 되었다.

a. 문제 설명

너비 우선 탐색으로 모든 노드를 순회하는 함수 solution()을 작성하세요. 시작 노드는 정수형 start로 주어집니다. graph 배열은 [출발 노드, 도착 노드] 쌍이 들어 있는 배열입니다. 반환값은 그래프의 시작 노드부터 모든 노드를 너비 우선 탐색한 경로가 순서대로 저장된 배열입니다.

ex) 

b. 의사 코드

1. 우선 주어진 graph를 인접리스트인 unordered_map 에 넣어서 관리하자.
2. DFS는 Queue의 특성을 가졌으니, Queue를 잘 이용하는데, 방문 시점을 push로 할지 pop으로 할지 잘 구분하자.

c. 문제 풀이

#include <bits/stdc++.h>

using namespace std;

void bfs(unordered_map<int, vector<int>>& um, int start)
{
	queue<int> q;
	unordered_set<int> visited;
	
	q.push(start);
	visited.insert(start);
	cout << start << " ";

	while (!q.empty())
	{
		auto front = q.front();
		q.pop();

		for (const auto& e : um[front])
		{
			if (visited.find(e) == visited.end())
			{
				q.push(e);
				visited.insert(e);
				cout << e << " ";
			}
		}
	}
}

void solution(vector<pair<int, int>>& graph, int start)
{
	unordered_map<int, vector<int>> um;

	for (const auto& e : graph)
	{
		int first = e.first;
		int second = e.second;

		um[first].push_back(second);
	}

	bfs(um, 1);
}

int main()
{
	vector<pair<int, int>> graph = { {1,2},{1,3},{2,4},{2,5},{3,6},{3,7},{4,8},{5,8},{6,9},{7,9} };
	vector<pair<int, int>> graph2 = { {0,1},{1,2},{2,3},{3,4},{4,5},{5,0}};

	solution(graph, 1);
	cout << endl;
	solution(graph2, 0);
	
}

d. 문제 후기

• BFS의 기본 구현 문제이다. 여기서 가중치가 붙게된다면 우선순위 큐(최소 힙)를 이용하여 최단 경로를 구하는 알고리즘을 만들 수 있다.

a. 문제 설명

주어진 그래프와 시작 노드를 이용하여 다익스트라 알고리즘을 구현하는 solution()함수를 작성하세요. 시작 노드 start, 노드의 개수 numNode, [시작 노드, 도착 노드, 가중치] 형태로 간선 정보를 담은 배열 edges가 인수로 주어집니다. edges에 [2,1,9] 가 있다면 시작 노드 2에서 도착 노드 1까지 가중치가 9인 간선이 있다는 뜻입니다. 시작 노드 start 부터 각 노드까지 최소 비용을 담은 벡터를 반환하는 solution() 함수를 구현하세요.

ex) 

b. 의사 코드

1. 일단 각 노드를 연결하는 그림을 그려보자.

c. 문제 풀이

#include <vector>
#include <tuple>

using namespace std;

const int INF = 99999;
const int MAX_NODES = 100;
int graph[MAX_NODES][MAX_NODES];
bool visited[MAX_NODES];

vector<int> solution(int start, int numNodes, const vector<tuple<int, int, int>> edges) {
  //❶ 그래프 및 방문 여부 초기화
  for (int i = 0; i < MAX_NODES; ++i) {
    fill_n(graph[i], MAX_NODES, INF);
    visited[i] = false;
  }
  
  //❷ 입력받은 간선 정보를 그래프로 표현
  for (const auto& [from, to, weight] : edges) {
    graph[from][to] = weight;
  }

  //❸ 시작 노드를 제외한 모든 노드의 최소 비용을 INF로 초기화
  vector<int> distances(numNodes, INF);
  distances[start] = 0;

  for (int i = 0; i < numNodes - 1; ++i) {
    int minDistance = INF;
    int closestNode = -1;

    //❹ 최소 거리 노드 찾기
    for (int j = 0; j < numNodes; ++j) {
      if (!visited[j] && distances[j] < minDistance) {
        minDistance = distances[j];
        closestNode = j;
      }
    }

    //❺ 찾은 노드를 방문 처리
    visited[closestNode] = true;

    //❻ 인접 노드에 대한 거리 업데이트
    for (int j = 0; j < numNodes; ++j) {
      int newDistance = distances[closestNode] + graph[closestNode][j];
      if (!visited[j] && graph[closestNode][j] != INF && newDistance < distances[j]) {
        distances[j] = newDistance;
      }
    }
  }

  return distances;
}


//아래 코드는 테스트 코드 입니다.
#include <iterator>
#include <iostream>

using namespace std;


void print(vector<int> vec)
{
  copy(vec.begin(), vec.end(), std::ostream_iterator<int>(cout, " "));
  cout << endl;
    
}

int main()
{
  
  print(solution(0, 3, {{0, 1, 9},{0, 2, 3},{1, 0, 5},{2, 1, 1}})); //출력값 : 0 4 3
  print(solution(0, 4, {{0, 1, 1}, {1, 2, 5}, {2, 3, 1}})); //출력값 : 0 1 6 7
  return 0;
}

d. 문제 후기

• BFS/DFS는 자세히 실습해보질 않아서 많이 어려움을 느끼는 것 같다.

a. 문제 설명

문제 참조

b. 의사 코드

1. 처음에는 DFS를 이용해 문제를 풀려고 했으나 잘 풀리지 않았다.
2. 이후로 BFS로 문제를 풀어볼려고 하였으나 잘 되지 않았다.

c. 문제 풀이

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;


unordered_map<int, vector<pair<char, int>>> um;
unordered_map<char, int> um2;
unordered_set<int> visit;


int bfs(int start, int end)
{
    int cnt = -1;
    queue<int> q;
    
    int stack = 0;
    q.push(start);
    while(!q.empty())
    {
        int front = q.front();
        q.pop();
        visit.insert(front);
        cnt++;
        
        if(front == end) break;
        
        int size = um[front].size();
        for(int i = 0; i < size; i++)
        {
            if(visit.find(um[front][i].second) == visit.end())
            {
                q.push(um[front][i].second);
            }
        }
    }    
    
    //visit.clear();
    
    return cnt;
}

int solution(vector<string> maps) {
    int answer = 0;
    
    int row = maps.size();
    int col = maps[0].size();
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j <col; j++)
        {
            if(maps[i][j] == 'X') continue;
            
            int cur = i*row+j;
            int up = (i-1)*row+j;
            int down = (i+1)*row+j;
            int left = i*row + j - 1;
            int right = i*row + j + 1;
            
            if(maps[i][j] == 'S') um2['S'] = cur;
            if(maps[i][j] == 'L') um2['L'] = cur;
            if(maps[i][j] == 'E') um2['E'] = cur;
            
            if(i-1 >= 0 && maps[i-1][j] != 'X') um[cur].push_back({maps[i-1][j],up});
            if(i+1 < row && maps[i+1][j] != 'X') um[cur].push_back({maps[i+1][j],down});
            if(j-1 >= 0 && maps[i][j-1] != 'X') um[cur].push_back({maps[i][j-1],left});
            if(j+1 < col && maps[i][j+1] != 'X') um[cur].push_back({maps[i][j+1],right});
        }
    }
    
    if(um[um2['S']].empty()) return -1;
    answer = bfs(um2['S'], um2['L']) + bfs(um2['L'], um2['E']);    
    
    
    return answer;
}

d. 문제 후기

• 해시맵과 해시셋이 능사가 아니라는 것을 알았다. 그래프 유형의 문제는 약하다는것을 느꼈었고, 고민끝에 정답을 보고 한줄한줄 분석하여 내것으로 암기하여 풀어보려고 한다.
• 정답 풀이

#include <queue>
#include <string>
#include <vector>

using namespace std;

struct Point //S나 L나 E의 특수한 공간의 위치를 반환
{
	int y, x, cnt;
};

int dy[4] = { -1,0,1,0 }; // 상하의 증감값을 표현
int dx[4] = { 0, 1, 0, -1 }; // 좌우의 증감값을 표현
int n, m; // row와 col을 표현

bool isWithinRange(int y, int x) { return 0 <= y && y < n && 0 <= x && x < m; }//21. 상하좌우로 이동했을 시, 배열의 range에 들어가는지 검사

Point findStartPoint(char start, vector<string>& maps)
{
	for (int i = 0; i < n; i++) // 7.maps의 row만큼 반복
	{
		for (int j = 0; j < m; j++) // 8.maps의 col 만큼 반복
		{
			if (maps[i][j] == start) // 9.start를 검출했다면
			{
				return { i,j,0 }; //10.start의 위치를 반환
			}
		}
	}
}

int bfs(char start, char end, vector<string>& maps)
{
	bool visited[101][101] = { false }; // 4. 방문한 곳들을 이력으로 남기는 배열
	queue<Point> q; // 5. bfs를 진행하기 위한 queue 선언

	q.push(findStartPoint(start, maps)); // 6. queue에 start 위치를 push해주기

	while (!q.empty()) //11. q가 다 빌때까지 반복
	{
		Point current = q.front(); //12. q의 front를 기준으로 최근 포인트를 저장
		q.pop(); //13. current로 저장을 했으니 빼주기

		if (maps[current.y][current.x] == end) //14. 현재 위치가 도착점이면
		{
			return current.cnt; //15. 현재 위치의 cnt를 반환
		}

		for (int i = 0; i < 4; i++) // 16. 4번 반복? 아...! 상하좌우를 for문으로 표현
		{
			int ny = current.y + dy[i]; // 17. 현재위치의 y좌표와 증분y축의 값을 더해 위와 아래를 ny에 넣기
			int nx = current.x + dx[i]; // 18. 현재위치의 x좌표와 증분x축의 값을 더해 좌측과 우측을 nx에 넣기
			// 19. i를 순서대로 하면 위, 오른쪽, 아래, 왼쪽

			if (isWithinRange(ny, nx) && !visited[ny][nx] && maps[ny][nx] != 'X') // 20. 배열 내부에 들어 있는 값인지, 방문한 적이 없는지,  X가 아닌지 다 조건에 적합하다면, q에 푸쉬한다.
			{
				q.push({ ny,nx,current.cnt + 1 }); // 22. count를 1 증가시킨 채 이동한 좌표를 푸쉬해준다.
				visited[ny][nx] = true; // 23. 방문했다는 위치를 갱신
			}
		}
	}
	return -1; // 24. E를 찾지 못했다면 마지막 위치 반환
}

int solution(vector<string> maps)
{
	n = maps.size(); // 1. row
	m = maps[0].size(); // 2. col

	int distanceToL = bfs('S', 'L', maps); // 3. Start 부터 End까지 가는 거리를 cnt로 환산했을 때, bfs 함수를 이용
	if (distanceToL == -1) return -1; // 25. bfs가 -1이 되어 돌아왔다면, 목표를 찾지 못했다는 뜻이므로 -1을 리턴

	int distanceToE = bfs('L', 'E', maps); // 26. bfs 함수를 다시 목표만 바꾸어 호출
	return distanceToE == -1 ? -1 : distanceToL + distanceToE; // 27. -1이 돌아왔다면 -1을, 제대로 카운팅 되었다면 두개의 변수를 합침
}

a. 문제 설명

문제 참조

b. 의사 코드

1. 처음에 고민했던 경험을 바탕으로 BFS를 사용하여 풀기로 하였다.

c. 문제 풀이

#include <vector>
#include <queue>

using namespace std;

struct Node
{
    int x;
    int y;
    int cnt;
};

int visit[100][100];

int solution(vector<vector<int>> maps)
{
    int answer = -1;
    int row = maps.size();
    int col = maps[0].size();
    queue<Node> q;
    q.push({0,0,1}); //시작 위치
    
    while(!q.empty())
    {
        Node cur = q.front();
        q.pop();
        visit[cur.y][cur.x]++;
        
        if(cur.x == col-1 && cur.y == row-1)
        {
            answer = cur.cnt;
            return cur.cnt;
            break;
        }
        
        for(int i = 0; i < 4; i++) // 0은 up, 1은 down, 2는 left, 3은 right
        {
            if(i == 0 && cur.y-1 >= 0 && maps[cur.y-1][cur.x] && visit[cur.y-1][cur.x] == 0) q.push({cur.x,cur.y-1,cur.cnt+1});
            if(i == 1 && cur.y+1 < row && maps[cur.y+1][cur.x] && visit[cur.y+1][cur.x] == 0) q.push({cur.x,cur.y+1,cur.cnt+1});
            if(i == 2 && cur.x-1 >= 0 && maps[cur.y][cur.x-1] && visit[cur.y][cur.x-1] == 0) q.push({cur.x-1,cur.y,cur.cnt+1});
            if(i == 3 && cur.x+1 < col && maps[cur.y][cur.x+1] && visit[cur.y][cur.x+1] == 0) q.push({cur.x+1,cur.y,cur.cnt+1});
        }
    }
    
    return answer;
}

d. 문제 후기

• 정답은 모두 맞았으나 효율성체크에서 모두 오답이 떴다.

a. 문제 설명

n개의 양의 정수로 이루어진 배열 arr와 정수 target이 주어졌을 때 이 중에서 합이 target인 두 수가 arr에 있는지 찾고, 있으면 true, 없으면 false를 반환하는 solution() 함수를 작성하세요.

• n은 2 이상 10,000이하의 자연수 입니다.
• arr의 각 원소는 1 이상 10,000 이하의 자연수 입니다.
• arr의 원소 중 중복되는 원소는 없습니다.
• target은 1 이상 20,000 이하의 자연수 입니다.

ex)

b. 의사 코드

1. 평소같으면 2중 for문을 써서 확인해보겠지만, hash를 활용하여 어떻게 동작하는지 확인해보자.
2. Hash를 쓴다면, 1,2,3,4,8의 값을 키에 넣어 있는지 없는지를 확인하는 수단으로 사용할 수 있을듯 하다.
3. target 숫자를 확인하고 첫번째 숫자와 같이 더하면 target이 되는 수를 찾아보는 식을 짠다.

c. 문제 풀이

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

bool solution(vector<int> arr, int target)
{
	bool answer = false;
	unordered_map<int, int> unmap;

	for (const auto& e : arr) unmap[e]++; //1. 각 숫자를 해시에 넣어준다.

	for (const auto& e : arr)
	{
    	//2. 해시의 키 값을 find 함수를 이용해 방정식의 해가 되는 값을 찾는다.
        //*  또한, 해가 자기 자신이 될 경우도 있기 때문에 자기 자신이 될 경우는 제외한다.
		if (unmap.find(target - e) != unmap.end() && (target - e) != e)
		{
			answer = true;
			break;
		}
	}

	return answer;
}

int main()
{
	vector<int> arr1 = { 1,2,3,4,8 };
	int target1 = 6;

	vector<int> arr2 = { 2,3,5,9 };
	int target2 = 10;

	cout << boolalpha << solution(arr1, target1) << endl;
	cout << boolalpha << solution(arr2, target2) << endl;
}

d. 문제 후기

• 시간복잡도 O(2N) : 주어진 배열을 2번 순회한다.
• 책에서는 vector를 2개 선언하여 하나는 해시의 key역할, 하나는 value을 하게 만들었다.
• 해시의 ADT파트에서 스스로 구현해보았으므로 이 과정은 생략하고 STL을 이용하여 풀이해보았다.

a. 문제 설명

• 입력 문자열은 영어 소문자로만 이루어져 있습니다.
• 문자열의 최대 길이는 10^6 입니다.
• 해시 충돌은 고려하지 않습니다.
• 아래와 같은 문자열 해싱 방법을 활영해서 해싱 함수를 구현하세요.
• 다음 식에서 p는 31, m은 1,000,000,007 입니다.
  • hash(s) = (s[0] + s[1]*p + s[2]*p^2 ........ s[n-1]*p^n-1)mod m

ex)

b. 의사 코드

1. 문자열 해싱을 이용해, 문자열을 숫자로 변환해준다.
2. 변환한 숫자를 Key값으로 만들어 준 후에, 해싱화 시켜준다.
3. 해싱화 시킨 값들을 찾는다.해싱화 시킨 값들을 찾는다.

c. 문제 풀이

#include <vector>
#include <string>
#include <unordered_set>

using namespace std;

// ❶ 다항 해시 함수 구현
long long polynomial_hash(const string& str) {
    const int p = 31;  // 소수
    const long long m = 1000000007;  // 버킷 크기
    long long hash_value = 0;

    for (char c : str) {
        hash_value = (hash_value * p + c) % m;
    }

    return hash_value;
}

vector<bool> solution(vector<string> string_list, vector<string> query_list) {
    unordered_set<long long> hash_set;

    //❷ string_list의 각 문자열에 대해 다항 해시값을 계산하고 저장
    for (const string& str : string_list) {
        long long hash = polynomial_hash(str);
        hash_set.insert(hash);
    }

    vector<bool> result;

    //❸  query_list의 각 문자열이 string_list에 있는지 확인하고 result에 추가
    for (const string& query : query_list) {
        long long query_hash = polynomial_hash(query);
        bool found = (hash_set.find(query_hash) != hash_set.end());
        result.push_back(found);
    }
    // ❹ query_list의 문자열이 hash에 있는지 결과가 저장된 result를 반환
    return result;
}


//아래 코드는 테스트 코드 입니다.
#include <iterator>
#include <iostream>
void print(vector<bool> vec)
{
    copy(vec.begin(), vec.end(), std::ostream_iterator<bool>(cout, " "));
    cout << endl;
}

int main()
{
    //true를 출력하면 1이되고 false를 출력하면 0
    print(solution({ "apple", "banana", "cherry" }, { "banana", "kiwi", "melon", "apple" })); // 1 0 0 1
    return 0;

}

d. 문제 후기

• 시간복잡도 O(N^2) : 해싱할 문자열의 문자 하나하나를 검사하고, 그 문자열들을 숫자로 변환하는 과정이 있기 때문
• 문자열 해싱은 메르센 소수 31과 1000000007만 기억하고 있어야겠다.
• 또한, 이 문자열 해싱은 잘못쓰이면, 오버플로우가 일어나기 때문에 mod m 연산을 잘 해주는 것이 중요하다.

a. 문제 설명

b. 의사 코드

1. 일단 참가자들을 다 해시에 넣는다.문자열 해싱을 이용해, 문자열을 숫자로 변환해준다.
2. 완주자들을 해시에서 빼준다.
3. 참가자 중 완주자에 들지 못한 사람을 answer에 넣어준다.

c. 문제 풀이

#include <string>
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) 
{
    string answer = "";
    unordered_map<string, int> unmap;
    
    for(auto e : participant) unmap[e]++; //1. 일단 참가자들을 다 해시에 넣는다.
    
    for(int i = 0; i < completion.size(); i++)
    {
        unmap[completion[i]]--; //2. 완주자들을 해시에서 빼준다.
    }
    
    for(int i = 0; i < participant.size(); i++)
    {
        if(unmap[participant[i]] > 0) //3. 참가자 중 완주자에 들지 못한 사람(i > 0)을 answer에 넣어준다.
        {
            answer += participant[i];
            break;
        }
    }
    
    return answer;
}

d. 문제 후기

• 시간복잡도 O(3N) : 해시에 모든 참가자를 넣고, 완주자들을 해시에서 제외하고, 남은 참가자를 도출
• 해시맵을 사용하는 첫 예제인 만큼 어떻게 해시맵을 사용해야 할 지 알게 되었던 문제였다.

a. 문제 설명

b. 의사 코드

1. 주어진 끝말잇기 단어를 해시맵에 모두 담는 반복문을 만든다.
2. 만약, 중복되거나 끝말이 아닌 단어가 온다면 count를 기록해둔다.
3. count에 따라서 몇번째 사람이 걸렸는지, 몇번 돌았는지를 기록한다.

c. 문제 풀이

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

vector<int> solution(int n, vector<string> words) 
{
    vector<int> answer;
    unordered_map<string, int> hash_map;
    int cnt = 0;
    
    // !. 첫번째 해시는 무조건 담는다.
    hash_map[words[0]]++;
    // 1. 주어진 단어를 해시맵에 담는 반복문을 만든다.
    for(int i = 1; i < words.size(); i++)
    {
        // 2. 만약, 중복되거나 끝말이 아닌 단어가 온다면 count를 기록해둔다.
        // !. 한글자인 단어도 검출
        if(hash_map[words[i]] >= 1 || words[i-1][words[i-1].size()-1] != words[i][0] || words[i].size() == 1)
        {
            cnt = i;
            break;
        }
        else
        {
            hash_map[words[i]]++;
        }
    }

    // !. 만약 아무도 실패하지 않았다면, 0,0을 리턴한다.
    if(cnt == 0)
    {
        answer.push_back(0);
        answer.push_back(0);
        return answer; 
    }
    // 3. 카운트에 따라서 n과 조합하여 가장 먼저 탈락하는 사람의 번호와 몇번째 차례인지 도출해낸다.
    answer.push_back(cnt%n+1); // 가장 먼저 탈락하는 사람
    answer.push_back(cnt/n+1); // 몇번째 차례
    return answer;
}

d. 문제 후기

• 시간복잡도 O(N) : 해시에 참가자들을 넣으면서, 단어들이 규칙에 맞는지 도출해낸다.
• 이전에도 푼 문제지만, 중복인 단어나 끝말잇기의 규칙에 잘 들어맞는지를 판단하는것이 중요!

a. 문제 설명

b. 의사 코드

1. 전화번호를 모두 맵에 저장한다.
2. 각 전화번호가 자기 자신이 아니라는 가정 하에 한 단어씩 글자마다 비교하여 맵에 있는지 확인한다.

c. 문제 풀이

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) 
{
    bool answer = true;
    unordered_map<string, int> unmap;
    
    // 1. 전화번호를 모두 맵에 저장한다.
    for(auto e : phone_book) unmap[e]++;
    
    // 2. 각 전화번호를 한번씩 순회하여 맵에 있는지 확인한다.
    for(auto e : phone_book)
    {
        string temp = "";
        
        for(auto c : e)
        {
            temp.push_back(c);
            if(temp != e && unmap.find(temp) != unmap.end())
            {
                return false;
            }
        }
        
    }
    return answer;
}

d. 문제 후기

• 시간복잡도 O(N*M^2) : phone_book을 맵에 한번씩 넣고,  phone_book에서 글자 하나하나를 계속 비교한다.
• 책을 보니 정렬로 푸는 매우 쉬운 방법이 있어 그 방법을 이용하면 될 것 같다. 
• string끼리의 정렬과, int끼리의 정렬은 다르다는 것을 알았다.
• 꼭 해시맵이 시간복잡도 상으로 이득을 보는건 아니라는 것을 알게 되었다.

a. 문제 설명

b. 의사 코드

1. want 와 number를 해시맵에 초기화한다.
2. 할인 행사가 진행되는 품목을 순회하는데, 10개씩 확인해봐야 하기 때문에 unmap_temp을 하나 더 선언하여 할인행사 하는 품목들을 하나하나 넣어준다.
3. 마지막으로 unmap_temp와 unmap에 담긴 것들이 모두 같은지 비교한다.
4. 가능한 날짜마다 answer에 1씩 더해준다.

c. 문제 풀이

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) 
{
    int answer = 0;
    unordered_map<string, int> unmap;
    
    for (int i = 0; i < want.size(); i++)
    {
        unmap[want[i]] = number[i];
    }
    
    for (int i = 0; i < discount.size()-9; i++)
    {
        unordered_map<string, int> unmap_temp;
        bool flag = false;
        
        for(int j = i; j < i + 10; j++)
        {
            unmap_temp[discount[j]]++;
        }
        
        for(const auto& e : unmap_temp)
        {
            if(unmap.find(e.first) == unmap.end() || e.second != unmap.find(e.first)->second)
            {
                flag = true;
                break;
            }
        }
        
        if(flag) continue;
        answer++;
    }
    return answer;
}

d. 문제 후기

• 시간복잡도 O(20*N) : 일단 해시맵에 저장하고, 할인행사중인 10개의 품목을 또 저장한 다음, 10개의 품목 하나하나 검사하는 과정이 있으므로 20N이다.
• 책에서는 시간복잡도를 더 개선할 수 있는 방법을 제시하였는데, 개발자의 입장에서는 계속 효율적인 방법을 찾아나가는 것이 유지보수가 아닐까? 라는 생각이 든다.

a. 문제 설명

b. 의사 코드

1. 일단 record의 공백으로 나누어진 부분을 명령, uid, 이름으로 분석해야 하기 때문에 이것을 string 내장함수를 적절히 이용하여 분리한다
2. 이름을 변경해야 하는 부분은 Enter와 Change이기 때문에, Enter와 Change에서는 for문을 다시한번 사용하여 이전에 입력했던 채팅안내문의 닉네임을 수정하였다. <-- 여기서부터는 코드를 작성하며 생각하였다.

c. 문제 풀이(오답)

#include <string>
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<string> solution(vector<string> record) 
{
    vector<string> answer;
    unordered_map<string, string> unmap;
    
    for(auto e : record)
    {
        if(e.find("Enter") != string::npos)
        {
            int pos1 = e.find(' ');
            string cmd = e.substr(0, pos1);
            
            int pos2 = e.find(' ', e.find(' ') + 1);
            string uid = e.substr(pos1+1, pos2 - pos1 - 1);
            
            string name = e.substr(pos2+1, e.size() - pos2);
            
            unmap[uid] = name;
            
           for(int i = 0; i < answer.size() ; i++)
            {
                if(answer[i] == uid && answer[i+1].find("들어왔") != string::npos)
                {
                    answer[i+1] = name + "님이 들어왔습니다.";
                }
                else if (answer[i] == uid && answer[i+1].find("나갔") != string::npos)
                {
                    answer[i+1] = name + "님이 나갔습니다.";
                }
            }
            
            answer.push_back(uid);
            answer.push_back(unmap[uid] + "님이 들어왔습니다.");
        }
        else if(e.find("Leave") != string::npos)
        {
            int pos1 = e.find(' ');
            string cmd = e.substr(0, pos1);
            
            int pos2 = e.find(' ', e.find(' ') + 1);
            string uid = e.substr(pos1+1, pos2 - pos1 - 1);
            
            answer.push_back(uid);
            answer.push_back(unmap[uid] + "님이 나갔습니다.");
        }
        else if(e.find("Change") != string::npos)
        {
            int pos1 = e.find(' ');
            string cmd = e.substr(0, pos1);
            
            int pos2 = e.find(' ', e.find(' ') + 1);
            string uid = e.substr(pos1+1, pos2 - pos1 - 1);
            
            string name = e.substr(pos2+1, e.size() - pos2);
            
            unmap[uid] = name;
            
            for(int i = 0; i < answer.size() ; i++)
            {
                if(answer[i] == uid && answer[i+1].find("들어왔") != string::npos)
                {
                    answer[i+1] = name + "님이 들어왔습니다.";
                }
                else if (answer[i] == uid && answer[i+1].find("나갔") != string::npos)
                {
                    answer[i+1] = name + "님이 나갔습니다.";
                }
            }
        }
    }
    
    vector<string> answer2;
    
    for(int i = 1; i < answer.size(); i+=2) answer2.push_back(answer[i]);
    
    return answer2;
}

d. 문제 후기

• 시간복잡도 O(N^2) : 명령어를 저장하고, 저장한 명령어를 수행 할 때, 이름을 바꾸기 위해서 이전 기록들을 뒤져 이름을 계속 바꾸어 나가는 작업을 수행하였다.
• 정답을 보면 꽤나 간단하게 코드가 짜여져 있었다. 아래 코드를 확인하면 된다.
  

#include <vector>
#include <unordered_map>
#include <sstream>

using namespace std;

vector<string> solution(vector<string> record)
{
	vector<string> answer;
	unordered_map<string, string> uid;

	for (const auto& line : record)
	{
		stringstream ss(line);
		string cmd, id, name;
		ss >> cmd >> id;

		if (cmd != "Leave")
		{
			ss >> name;
			uid[id] = name;
		}
	}

	for (const auto& line : record)
	{
		stringstream ss(line);
		string cmd, id;
		ss >> cmd >> id;

		if (cmd == "Enter")
		{
			answer.push_back(uid[id] + "님이 들어왔습니다.");
		}
		else if (cmd == "Leave")
		{
			answer.push_back(uid[id] + "님이 나갔습니다.");
		}
	}

	return answer;
}

•  새롭게 안 사실은 sstream헤더의 존재로 cmd, uid, name 변수에 깔끔하게 나눌 수 있었으며
• 굳이 2중 for문을 쓰는게 아닌, 2번 for문을 써서 첫번째는 명령을 먼저 수행하여 uid에 따른 name만 변경하고 두번째는 명령어에 따라서  answer에 넣어주는 작업을 하였는데, 2중 for문을 경계하는법을 알게된 것 같다.

a. 문제 설명

b. 의사 코드

1. 일단 속한 장르 중 가장 많이 재생된 장르를 내림차순으로 정렬해야 했기 때문에 hash_map<string, int> 를 이용하여 장르별 plays를 총합하여, sorting 하였다.
2.  이후 각 장르 별 idx와 play횟수를 make_pair를 통해 한 DataType에 묶어두고, 이를 내림차순으로 정렬하고 같은 재생횟수는 idx기준으로 오름차순 정렬을 한번 더 한 다음 장르별 차트hash_map에 넣어준다.
3. 장르별 차트hash_map의 second값을 2개 뽑아 순서대로 넣어주면 끝

c. 문제 풀이(오답)

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>

using namespace std;

bool ByValue(const pair<string, int>& a, const pair<string, int>& b)
{
    return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays)
{
    vector<int> answer;

    unordered_map<string, int> umap;
    for (int i = 0; i < genres.size(); i++)
    {
        umap[genres[i]] += plays[i];
    }

    vector<pair<string, int>> vec_pair(umap.begin(), umap.end());
    sort(vec_pair.begin(), vec_pair.end(), ByValue);

    unordered_map<string, vector<pair<int, int>>> umap_chart;
    for (int i = 0; i < vec_pair.size(); i++)
    {
        vector<pair<int, int>> temp;
        for (int j = 0; j < plays.size(); j++)
        {
            if (vec_pair[i].first == genres[j])
            {
                temp.push_back(make_pair(plays[j], j));
            }
        }

        sort(temp.begin(), temp.end());
        reverse(temp.begin(), temp.end());

        for (int j = 1; j < temp.size(); j++)
        {
            if (temp[j - 1].first == temp[j].first && temp[j - 1].second > temp[j].second)
            {
                swap(temp[j - 1], temp[j]);
            }
        }

        umap_chart[genres[i]] = temp;
    }

    for (const auto& e : umap_chart)
    {
        int cnt = 0;
        for (int i = 0; i < e.second.size(); i++)
        {
            if (cnt >= 2) break;
            answer.push_back(e.second[i].second);
            cnt++;
        }
    }
    
    return answer;
}

d. 문제 후기

• 시간복잡도 O(N^2) : 가장 많이 실행된 장르를 순회하고, 그 장르에서 가장 많이 실행된 2가지를 선별하는 과정이 있어 2중 for문을 쓰게 되었다.
• 정답을 보면 꽤나 간단하게 코드가 짜여져 있었다. 아래 코드를 확인하면 된다.
  

#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>

using namespace std;

bool compareGenre(const pair<string, int>& a, const pair<string, int>& b) {
  return a.second > b.second;
}

bool compareSong(const pair<int, int>& a, const pair<int, int>& b) {
  if (a.second == b.second) return a.first < b.first;
  return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
  vector<int> answer;
  unordered_map<string, vector<pair<int, int>>> genres_dict;
  unordered_map<string, int> play_dict;

  //❶ 장르별 총 재생 횟수와 각 곡의 재생 횟수 저장
  for (int i = 0; i < genres.size(); ++i) {
    genres_dict[genres[i]].push_back({i, plays[i]});
    play_dict[genres[i]] += plays[i];
  }

  //❷ 총 재생 횟수가 많은 장르순으로 정렬
  vector<pair<string, int>> sorted_genres(play_dict.begin(), play_dict.end());
  sort(sorted_genres.begin(), sorted_genres.end(), compareGenre);

  //❸ 각 장르 내에서 노래를 재생 횟수 순으로 정렬해 최대 2곡 까지 선택
  for (auto& genre : sorted_genres) {
    auto& songs = genres_dict[genre.first];
    sort(songs.begin(), songs.end(), compareSong);

    for (int i = 0; i < min(2, (int)songs.size()); ++i) {
      answer.push_back(songs[i].first);
    }
  }

  return answer;
}

//아래 코드는 테스트 코드 입니다.
#include <iterator>
#include <iostream>
void print(vector<int> vec)
{
    copy(vec.begin(), vec.end(), std::ostream_iterator<int>(cout, " "));
    cout << endl;
}

int main()
{
    print(solution({"classic", "pop", "classic", "classic", "pop"}, {500, 600, 150, 800, 2500})); //출력값 :  1 0 0 1
    return 0;

}

a. 문제 설명

b. 의사 코드

1. 우선 신고자와 피신고자로 hash_map 변수를 만들어, 신고자는 내가 신고한 사람들을 모으고 / 피신고자는 신고를 받은 횟수를 카운팅해준다.
2. 피신고자가 k라는 기준보다 많이 신고 당할 경우, id_list를 한번 순회하여 신고자들에게 메일을 전송한 횟수를 retrun 해준다.

c. 문제 풀이

#include<iostream>
#include<unordered_map>
#include<set>
#include<vector>
#include<algorithm>
#include<string>
#include<sstream>

using namespace std;

vector<int> solution (vector<string> id_list, vector<string> report, int k)
{
    vector<int> answer;
    
    sort(report.begin(), report.end());
    auto pos = unique(report.begin(), report.end());
    report.erase(pos, report.end());
    
    unordered_map<string, vector<string>> umap_report;
    unordered_map<string, int> umap_reported;
    
    for(const auto& str : report)
    {
        stringstream ss(str);
        string receiver;
        string reporter;
        
        ss >> reporter >> receiver;
        
        umap_report[reporter].push_back(receiver);
        umap_reported[receiver]++;
    }
    
    for(const auto& id : id_list)
    {
        int temp = 0;
        for(const auto& ban : umap_reported)
        {
            if(ban.second < k) continue;
            if(find(umap_report[id].begin(), umap_report[id].end(), ban.first) != umap_report[id].end())
            {
                temp++;
            }
        }
        answer.push_back(temp);
    }
    
    return answer;
}

d. 문제 후기

• 시간복잡도 O(N^2) : id_list를 순회하며 피신고자hash_map을 k의 기준에 부합한지 1번 더 순회하므로 N^2의 시간복잡도를 가진다.
• 이전에 stringstream에 대해서 배우지 않았다면, 역시나 어렵게 공백을 기준으로 쪼개는 알고리즘 코드를 작성하였을 것이다.

a. 문제 설명

b. 의사 코드

1. 순열을 사용해야 한다는 것을 알았으나, next_permutation 함수의 사용법과 재귀로 조합함수를 어떻게 짜야하는지 감이 안잡혀서 다시한번 제대로 배워야 겠다는 생각이 들었다.

c. 문제 풀이(답지)

#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;

map<string,int> combi; // 주문의 조합 - 조합의 빈도

// 실제 주문의 조합을 구하는 함수
void combination(string src, string dst, int depth) {
  if (dst.size() == depth) combi[dst]++;

  else for (int i = 0; i < src.size(); i++)
    combination(src.substr(i+1), dst+src[i], depth);
}

vector<string> solution(vector<string> orders, vector<int> course) {
  vector<string> answer;
  // ❶ 각 주문들을 오름차순으로 정렬
  for (string &order : orders)
    sort(order.begin(), order.end());
  
  for (int len : course) {
    for (string order : orders)
      // ❷ course의 길이에 해당되는 조합 생성
      combination(order, "", len);

    // ❸ 각 주문의 빈도수를 순회하면서 가장 많은 빈도수를 maxOrder에 저장
    int maxOrder = 0;
    for (auto it : combi)
      maxOrder = max(maxOrder, it.second);

    // ❹ 주문 횟수가 2회 이상이면서, 가장 많이 주문된 주문의 구성은 answer에 추가
    for (auto it : combi)
      if (maxOrder >= 2 && it.second == maxOrder)
        answer.push_back(it.first);
    
    combi.clear();
  }
  // ❺ 반환 전, 문제의 조건에 따라 주문의 구성들을 오름차순 정렬해서 반환 
  sort(answer.begin(), answer.end());
  return answer;
}


//아래 코드는 테스트 코드 입니다.
#include <iterator>
#include <iostream>
void print(vector<string> vec)
{
    copy(vec.begin(), vec.end(), std::ostream_iterator<string>(cout, " "));
    cout << endl;
}

int main()
{
    print(solution({"ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"}, {2, 3, 4})); //출력값 :  AC ACDE BCFG CDE
    print(solution({"ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"}, {2, 3, 5})); //출력값 : ACD AD ADE CD XYZ
    print(solution({"XYZ", "XWY", "WXA"}, {2, 3, 4})); //출력값 : WX XY 

    return 0;
}

d. 문제 후기

• 의사코드에 있는 내용과 동일

a. 문제 설명

소괄호는 짝을 맞춘 열린 괄호 '(' 와 닫힌 괄호 ')'로 구성합니다. 문제에서는 열린 괄호나 닫힌 괄호가 마구 뒤섞인 문자열 s를 줍니다. 이 때 소괄호가 정상으로 열고 닫혔는지 판별하는 solution()함수를 구현하세요.

만약 소괄호가 정상적으로 열고 닫혔다면 true를, 그렇지 않다면 false를 반환하면 됩니다.

• 열린 괄호는 자신과 가장 가까운 닫힌 괄호를 만나면 상쇄됩니다.
• 모든 괄호가 상쇄되어 더이상 아무 괄호도 없어야만 정상으로 열고 닫혔다고 할 수 있습니다.
• 더 상쇄할 괄호가 없을 때 까지 상쇄를 반복합니다.

ex)

b. 의사 코드

1. 내부에 있는 '(' 와 ')'를 순회를 통해 확인한다.
2. stack을 공간을 하나 만들고 순회하면서 '('를 만나면 push를, ')' 만나면 pop을 한다.
3. 만약 ')'을 했을 때 stack이 비어있다면 bool을 false로 하고 solution을 return 한다.
4. 만약 ')'을 했을 때 stack이 비어있지 않다면 계속 pop을 한다.

c. 문제 풀이

#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool solution(const string& param)
{
	stack<char> stack;

	for (int i = 0; i < param.size(); i++)
	{
		if (param[i] == '(')
		{
			cout << "push : (" << endl;
			stack.push(param[i]);
		}
		else if (param[i] == ')' && !stack.empty())
		{
			cout << "pop : )" << endl;
			stack.pop();
		}
		else if (param[i] == ')' && stack.empty())
		{
			cout << "error" << endl;
			return false;
		}
	}

	return stack.empty() ? true : false;
}

int main()
{
	string s = "()())"; // 임의의 괄호를 입력하세요

	cout << boolalpha << solution(s) << endl;
}

d. 문제 후기

• 시간복잡도 O(N) : 주어진 문자열을 1번 순회한다.
• 코테에서의 stack 은 짝을 맞추거나, 재귀, 이전으로 되돌리는 동작에 특화되어 있다는 것을 알았다.

a. 문제 설명

10진수 decimal을 입력받아 2진수로 변환해서 문자열 형태로 반환하는 solution() 함수를 구현하세요.

ex)

b. 의사 코드

1. 일단 decimal(10진수) 와 문자열 형태를 받아야 하니 int 자료형을 선언하고 string을 return 한다.
2. 입력받은 숫자를 0으로 나누어 떨어질 때 까지 계속 2로 나누어 준다.
3. 2로 나누어주면서 나온 나머지에 따라 string 자료형에 1 또는 0을 push_back() 해준다.
4. reverse()를 통해 문자열을 뒤집어준다.

c. 문제 풀이

#include <iostream>
#include <stack>
#include <string>
#include <algorithm>

using namespace std;

void print(const string& s)
{
	for (const auto& e : s)
	{
		cout << e;
	}

	cout << endl;
}

string solution(int& input)
{
	string s;
    
	if (input == 0)
	{
		s.push_back('0');
		return s;
	}

	while (input / 2 != 0)
	{
		if (input % 2 == 1)
		{
			s.push_back('1');
			input = input / 2;
		}
		else
		{
			s.push_back('0');
			input = input / 2;
		}
	}

	s.push_back('1');
	reverse(s.begin(), s.end());

	return s;
}

int main()
{
	int input = 0;
	cout << "10진수를 입력해주세요. : ";
	cin >> input;

	print(solution(input));
}

d. 문제 후기

• 시간복잡도 O(logN) : 주어진 숫자에 2를 계속 나눈다.
• string에 나머지를 계속 넣어주는데, reverse를 한번 해야한다는 사실을 놓쳤다.
• 또한 0을 입력받았을 때와 같은 예외상황들을 코드로 일일히 추가하니 길어지는듯한 느낌을 받았다.
• 이런 문제는 Queue로도 풀어보면 괜찮을것 같다는 생각도 든다.

a. 문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
• 대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제약 조건

• s의 길이는 1 이상 1000이하 입니다.

b. 의사 코드

1. 처음에는 "회전" 이라는 의미를 잘 몰랐다. 회전의 의미는 각도를 활용한 회전이 아니라, "ABCD" -> "BCDA" 처럼 이동하는 회전이라는 것을 이해했다.
2. 결국 올바른 괄호쌍의 개수를 맞추는 문제이므로 string을 한번 순회하여 괄호쌍의 개수가 맞는지 먼저 확인한다.
3. 확인되었다면 여는 괄호 '(' '{' '[' 부터 시작하는 index를 찾아준다.
4. 반복자를 통해 적용되는 괄호쌍이 몇개인지 확인 한 후 숫자로 return 해준다. 

c. 문제 풀이(오답)

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(string s) 
{
    int answer = 0;
    stack<char> stack;
    
    // 1. 괄호쌍을 순회하여 올바른 괄호인지 찾기
    int open_count = 0, close_count = 0;
    for(const auto& e : s)
    {
        if(e == '(' || e == '{' || e == '[' )
        {
            open_count++;
        }
        else if(e == ')' || e == '}' || e == ']' )
        {
            close_count++;
        }
    }
    
    // 괄호쌍의 개수가 맞지 않는다면 맞는 문자열은 없다.
    if(open_count != close_count) return 0; 
    
    // 2. 여는 괄호의 index를 찾아 순회한다.
    int index = 0;
    for(int i = 0; i < s.size(); i++)
    {
        if(s[i] == '(' || s[i] == '{' || s[i] == '[' )
        {
            index = i;
            break;
        }
    }
    
    // 3. 순회하여 조건에 맞는 식들을 찾는다.
    for(auto it = s.begin() + index; it != s.end(); it++)
    {
        if(*it == '(' || *it == '{' || *it == '[' )
        {
            stack.push(*it);
        }
        else
        {
            if(*it == ')' && stack.top() == '(')
            {
                stack.pop();
            }
            else if(*it == '}' && stack.top() == '{')
            {
                stack.pop();
            }
            else if(*it == ']' && stack.top() == '[')
            {
                stack.pop();
            }
            
            if(stack.empty()) answer++;
        }
    }
    for(auto it = s.begin(); it != s.begin()+index; it++)
    {
        if(*it == '(' || *it == '{' || *it == '[' )
        {
            stack.push(*it);
        }
        else
        {
            if(*it == ')' && stack.top() == '(')
            {
                stack.pop();
            }
            else if(*it == '}' && stack.top() == '{')
            {
                stack.pop();
            }
            else if(*it == ']' && stack.top() == '[')
            {
                stack.pop();
            }
            
            if(stack.empty()) answer++;
        }
    }
    
    return answer;
}

d. 문제 후기

//////////////////////////////정답코드

#include <string>
#include <vector>
#include <unordered_map>
#include <stack>

using namespace std;

unordered_map<char, char> bracketPair = {{')', '('}, {'}', '{'}, {']', '['}};

bool isValid(string& s, int start)
{
    stack<char> stk;
    unsigned int sz = s.size();
    
    for(int i = 0; i < sz; i++)
    {
        char ch = s[(start + i) % sz];
        
        if(bracketPair.count(ch))
        {
            if(stk.empty() || stk.top() != bracketPair[ch]) return false;
            stk.pop();
        }
        else
        {
            stk.push(ch);
        }
    }
    
    return stk.empty();
}

int solution(string s) 
{
    int answer = 0;
    int n = s.size();
    
    for(int i = 0; i < n; i++)
    {
        answer += isValid(s,i);
    }
    return answer;
}

• 내가 생각한 sudo코드에는 오류가 있어 책에 있는 정답을 보고 풀었다. (정답률 56.7%)
• 왜 오답이 나왔는지는 3.에서 stack에서 empty()를 확인하는 과정에서 하나 빼먹은 것이 있는듯 하였다.
• 책에서는 unordered_map을 이용하여 풀었는데, unordered_map의 key값과 value를 이용하여 열린,닫힌 괄호를 표현한다는 생각이 참신해보였다.
• 다음부터는 하나의 값에 무조건 하나의 짝이 있을 때에는 map을 활용해야겠다.

a. 문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

b. 의사 코드

1. 의사코드 작성하지 않고 직관적으로 풀었습니다 ㅠㅠ..

c. 문제 풀이

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int solution(string s)
{
    int answer = 1;
    stack<char> stack;
    
    stack.push(s[0]);
    
    for (int i = 1; i < s.size(); i++)
    {
        if(!stack.empty() && s[i] == stack.top())
        {
            stack.pop();
        }
        else if(stack.empty())
        {
            stack.push(s[i]);
        }
        else if(!stack.empty() && s[i] != stack.top())
        {
            stack.push(s[i]);
        }
    }
    
    if(stack.empty()) return true;
    
    return false;
}

d. 문제 후기

• 프로그래머스 Lv.2 문제지만 stack을 사용한다면 굉장히 쉬운 문제였다.
• if문을 많이 사용하는 것은 직관적이지 못하니, if문과 for문을 자료구조로 간략하게 나타내는 것이 포인트 인 듯 하다.

a. 문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

b. 의사 코드

1. 의사코드 작성하지 않고 직관적으로 풀었습니다 ㅠㅠ..

c. 문제 풀이

#include <string>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

vector<int> solution(vector<int> a) 
{    
    vector<int> answer;
    
    for(int i = 0; i < a.size() ; i++)
    {
        int cnt = 0;
        for(int j = i+1; j < a.size(); j++)
        {
            if(a[i] <= a[j])
            {
                cnt++;
            }
            else
            {
                cnt++;
                break;
            }
        }
        answer.push_back(cnt);
    }
    return answer;
}

d. 문제 후기

• 내가 푼 답지의 시간복잡도는 O(N^2)이었고, 다른 사람들이 문제 푼 답지를 보니 stack을 사용하여 시간복잡도를O(2N)으로 푼 답지가 있었다.
• 정답은 맞추었지만, 시간복잡도 상으로 더 빠르게 풀 수 있는 답안이 있으므로 stack을 사용한 예제를 다시한번 복기하면서 한번 더 배웠다.

a. 문제 설명

문제 링크 참조

b. 의사 코드

1. 우선 인형을 담을 stack을 하나 만들어주고 moves 컨테이너를 한번씩 순회한다.
2. stack은 중간 요소 접근을 할 수 없으므로, 현재 것을 비교하는 grab과 prev 변수를 만들어 관리한다.
3. grab과 prev가 같다면 answer에 2를 더하고 같은 숫자의 인형들을 없애준다.
4. 점수를 리턴한다.

c. 문제 풀이

#include <string>
#include <stack>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) 
{
    int answer = 0;
    stack<int> stack;
    
    for(int i = 0; i < moves.size(); i++)
    {
        int grab = 0;
        int prev = stack.empty() ? false : stack.top();
        for(int j = 0; j < board.size(); j++)
        {
            if(board[j][moves[i]-1] != 0)
            {
               stack.push(board[j][moves[i]-1]);
               grab = board[j][moves[i]-1];
               board[j][moves[i]-1] = 0;
               break;
            }
        }
        
        if(!stack.empty() && grab == prev)
        {
            stack.pop();
            stack.pop();
            answer+=2;
        }
    }
    return answer;
}

d. 문제 후기

• 문제 지문은 길지만 2차원 배열과 스택에 대한 개념만 알고 있다면 비교적 쉽고 재밌는 문제였던 것 같다.
• 이번에도 2차원 배열을 사용했기 때문에, 2중 for문을 사용하여 순회하였지만 2중 for문은 O(N^2)의 시간복잡도를 가지기 때문에 항상 유의하여 사용하여야겠다.

a. 문제 설명

문제 링크 참조

b. 의사 코드

1. 우선 문제에 주어진 표와 동일하게 만들어줘야 하므로, n개의 size를 가진 vector를 만들어준다. 이 때, vector에는 처음 만들어두었던 행의 숫자를 넣어준다.
2. 되돌리기 기능을 위한 stack 컨테이너를 만들어준다.
3. 명령어를 담은 cmd를 한번씩 순회하며 조건문을 만들어 순회해준다.
4. 순회를 마치고 처음에 만들어두었던 vector의 행 숫자와 비교하며 O와 X를 string 에 리턴해준다.

c. 문제 풀이(오답)

#include <string>
#include <stack>
#include <vector>

using namespace std;

string solution(int n, int k, vector<string> cmd) 
{
    string answer = "";
    vector<int> vec;
    stack<pair<int,int>> stk;
    
    for(int i = 0; i < n; i++) vec.push_back(1); //기존 것과 비교할 vector
    
    for(int i = 0; i < cmd.size(); i++) //명령을 수행하는 순회
    {
        if(cmd[i][0] == 'U')
        {
            k-=stoi(cmd[i].substr(2,cmd[i].size()-2)); // 주어진 숫자만큼 올라가기
            if(k < 0) k = 0;
        }
        else if(cmd[i][0] == 'D')
        {
            k+=stoi(cmd[i].substr(2,cmd[i].size()-2)); // 주어진 숫자만큼 내려가기
            if (k > vec.size() - 1) k = vec.size() - 1;
        }
        else if(cmd[i] == "C")
        {
            if(k == vec.size()-1)
            {
                stk.push(make_pair(k,vec[k]));
                vec.erase(vec.begin()+k);
                k-=1;
            }
            else
            {
                stk.push(make_pair(k,vec[k]));
                vec.erase(vec.begin()+k); 
            }
        }
        else if(cmd[i] == "Z")
        {
            vec.insert(vec.begin()+stk.top().first,stk.top().second);
            stk.pop();
        }
    }
    
    for(int i = 0; i < vec.size(); i++)
    {
        answer.push_back('O');
    }
    for(int i = 0; i < stk.size(); i++)
    {
        answer.insert(answer.begin()+stk.top().first,'X');
        stk.pop();
    }
    
    return answer;
}

d. 문제 후기(정답)

• 이번 문제는 1시간동안 잡고 풀어보았으나, 틀리게 되어 어떤 곳이 잘못된 것인지 잘 몰랐다.
• 프로그래머스에서 그대로 문제를 풀자니, 디버깅이 안되어 어디서부터 잘못되었는지 확인할 수 없는게 안좋은 듯 하다.
• 오답에 있는 문제는 1~2주 후에 다시 풀어보는게 좋을듯 하다.
• 풀이 정답

#include <string>
#include <vector>
#include <stack>

using namespace std;

string solution(int n, int k, vector<string> cmd) {
   
   //❶삭제 된 행의 인덱스를 저장 
    stack<int> deleted;
   //❷ 각 행의 위아래에 있는 행의 인덱스를 저장 
    vector<int> up;
    vector<int> down;

    for (int i = 0; i < n + 2; i++) {
        up.push_back(i - 1);
        down.push_back(i + 1);
    }
  //❸ 임시공간을 고려한 현재위치 
  k++;

  //❹ 주어진 명령어를 순회  
  for (int i = 0; i < cmd.size(); i++) {
        //❺ 현재 위치를 삭제하고 그 다음 위치로 이동
        if (cmd[i][0] == 'C') {
            deleted.push(k);
            down[up[k]] = down[k];
            up[down[k]] = up[k];

            if (down[k] == n + 1) k = up[k];
            else k = down[k];
        }

        //❻ 가장 최근에 삭제한 행을 복원
        else if (cmd[i][0] == 'Z') {
            int r = deleted.top();
            down[up[r]] = r;
            up[down[r]] = r;
            deleted.pop();
        } 

        //❼  현재 행을 주어진 값 만큼 위혹은 아래로 이동
        else { 
            int sz = stoi(cmd[i].substr(2));
            
            if (cmd[i][0] == 'U') {
                for (int j = 0; j < sz; j++) {
                    k = up[k];
                }
            }
                  
            else if (cmd[i][0] == 'D') {
                for (int j = 0; j < sz; j++) {
                    k = down[k];
                }
            }
        }
        
    }

    string answer;
   
    //❽ 삭제된 행의 위치에 “X”, 그렇지 않은 행의 위치에 “X” 로 표시한 문자열 반환
    answer.append(n, 'O');
    while (!deleted.empty()) {
        answer[deleted.top() - 1] = 'X';
        deleted.pop();
    }

    return answer;
}

//아래 코드는 테스트 코드 입니다.
#include <iostream>

int main()
{
    
    cout << solution(8, 2, {"D 2", "C", "U 3", "C", "D 4", "C", "U 2", "Z", "Z"}) << endl;              //OOOOXOOO
    cout << solution(8, 2, {"D 2", "C", "U 3", "C", "D 4", "C", "U 2", "Z", "Z", "U 1", "C"}) << endl;  //OOXOXOOO
    return 0;
}

a. 문제 설명

• 1번 번호표를 가진 사람 기준 시계 방향으로 K번째 사람을 없앱니다.
• 없앤 사람 다음 사람을 기준으로 하고 다시 K번째 사람을 없앱니다.

N과 K가 주어질 때 마지막에 살아 있는 사람의 번호를 반환하는 solution() 함수를 구현해주세요.

b. 의사 코드

1. 먼저 Queue를 만들어 1,2,3,4,5를 밀어넣는다.
2. Queue의 내부에 있는 개수가 1이 될 때까지, 무언가를 한다.
3. 그 무언가는 맨 앞에 있는 숫자를 1개씩 빼면서, 2번째가 아니라면 다시 밀어넣고 2번째가 되는 순간 뺀다.
4. Queue가 단 1개가 되면 이 값을 리턴한다.

c. 문제 풀이

#include<iostream>
#include<queue>

using namespace std;

int solution(int n, int k)
{
    int answer = 0;
    queue<int> que;
    
    for(int i = 1; i <= n; i++)
    {
        que.push(i);
    }
    
    int cnt = 0;
    while(que.size() != 1)
    {
        cnt++;
        int temp = que.front();
        que.pop();
        if(cnt == k)
        {
            cnt = 0;
        }
        else
        {
            que.push(temp);
        }
    }

    return que.front();
}

int main()
{
    int n = 5, k = 2;
    
    cout << "마지막 남는 수는?" << endl;
    
    cout << solution(n,k);
}

d. 문제 후기

• 시간복잡도 O(N) : 주어진 숫자를 반복 순회한다.
• pop()과 front()를 잘 활용해야 한다. 내가 뺀 숫자를 다시 집어넣는다 라는 발상은 나는 push(pop())으로 하려 했으나, pop()은 리턴값이 없으므로 temporary 변수를 하나 만들어 따로 저장해두어야 하는걸 잊지말자.

a. 문제 설명

문제 링크 참조

b. 의사 코드

1. 먼저 progresses와 speeds가 어떤 동작을 하는지 이해한다.
2. 주어진 작업들을 pair클래스를 이용하여 하나의 Queue에 밀어 넣어준다.
3. Queue가 빌 때 까지, 무언가를 한다.
4. 그 무언가는 cnt라는 변수를 이용하여, 작업 진행된지 몇 초가 지났는지 구현하고 첫번째 작업이 끝날때까지 계속 cnt변수를 올려 흘러가는 시간을 구현한다.
5. 만약, 대기중인 작업(첫번째 작업)이 끝났으면 work라는 변수를 하나 만들어 이후 대기중인 작업도 이미 끝나있으면 work의 수 만큼 어딘가에 밀어 넣는다.
6. 그 어딘가는 answer 벡터이다.

c. 문제 풀이

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds)
{
    vector<int> answer;
    queue<pair<int,int>> que;
    
    int cnt = 0;
    int work = 0;
    
    for(int i = 0; i < progresses.size(); i++)
    {
        que.push(make_pair(progresses[i],speeds[i]));
    }
    
    while(!que.empty())
    {
        if((que.front().first + que.front().second * cnt) >= 100 )
        {
            work++;
            que.pop();
            continue;
        }
        
        cnt++;
        
        if(work > 0)
        {
            answer.push_back(work);
            work = 0;
        }
    }
    
    if(work > 0) answer.push_back(work);
    work = 0;
    
    return answer;
}

d. 문제 후기

• 시간복잡도 O(N) : 주어진 문자열을 무작위의 숫자동안 반복 순회한다.
• 예제에 주어진  progresses 와 speed 처럼 쌍으로 주어지는 변수가 있다면, 일단 pair 클래스로 묶어 두는 것이 가독성이 참 좋은것 같다고 느꼈다.

a. 문제 설명

문제 링크 참조

b. 의사 코드

1. 일단 goal을 순회한다.
2. card1과 card2는 순차적으로 처리해야 하므로, vector가 아닌 queue로 초기화 해준다.
3. goal을 순회할 때, card1과 card2에 똑같은 문자열이 있는지 조건문을 걸어 비교한다.
4. 계속 진행하다가 문장을 만들 수 없다면 no를 리턴한다.
5. 계속 진행이 되어 문장을 만들었다면 yes를 리턴한다.

c. 문제 풀이

#include <string>
#include <queue>
#include <vector>

using namespace std;

string solution(vector<string> cards1, vector<string> cards2, vector<string> goal) 
{
    string answer = "";
    queue<string> que1;
    queue<string> que2;
    
    for(auto& e : cards1) que1.push(e);
    for(auto& e : cards2) que2.push(e);

    for(int i = 0; i < goal.size(); i++)
    {
        if(goal[i] == que1.front())
        {
            que1.pop();
        }
        else if(goal[i] == que2.front())
        {
            que2.pop();
        }
        else if(goal[i] != que1.front() && goal[i] != que2.front())
        {
            return "No";
        }
    }
    return "Yes";
}

d. 문제 후기

• 시간복잡도 O(N) : 주어진 vector<string>을 Queue의 size만큼 순회한다.
• vector<string> 을 queue<string>으로 복사하는 과정에서 순회를 한번씩 해야하기 때문에 이 과정이 뭔가 부자연스럽게 느껴졌습니다.

a. 문제 설명

문제 링크 참조

b. 의사 코드

1. 먼저 words를 순회한다.
2. 순회하면서, 이전 단어를 수집할 vector<string> 자료형을 만들어준다.
3. 이전단어를 수집하며, 이전에 나왔던 단어인지, 끝말잇기의 조건에 부합하는지 확인한다.
4. 만약 조건과 틀릴 경우 num 변수를 하나 선언하여 몇번째에 틀렸는지 기록해둔다.
5. 기록된 숫자를 바탕으로, 번호와 차례수를 기록하거나 0을 리턴한다.

c. 문제 풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(int n, vector<string> words)
{
    vector<int> answer;
    vector<string> prev_words;

    int num = 0;

    for (int i = 0; i < words.size(); i++)
    {
        for (int j = 0; j < prev_words.size(); j++) //이전 단어가 나왔는지 확인
        {
            if (words[i] == prev_words[j])
            {
                num = i;
                break;
            }
        }
        
        if(!prev_words.empty() && prev_words.back().back() != words[i].front()) //이전 맨 끝글자와, 첫번째 
        {
            num = i;
            break;
        }
        
        prev_words.push_back(words[i]);
    }

    if (num == 0)
    {
        answer.push_back(0);
        answer.push_back(0);
    }
    else
    {
        answer.push_back((num % n) + 1);
        answer.push_back(num / n + 1);
    }

    return answer;
}

d. 문제 후기

• 시간복잡도 O(n(n-1)) : 주어진 문자열을 순회하며, 이전 것과 계속 비교한다.
• 정답률 90%라서 굉장히 아깝다고 생각되는 문제이다. 아직 해결방법을 찾진 않았지만 아마 스택/큐를 사용하지 않아 발생한 문제라고 생각되며, 다른 분들의 풀이를 보면서 1주 뒤에 또 풀 계획이다.

https://www.youtube.com/watch?v=HraOg7W3VAM

개발자라면 꼭 알아야 할 Hash Table의 모든 것 - 노마드코더

https://www.youtube.com/watch?v=X9Ty-FmHWqY

C++ STL, 해시 맵, unordered map  -  코드없는 프로그래밍

https://www.youtube.com/watch?v=MsDz50o3jHY

STL 해시 셋, std::unordered_set  -  코드없는 프로그래밍