[문제 링크]

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

[문제 풀이]

이름 그대로 문자열을 압축하는 문제였다. 문자열 처리가 좀 귀찮은 문제였다.

압출할 수 있는 길이에 따라 압축한 문자열의 길이를 비교하여 가장 작은 문자열의 길이를 리턴하는 것이 문제이다.

INPUT OUTPUT
"aabbaccc" 7
"ababcdcdababcdcd" 9
"abcabcdede" 8
"abcabcabcabcdededededede" 14
"xababcdcdababcdcd" 17

첫 번째 예제의 문자열을 길이 1로 압축한다면 "2a2ba3c"가 되고 이 문자열의 길이가 7로 가장 작은 길이가 된다.

두 번째 예제의 문자열을 길이 2로 압축한다면 "2ab2cd2ab2cd"가 되고 이 문자열의 길이는 12이다.

두 번째 에제의 문자열을 길이 8로 압축한다면 "2ababcdcd"가 되고 이 문자열의 길이가 9로 가장 작은 길이가 된다.

그럼 여기서 우리는 압축할 수 있는 길이를 1부터 다 찾아봐야한다는 사실을 알 수 있다.

하지만 1부터 어디까지 찾아봐야할까? 위에 예제들을 보면 압축할 수 있는 길이에서 절반을 압축하는 것을 볼 수 있다. 즉, 최대로 압출할 수 있는 길이는 주어진 문자열의 절반이다.

두 번째 예제의 문자열을 다시 보자. 주어진 문자열의 길이는 16이다. 이 길이의 절반은 8이다. 여기서 8보다 큰 숫자로 압축을 시도해봤자 압축이 되지 않는다.

이제 1부터 주어진 문자열 길이의 절반까지 반복문을 돌면서 가장 짧은 길이의 압축된 문자열 길이를 찾으면 된다.

여기서 문자열을 압축하는 과정을 구현하는게 생각보다 복잡했다.

본인은 우선 처음에 압축할 수 있는 길이에 따른 기준 문자열을 정하였다.

그리고 그 다음 인덱스부터 압축할 수 있는 길이만큼을 비교 문자열로 정하였다.

기준 문자열과 비교 문자열이 같다면 카운트를 해준다.

기준 문자열과 비교 문자열이 다르다면 두 가지 경우로 나뉜다.

지금까지 카운트된 횟수가 1보다 크다면 카운트 숫자를 스트링으로 변환한 뒤 숫자와 기준 문자열을 이어 붙이고 벡터에 저장하였다.

카운트 횟수가 1이라면 숫자를 생략하라고 했기 때문에 기준 문자열만 벡터에 저장하였다. 그리고 기준 문자열을 비교 문자열로 바꿔 준다. 그리고 연속으로 같은 문자열이 나온 게 아니기 때문에 카운트는 다시 1로 초기화한다.

이렇게 반복문이 끝나면 아직 벡터에 넣지 못한 문자열이 남을 수 있다. 그래서 반복문이 끝나고 같은 로직으로 카운트가 1보다 크면 숫자 + 기준 문자열을 넣어주고 1이라면 기준 문자열만 넣어준다.

마지막으로 벡터에 저장된 문자열을 하나로 이어 붙인 뒤에 길이를 업데이트 해준다.

이 문제에서 가장 많이 틀리는 케이스는 아마 문자열의 길이가 1일 때일 것이다.

문자열의 길이가 1일 때는 예외처리를 해주어야 한다.

[소스 코드]

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

int solution(string s) {
    int size = 1000;
	string tmp;
	string tmp2;
    vector<string> v;
	int s_size = s.size();
	for (int i = 1; i <= s_size / 2; i++) {
		bool flag = true;
		tmp = s.substr(0, i);
		int cnt = 1;
		int idx = 0;
		for (int j = i; j < s.size(); j++) {
			tmp2 = s.substr(j, i);
			j += (i - 1);

			if (tmp == tmp2) {
				cnt++;
			}
			else {
				if (cnt > 1) {
					string num = to_string(cnt);
					v.push_back(num + tmp);
				}
				else {
					v.push_back(tmp);
				}
				tmp = tmp2;
				cnt = 1;
			}

		}
		if (cnt > 1) {
			string num = to_string(cnt);
			v.push_back(num + tmp);
		}
		else {
			v.push_back(tmp);
		}
		string str;
		for (int j = 0; j < v.size(); j++) {
			str += v[j];
		}

		int str_size = str.size();
		size = min(size, str_size);
		tmp = "";
		v.clear();
	}
    if(s_size == 1) return 1;
    else return size;
}

