씅의 기록하는 개발노트

문제출처

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

문제풀이

1. ",{" 기준으로 문자열을 잘라 집합을 구한 후 집합의 크기를 기준으로 정렬한다.
2.  i번째 집합에 속해있는 숫자묶음을 추출한뒤 answer 리스트에 없는 숫자만 추가해주면 된다.


c++로 풀면 꽤나 소스도 길어지고 빡빡했을거 같았다. 왜냐하면 숫자가 아닌 문자들을 다 제외하는 로직을 구현을 시작해야 해서 이참에 파이썬을 한번 써봤다.
왜 문자열은 파이썬을 사용하면 금방 풀 수 있다고 하는지 느꼈다.
문자열 문제에 항상 힘들어했는데 파이썬을 애용해봐야겠다

소스코드

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%ED%8A%9C%ED%94%8C.py

import re
 
def solution(s):
    answer = [] # 정답
    numberSet = s.split(',{') # 집합을 구함
    numberSet.sort(key = len) # 집합 크기를 기준으로 정렬
 
    for i in numberSet :
    	number = re.findall("\d+", i) # 숫자묶음을 추출
    	for j in number :
    		if int(j) not in answer :
    			answer.append(int(j))
    return answer

문제출처

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

문제풀이

완전탐색 문제인데 약간 생각할 부분이 있었다. n의 범위가 50만까지인데 채널은 무한이기 때문에 뒤에서 탐색하는 경우 버튼을 더 적게 누를수도 있기 때문이다. 또 숫자버튼을 누르고 + 또는 -버튼 1개만 계속 눌러야 한다. 왜냐하면 +버튼을 누르다 -버튼을 누르고 다시 +버튼을 누르면 중복이 발생하기 때문에 최소값이 될 수 없기 때문이다.

이후 단순 구현만 해주면 된다.

소스코드

https://github.com/sw93/algorithm/blob/master/BOJ_PS/BOJ_1107/boj1107.cpp

#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
bool brokenButton[10];
 
// 숫자버튼을 누른 채널으로 이동 가능한지 확인하는 함수
bool checkButton(int channel) {
	if (channel == 0) {
		if (brokenButton[0]) return false;
		else return true;
	}
	while (channel) {
		if (brokenButton[channel % 10]) return false;
		else channel /= 10;
	}
	return true;
}
 
// checkButton을 통과한 채널의 자릿수를 구하는 함수
int getChannelDigit(int channel) {
	int ret = 0;
	if (channel == 0) return 1;
	while (channel) {
		channel /= 10;
		ret++;
	}
	return ret;
}
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	int buttonNumber;
	for (int i = 0; i < m; i++) {
		cin >> buttonNumber;
		brokenButton[buttonNumber] = 1;
	}
 
	int ans = 987654321;
 
	// 뒤에서 탐색하는게 더 효과적인 경우도 있으므로 n의 범위를 2배 늘림
	// 예를 들어 6버튼만 안고장나고 60만번 채널로 이동하고 싶은 경우
	// 초기 100번 채널에서 +버튼만 누르는 것 보다 666,666채널에서 -버튼을 누르는 횟수가 더 적음
	for (int i = 0; i <= 1000000; i++) {
		int channel = i;
		if (checkButton(channel)) {
 
			// 숫자버튼을 눌러 이동할때 필요한 자릿수
			int digit = getChannelDigit(channel);
 
			// 숫자버튼 이동과 +버튼 또는 -버튼 클릭의 합을 비교
			ans = min(ans, digit + abs(n - channel));
		}
	}
 
	cout << min(ans, abs(n - 100));
	return 0;
}

문제 출처

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

문제 풀이

모든 경우의 수를 다 탐색하는 문제다. 위치마다 4방향 탐색을 해도 되지만 위쪽과 왼쪽은 조금만 생각해보면 중복되는 처리임을 알 수 있다.

시간 복잡도는 사탕의 위치를 바꾸는 데 2방향(오른쪽, 아래)과 n의 크기로 구하는데 2 X 50 X 50 , 최대 개수를 구하는데는 50 X 50이다. 따라서 2 X 50^4 = 12,500,000으로 1초 안에 풀이가 가능하다.

즉 O(N^4)의 시간 복잡도를 가진 이 알고리즘은 N이 50이하로 작게 제한되어 있기 때문에 완전 탐색을 해도 충분히 풀이할 수 있다고 판단했다.

소스 코드

https://github.com/sw93/algorithm/blob/master/BOJ_PS/BOJ_3085/boj3085.cpp

#include <iostream>
#include <algorithm>
using namespace std;
int n;
char map[50][50];
void init() {
	cin >> n;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> map[y][x];
		}
	}
}
int eatCandy() {
	int ret = 1;
 
	// 열 체크
	for (int y = 0; y < n; y++) {
		int count = 1;
		for (int x = 1; x < n; x++) {
			if (map[y][x] == map[y][x - 1]) count++;
			else count = 1;
			ret = max(count, ret);
		}
	}
 
	// 행 체크
	for (int x = 0; x < n; x++) {
		int count = 1;
		for (int y = 1; y < n; y++) {
			if (map[y][x] == map[y - 1][x]) count++;
			else count = 1;
			ret = max(count, ret);
		}
	}
 
	return ret;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	init();
	int ans = 0;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
 
			// 오른쪽 탐색
			if (x + 1 < n) {
				swap(map[y][x], map[y][x + 1]);
				ans = max(ans, eatCandy());
				swap(map[y][x], map[y][x + 1]);
			}
 
			// 아래쪽 탐색
			if (y + 1 < n) {
				swap(map[y][x], map[y + 1][x]);
				ans = max(ans, eatCandy());
				swap(map[y][x], map[y + 1][x]);
			}
		}
	}
	cout << ans;
	return 0;
}