씅의 기록하는 개발노트

문제출처

https://programmers.co.kr/learn/courses/30/lessons/17683

문제풀이

문제에서 주어진 조건대로 문자열 처리를 하고 구현하면 되는 문제다. 여기서 핵심은 #이 붙은 문자 처리 방법이라고 생각한다. 본인은 #이붙은 문자를 convertSound(String m) 메서드를 통해 소문자로 치환한뒤 구현했다. 또한 나중에 악보를 생성할때를 생각해서 곡의 재생시간을 구할때 단위를 분으로 통일했다.

이 문제는 오해의 소지가 있다고 생각한다. 지문에서 `(None)`을 리턴한다고 했는데 실제로는 `(None)`이 아니라 (None)을 리턴해줘야 하기 때문이다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EB%B0%A9%EA%B8%88%EA%B7%B8%EA%B3%A1.java

class Solution {

    // #이 붙은 음을 소문자로 치환
    private String convertSound(String m) {
        m = m.replaceAll("C#", "c");
        m = m.replaceAll("D#", "d");
        m = m.replaceAll("F#", "f");
        m = m.replaceAll("G#", "g");
        m = m.replaceAll("A#", "a");
        
        return m;
    }
    
    // 곡의 재생시간을 분으로 환산
    private int getRunningTime(String startInfo, String endInfo) {
        int runningTime = 0;
        int startHour = Integer.parseInt(startInfo.split(":")[0]);
        int startMinute = Integer.parseInt(startInfo.split(":")[1]);
        int endHour = Integer.parseInt(endInfo.split(":")[0]);
        int endMinute = Integer.parseInt(endInfo.split(":")[1]);
        
        return (endHour - startHour) * 60 + (endMinute - startMinute);
    }
    
    // 재생 시간만큼 재생해 악보를 만듬
    private String playMusic(String sound, int runningTime) {
        StringBuilder sb = new StringBuilder();
        int soundLength = sound.length();
        for (int i=0; i<runningTime; i++) {
            sb.append(sound.charAt(i % soundLength));
        }
        return sb.toString();
    }
    
    public String solution(String m, String[] musicinfos) {
        String answer = "(None)";
        m = convertSound(m);
        
        int maxRunningTime = 0;
        for (String info : musicinfos) {
            String[] musicInfo = info.split(",");
            int runningTime = getRunningTime(musicInfo[0], musicInfo[1]);
            String musicName = musicInfo[2];
            String sound = convertSound(musicInfo[3]);
            
            // 곡 정보를 재생해서 만든 악보
            String music = playMusic(sound, runningTime);
            
            // 정보를 통해 만든 악보가 기억한 악보와 다르다면 제외
            if (!music.contains(m)) continue;
            
            // 악보가 같은경우 재생시간이 긴 제목을 반환
            if (runningTime > maxRunningTime) {
                answer = musicName;
                maxRunningTime = runningTime;
            }
        }
        return answer;
    }
}

문제출처

https://programmers.co.kr/learn/courses/30/lessons/12977

문제풀이

재귀 함수를 이용해 숫자의 합을 구한뒤 소수 판별을 해주면 되는 간단한 문제

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%86%8C%EC%88%98%20%EB%A7%8C%EB%93%A4%EA%B8%B0.cpp