[문제 링크]

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

[문제 풀이]

2019년 카카오 개발자 겨울 인턴십 코딩 테스트 문제이다.

제목에서부터 알 수 있듯이 인형 뽑기 게임을 하는데 바구니에 인형을 넣을 때 맨 위에 있는 인형과 넣는 인형이 같으면 터진다.

문제에 그림이 주어지기 때문에 문제를 이해하는 것은 어렵지 않다.

본인은 문제 설명을 보고 바로 스택을 떠올렸다.

인형을 위에서부터 뽑는다고 했기 때문에 번호마다 하나의 스택으로 생각하면 문제를 풀기가 편할 것이라고 생각했다.

그림을 보면 1번 격자에는 위에서부터 어피치와 튜브가 있다.

1번 격자를 스택으로 본다면 처음에 튜브를 넣고 어피치를 넣었을 것이다.

2번 격자를 스택으로 본다면 처음에 프로도를 넣고 무지를 2번 넣었을 것이다.

이런 식으로 해당하는 격자를 스택으로 표현하였고, 0이 아닌 경우에만 스택에 넣었다. (0은 빈 공간)

밑에서부터 넣어줘야 하기 때문에 1번 격자의 아래서부터 탐색을 진행하였다.

여기서 인형은 숫자로 표현되었다. 1은 네오, 2는 무지, 3은 튜브, 4는 어피치, 5는 프로도다.

매개 변수로 주어지는 board를 통해 스택으로 변환하였다면 이제 moves 변수를 통해 크레인을 움직이면서 바구니에 인형을 넣어줘야 한다.

여기서 바구니 또한 같은 구조이기 때문에 스택으로 선언하였다.

moves 변수에 들어있는 번호에 해당하는 스택에서 위에 있는 인형을 뽑는다.

여기서 해당 스택이 비어있다면 아무런 일도 일어나지 않는다고 했기 때문에 이 부분을 처리해줘야 한다.

바구니에 두 개의 같은 인형이 연속으로 쌓이면 사라진다고 했기 때문에 바구니에 인형을 넣을 때마다 바구니의 위에 있는 인형과 지금 넣으려고 하는 인형이 같은지 확인해야 한다. 같으면 카운트를 2 증가시켜준다. 2를 증가시키는 이유는 이미 바구니에 있는 인형과 지금 넣으려고 하는 인형이 사라지는 것이기 때문이다.

여기서 주의해야 할 부분이 있다면 바구니가 비어있을 때는 예외처리를 해줘야 한다.

마지막으로 스택에서 꺼낸 인형을 삭제해주면 된다.

참고로 본인은 스택의 인덱스를 0부터 시작하였다.

[소스 코드]

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

int solution(vector<vector<int>> board, vector<int> moves) {
    int n = board.size();
    stack<int> s[31];
    stack<int> bucket;
    int answer = 0;
    int idx = 0;
	for (int i = 0; i < n; i++) {
		for (int j = n - 1; j >= 0; j--) {
			if(board[j][i] != 0) s[idx].push(board[j][i]);
		}
		idx++;
	}
	
	for (int i = 0; i < moves.size(); i++) {
		int loc = moves[i];
		if (s[loc - 1].empty()) continue;

		if (bucket.empty()) {
			bucket.push(s[loc - 1].top());
		}
		else {
			if (bucket.top() == s[loc - 1].top()) {
				bucket.pop();
				answer += 2;
			}
			else {
				bucket.push(s[loc - 1].top());
			}
		}
		s[loc - 1].pop();
	}
    return answer;
}

 

+ Recent posts