#include <vector>
#include <cmath>
using namespace std;
int ans = 0;
bool checkPrime(int number) {
    if (number == 1) return false;
    if (number == 2) return true;
    for (int i=2; i<=sqrt(number); i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}
void go(vector<int> nums, int startIdx, int depth, int sum) {
    if (depth == 3) {
        if (checkPrime(sum)) {
            ans++;
        }
        return;
    }
    for (int i=startIdx; i<nums.size(); i++) {
        go(nums, i+1, depth+1, sum+nums[i]);
    }
}
int solution(vector<int> nums) {
    go(nums, 0, 0, 0);
    
    return ans;
}

문제 출처

https://programmers.co.kr/learn/courses/30/lessons/43164

문제 풀이

dfs로 풀이했는데 전체 탐색을 중간에 멈추는 방법을 생각하지 못했다. 그래서 탐색할 수 있는 전체 경로가 출력되서 자꾸 테스트 케이스도 통과 못하는 경우가 발생했다.
생각한 해결책은 2차원 벡터를 만들어 기저조건일 때 2차원 벡터에 경로를 넣어주는 것이다. 이후 전체 탐색이 완료되면 정렬한뒤 가장 앞에 있는 경로를 return하면 된다.
dfs탐색은 보통 알고 있는 방법대로 진행했는데 탈출 조건이나 정답을 return하는게 더 어려웠던 문제.

소스 코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C.cpp

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<bool> visit;
vector<string> path;
vector<vector<string>> answer;
void getTravelPath(vector<vector<string>> &tickets, string from, int depth) {
	if (tickets.size() == depth) {
		answer.push_back(path);
		return;
	}

	for (int i=0; i<tickets.size(); i++) {
		if (visit[i] || from != tickets[i][0]) continue;
		visit[i] = 1;
		path.push_back(tickets[i][1]);
		getTravelPath(tickets, tickets[i][1], depth+1);
		path.pop_back();
		visit[i] = 0;
	}
}
vector<string> solution(vector<vector<string>> tickets) {
    visit.resize(tickets.size(), 0);
    path.push_back("ICN");
    getTravelPath(tickets, "ICN", 0);
    sort(answer.begin(), answer.end());
    return answer.front();
}

문제출처

https://programmers.co.kr/learn/courses/30/lessons/62049

문제풀이

규칙을 찾아내면 쉬운 문제. 규칙을 처음에 찾으려고 직접 종이를 접어가면서 풀이했다. 직접 종이를 접어가며 나오는 출력값을 적어가는 도중 0을 대칭으로 어떤 연산이 일어나는 걸 알아차렸다. 

즉 n이 3인경우 0 0 1 -> 0 0 1 0 0 1 1 으로 바뀌는데 0 0 1 뒤에 0을 붙이고 n이 2일때의 값을 뒤집어서 1이면 0, 0이면 1을 넣어주면 된다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%A2%85%EC%9D%B4%EC%A0%91%EA%B8%B0.cpp

#include <string>
#include <vector>

using namespace std;
/*
* 규칙 
* n = 1 -> 0
* n = 2 -> 0 0 1
* n = 3 -> 0 0 1 0 0 1 1
* n = 4 -> 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1
* n = 2 -> 3이 될때 0 0 1과 0 1 1 을 보면 기존 0은 1로 1은 0으로 바뀌고 가운데 0이 끼는 것을 알 수 있음
* n = 3 -> 4가 될때도 기존 3인 값에 0이 추가 되고 역순으로 0은 1로 1은 0으로 바뀜
*/
vector<int> solution(int n) {
    vector<int> answer;
    answer.push_back(0);
    if (n == 1) return answer;
    for (int i=2; i<=n; i++) {
        vector<int> temp = answer;
        answer.push_back(0);
        for (int j=temp.size()-1; j>=0; j--) {
            if (temp[j] == 0) answer.push_back(1);
            else if (temp[j] == 1) answer.push_back(0);
        }
    }
    
    return answer;
}

문제 출처

https://programmers.co.kr/learn/courses/30/lessons/12987

문제 풀이

정렬한뒤 풀이하는게 핵심이다. A, B벡터 모두 가장 큰수부터 비교를 해 B가 더 크다면 승점 확보와 index를 감소시킨다.

A의 가장 큰수 vs B의 가장 큰수가 붙었을때 A가 더 크다면 B에서 이길 수 있는 수가 없으므로 A의 index를 하나 감소시켜 재 비교해주면 된다.

소스 코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%88%AB%EC%9E%90%20%EA%B2%8C%EC%9E%84.cpp

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    int aIdx = A.size()-1;
    int bIdx = B.size()-1;
    while (1) {
        if (aIdx < 0) break;
        if (A[aIdx] < B[bIdx]) {
            bIdx--;
            answer++;
        }
        aIdx--;
    }
    
    return answer;
}

문제 출처

programmers.co.kr/learn/courses/30/lessons/60059

문제 풀이

전체탐색과 2차원 배열을 다룰 수 있는지 묻는 문제 입니다.

자물쇠에 키를 대조할때 겹치면 안되나 키가 자물쇠의 범위를 벗어나도 된다는 것이 핵심입니다. 
즉 키의 (0,0) 부분이 map의 (0,0) ~ (n+m-1, n+m-1)까지 이동하며 탐색하면 됩니다.

아래 그림은 자물쇠와 키의 예시입니다.

map을 확장한뒤 map[n+2m-2][n+2m-2]의 정 중앙에 자물쇠를 두어 겹치게 한다면 전체탐색이 가능합니다.

즉 탐색을 좌측상단 열쇠위치에서 시작하고 마지막 탐색은 우측하단 열쇠 위치까지 진행하여 열쇠와 자물쇠가 적합한지 판단하는 문제입니다.

탐색한 뒤 키와 자물쇠가 중복되지 않은 것을 판별하기 위해 map에서 자물쇠 위치를 탐색할때 배열에 있는 값이 1이 아니면 false를 return합니다.

소스 코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EC%9E%90%EB%AC%BC%EC%87%A0%EC%99%80%20%EC%97%B4%EC%87%A0.cpp

#include <string>
#include <vector>
using namespace std;

void rotateKey(vector<vector<int>> &key) {
    int keySize = key.size();
    vector<vector<int>> temp = key;
    for (int y=0; y<keySize; y++) {
        for (int x=0; x<keySize; x++) {
            key[y][x] = temp[keySize-x-1][y];
        }
    }
}

bool isUnlock(int sy, int sx, vector<vector<int>> key, vector<vector<int>> map) {
    int keySize = key.size();
    int mapSize = map.size();
    
    for (int y=sy; y<sy+keySize; y++) {
        for (int x=sx; x<sx+keySize; x++) {
            map[y][x] += key[y-sy][x-sx];
        }
    }

    for (int y=keySize-1; y<mapSize-keySize+1; y++) {
        for (int x=keySize-1; x<mapSize-keySize+1; x++) {
            if (map[y][x] == 1) continue;
            return false;
        }
    }
    
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    int keySize = key.size();  
    int lockSize = lock.size(); 
    int mapSize = lockSize + (keySize-1)*2; 

    // 작업할 map생성
    vector<vector<int>> map(mapSize, vector<int>(mapSize, 0));
    for (int y=0; y<lockSize; y++) {
        for (int x=0; x<lockSize; x++) {
            map[y+keySize-1][x+keySize-1] = lock[y][x];
        }
    }
    
    // 90도씩 4번 회전
    for (int i=0; i<4; i++) {
        // key를 전체 map에 대해 탐색
        for (int y=0; y<mapSize-keySize+1; y++) {
            for (int x=0; x<mapSize-keySize+1; x++) {
                if (isUnlock(y, x, key, map)) {
                    return true;
                }
            }
        }
        rotateKey(key);
    }
    
    return false;
}

문제출처

https://programmers.co.kr/learn/courses/30/lessons/60058

문제풀이

문제에서 주어진대로 구현해주면 된다. 올바른 괄호를 체크할때 스택을 사용했다. 딱히 어려운 부분은 없고 문제를 정확히 읽고 구현해주면 되는 문제인데 u를 구할때 약간 생각이 필요했다. 문자열을 탐색하면서 '('의 개수와 ')'의 개수가 같아질 때가 u이고 나머지 문자열이 v가 된다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EA%B4%84%ED%98%B8%20%EB%B3%80%ED%99%98.cpp

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

// 올바른 괄호 문자열 체크
bool isCorrectBracket(string bracket) {
    stack<char> st;
    for (int i=0; i<bracket.size(); i++) {
        if (bracket[i] == '(') {
            st.push(bracket[i]);
        } else if (bracket[i] == ')') {
            if (st.empty()) {
                return false;
            } else {
                st.pop();
            }
        }
    }
    
    if (st.empty()) return true;
    else return false;
}

// 재귀
string go(string p) {
    // 1번
    if (p == "") {
        return p;
    }
    
    // 2번
    string u = "", v = "";
    int left = 0, right = 0;
    for (int i=0; i<p.size(); i++) {
        if (p[i] == '(') left++;
        else if (p[i] == ')') right++;
        if (left == right) {
            u = p.substr(0, i + 1);
            v = p.substr(i + 1);
            break;
        }
    }
    
    // 3번
    if (isCorrectBracket(u)) {
        return u + go(v);
    } else {    // 4번
        string ret = "(" + go(v) + ")";
        u = u.substr(1, u.size() - 2);
        for (int i=0; i<u.size(); i++) {
            if (u[i] == '(') u[i] = ')';
            else if (u[i] == ')') u[i] = '(';
        }
        return ret + u;
    }
}

string solution(string p) {
    string answer = "";
    if (isCorrectBracket(p)) return p;
    answer = go(p);
    return answer;
}

문제 출처

https://programmers.co.kr/learn/courses/30/lessons/64061

문제풀이

아마 처음 긴장을 풀어주기 위해 1번 문제로 준비한 문제가 아닐까 싶다. 이 문제에서의 핵심은 스택을 사용하는 거라 생각한다. 바구니는 아래칸부터 인형이 순서대로 쌓이는 구조이며 이는 한쪽에서만 입력이 일어남을 알 수 있다. 크레인이 인형을 뽑고나서 스택의 top과 뽑은 인형이 같다면 스택을 pop하고 정답을 2 더해주면 되는 문제이다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%ED%81%AC%EB%A0%88%EC%9D%B8%20%EC%9D%B8%ED%98%95%EB%BD%91%EA%B8%B0%20%EA%B2%8C%EC%9E%84.cpp

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

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    stack<int> s;
    for (int i=0; i<moves.size(); i++) {
        int x = moves[i] - 1;
        
        for (int y=0; y<board.size(); y++) {
            if (board[y][x] == 0) continue;

            if (!s.empty() && (s.top() == board[y][x])) {
                s.pop();
                answer += 2;
            } else {
                s.push(board[y][x]);
            }
            
            board[y][x] = 0;
            break;
        }
    }
    return answer;
}

문제출처

https://www.acmicpc.net/problem/2178

문제풀이

최단거리를 구하는 문제이므로 BFS를 사용했다. 이 문제에서 가장 중요한 거는 input이 붙어서 주어진다는 것이다. 나 같은 경우는 map에 미로 정보를 입력하고 bfs탐색시작점을 1로 시작해 탐색한 거리마다 기존 값+1을 해주는 방식으로 풀이했다.

미로의 출구는 항상 map[n-1][m-1]의 위치이기 때문에 모든 탐색을 다 한뒤 거리를 저장한 배열의 n행 m열의 값을 출력해주면 된다. 

소스코드

https://github.com/sw93/algorithm/blob/master/BOJ_PS/BOJ_2178/boj2178.cpp

#include <cstdio>
#include <queue>
using namespace std;
int n, m;
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };
int map[100][100];
int dist[100][100];
void bfs(int y, int x) {
	queue<pair<int, int> > q;
	q.push(make_pair(y, x));
	dist[y][x] = 1;

	while (!q.empty()) {
		y = q.front().first;
		x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= n || nx >= m || dist[ny][nx] != 0 || map[ny][nx] != 1) continue;

			q.push(make_pair(ny, nx));
			dist[ny][nx] = dist[y][x] + 1;
		}
	}
}
int main() {
	scanf("%d %d", &n, &m);
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			scanf("%1d", &map[y][x]);
		}
	}
	bfs(0, 0);
	printf("%d\n", dist[n - 1][m - 1]);
	return 0;
}

문제출처

https://www.acmicpc.net/problem/4963

문제풀이

DFS, BFS 2가지 그래프 탐색 알고리즘 어떤 것을 써도 풀이 가능한 문제다. 나는 BFS를 사용했는데 입력을 받는 map배열과 방문여부를 확인하는 visit배열을 사용해서 풀이했다.

단지번호붙이기 문제와 같은 유형인데 단지 4방향 -> 8방향으로 확대되었다는 것밖에 바뀐게 없다.

소스코드

https://github.com/sw93/algorithm/blob/master/BOJ_PS/BOJ_4963/boj4963.cpp

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int w, h;
const int dy[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dx[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int map[50][50];
bool visit[50][50];
void bfs(int y, int x) {
	queue<pair<int, int> > q;
	q.push(make_pair(y, x));
	visit[y][x] = 1;

	while (!q.empty()) {
		y = q.front().first;
		x = q.front().second;
		q.pop();

		for (int i = 0; i < 8; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= h || nx >= w || visit[ny][nx]) continue;
			if (map[ny][nx] == 1) {
				q.push(make_pair(ny, nx));
				visit[ny][nx] = 1;
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	while (1) {
		cin >> w >> h;
		if (w == 0 && h == 0) break;
		memset(map, 0, sizeof(map));
		memset(visit, 0, sizeof(visit));
		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				cin >> map[y][x];
			}
		}

		int landCount = 0;
		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				if (map[y][x] == 1 && visit[y][x] == 0) {
					bfs(y, x);
					landCount++;
				}
			}
		}
		cout << landCount << "\n";
	}
	return 0;
}