그로블

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

풀이

다익스트라 알고리즘을 사용해서 풀면 된다.

1. 최단거리 테이블을 생성한 뒤 시작점을 0, 다른 노드는 inf(무한)로 설정한다.

2. 방문하지 않은 노드 중에 가장 거리가 짧은 노드를 선택한다.

3. 방문한 노드를 거쳐 다른 노드로 가는 모든 비용을 계산해 테이블을 갱신한다.

4. 2-3과정을 반복한다.

5. 가장 멀리 떨어져 있는 노드의 개수를 return한다.

이 때, 2번 과정을 수행하기 위해 우선순위 큐를 사용한다. 이번 문제같은 경우는 간선에 따로 가중치가 존재하지 않지만 각자 다른 가중치가 적용될 때 우선순위 큐를 사용하면 쉽게 거리가 가장 짧은 노드를 선택할 수 있다.

import heapq

def solution(n, edge):
    #최단거리 테이블(1번부터 사용)
    distance = [float("inf")]*(n+1)
    distance[0] = 0
    #인접행렬 생성
    graph = [[] for i in range(n+1)]
    for i in edge:
        graph[i[0]].append(i[1])
        graph[i[1]].append(i[0])

    dijkstra(distance, graph)

    return distance.count(max(distance))


def dijkstra(distance, graph):
    q = []
    #시작 노드 -> 1번 / 큐: (거리, 노드)
    heapq.heappush(q, (0, 1))
    distance[1] = 0

    while q:
        #최단거리 가장 짧은 노드
        dist, now = heapq.heappop(q)
        #방문 여부 확인
        if distance[now] < dist:
            continue
        #인접 노드 방문
        for i in graph[now]:
            cost = dist + 1
            #해당 경로가 더 빠른 경우
            if cost < distance[i]:
                distance[i] = cost
                heapq.heappush(q, (cost, i))

테스트 1 〉	통과 (0.03ms, 10.2MB)
테스트 2 〉	통과 (0.02ms, 10.3MB)
테스트 3 〉	통과 (0.07ms, 10.3MB)
테스트 4 〉	통과 (0.46ms, 10.3MB)
테스트 5 〉	통과 (1.58ms, 10.5MB)
테스트 6 〉	통과 (2.68ms, 10.9MB)
테스트 7 〉	통과 (51.25ms, 17.2MB)
테스트 8 〉	통과 (48.65ms, 20.6MB)
테스트 9 〉	통과 (51.84ms, 20.7MB)

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

출처

※ 공지 - 2020년 9월 3일 테스트케이스가 추가되었습니다.

풀이

import numpy as np

def solution(N, number):
    for i in range(7):
        if np.where(func(N, number, i) == number)[0].size != 0:
          return i+1
    return -1



def calc(a, b, op):
    if op == '+':
        return a + b
    if op == '-':
        return a - b
    if op == '//':
        return a // b
    if op == '*':
        return a * b


def func(N, number, cnt):
    if cnt == 0:
        return np.array([N])

    op = ['+', '-', '//', '*']
    arr = np.array([], dtype = int)
    before = func(N, number, cnt-1)
    
    arr = np.append(arr, np.core.defchararray.add(str(N), before[before>=0].astype(str)))
    arr = np.append(arr, np.core.defchararray.add(before.astype(str), str(N)))

    arr = arr.astype(int)

    for i in op:
      arr = np.append(arr, calc(N, before, i))
      arr = np.append(arr, calc(before, N, i))
    
    arr = np.unique(arr)

    return arr

진짜 바보같은 생각을 하고 열심히 코드를 짰다. 숫자 5개를 조합하는 방법으로 1개+4개 / 4개+1개 이런 경우만 생각했는데 당연히 2개+3개 / 3개+2개 / 1개+2개+2개 등 이런 경우도 있는걸 놓치고 있었다. 문제 5, 6, 7, 8번을 다 틀려서 생각하다가 잘못된걸 찾았다.

그리고 NN 형태로 생긴 숫자는 말 그대로 원래 숫자끼리만 붙일 수 있고 (연산)숫자 / 숫자(연산)이런 형태로는 붙일 수 없는데 이것까지 생각해서 코드 짜느라 시간도 조금 더 걸렸다ㅠ

1. N을 이어붙여서만 만들 수 있는 숫자를 빈 배열에 추가한다.

2. 각 단계의 숫자를 조합해서 각 단계별로 사칙연산을 수행한다(5단계 -> 1/4, 2/3, 3/2, 4/1)

3. 한 단계가 끝날때마다 입력받은 number가 배열 안에 있는지 확인한다.

이런식으로 접근하면 아주 간단하게 풀 수 있었다. 마지막에 숫자를 1개부터 8개까지 써야되는데 7개까지만 써서 잠깐 도 막혔었다..ㅎ 중간에 리스트에 중복 제거를 해주면 속도도 크게 빨라진다.

def solution(N, number):
    
    arr = [[] for i in range(10)]
    nn = ''
    for i in range(8):
        nn += str(N)
        arr[i].append(int(nn))
        for j in range(i):
            for k in arr[j]:
                for l in arr[i-j-1]:
                    arr[i].append(k + l)
                    arr[i].append(k - l)
                    arr[i].append(k * l)
                    if l != 0:
                        arr[i].append(k // l)
        arr[i] = list(set(arr[i]))
        if number in arr[i]:
            return i+1
    
    return -1

테스트 1 〉	통과 (0.99ms, 10.6MB)
테스트 2 〉	통과 (0.03ms, 10.4MB)
테스트 3 〉	통과 (0.05ms, 10.4MB)
테스트 4 〉	통과 (18.64ms, 14.4MB)
테스트 5 〉	통과 (14.78ms, 13.2MB)
테스트 6 〉	통과 (0.21ms, 10.4MB)
테스트 7 〉	통과 (0.20ms, 10.4MB)
테스트 8 〉	통과 (17.92ms, 14.5MB)
테스트 9 〉	통과 (0.03ms, 10.4MB)

문제 설명

ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디, 생물 종, 보호 시작일, 보호 시작 시 상태, 이름, 성별 및 중성화 여부를 나타냅니다.

ANIMAL_OUTS 테이블은 동물 보호소에서 입양 보낸 동물의 정보를 담은 테이블입니다. ANIMAL_OUTS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, NAME, SEX_UPON_OUTCOME는 각각 동물의 아이디, 생물 종, 입양일, 이름, 성별 및 중성화 여부를 나타냅니다. ANIMAL_OUTS 테이블의 ANIMAL_ID는 ANIMAL_INS의 ANIMAL_ID의 외래 키입니다.

관리자의 실수로 일부 동물의 입양일이 잘못 입력되었습니다. 보호 시작일보다 입양일이 더 빠른 동물의 아이디와 이름을 조회하는 SQL문을 작성해주세요. 이때 결과는 보호 시작일이 빠른 순으로 조회해야합니다.

예시

예를 들어, ANIMAL_INS 테이블과 ANIMAL_OUTS 테이블이 다음과 같다면

ANIMAL_INS

ANIMAL_OUTS

SQL문을 실행하면 다음과 같이 나와야 합니다.

본 문제는 Kaggle의 "Austin Animal Center Shelter Intakes and Outcomes"에서 제공하는 데이터를 사용하였으며 ODbL의 적용을 받습니다.

풀이

SELECT INS.ANIMAL_ID, INS.NAME 
FROM ANIMAL_INS INS 
JOIN ANIMAL_OUTS OUTS 
ON INS.ANIMAL_ID = OUTS.ANIMAL_ID 
WHERE INS.DATETIME > OUTS.DATETIME 
ORDER BY INS.DATETIME

ANIMAL_INS 테이블과 ANIMAL_OUTS 테이블을 JOIN으로 합친 뒤 ANIMAL_INS의 DATETIME이 빠른 레이블을 찾아 정렬해주면 된다.

문제 설명

리틀 프렌즈 사천성

언제나 맛있는 음식들이 가득한 평화로운 푸드 타운. 푸드 타운에서 행복하게 사는 리틀 프렌즈들은 마을에 있는 매직 스푼을 보물처럼 보관하고 있다. 매직 스푼은 재료만 준비해서 냄비에 넣고 휘젓기만 하면 순식간에 최고의 요리로 만들어주는 신비의 아이템. 어느 날 매직 스푼을 호시탐탐 노리는 악당들이 보물을 훔쳐간다. 매직 스푼을 되찾고 다시 마을에 평화를 가져오기 위해 프렌즈의 대모험이 시작되는데...

리틀 프렌즈 사천성은 프렌즈 사천성과 유사한 게임이다. 게임은 2차원 배열에서 진행되는데, 여러 가지 무늬로 구성된 타일이 배치되어 있으며 같은 모양의 타일은 두 개씩 배치되어 있다. 게임의 목적은 배치된 모든 타일을 제거하는 것으로, 같은 모양의 타일을 규칙에 따라 제거하면 된다. 타일을 제거할 수 있는 경우는 다음과 같다.

다음 조건을 만족하는 경로가 있을 때 두 타일을 제거할 수 있다.

• 경로의 양 끝은 제거하려는 두 타일이다.
• 경로는 두 개 이하의 수평/수직 선분으로 구성되어 있고, 이들은 모두 연결되어 있다. (즉, 경로를 한 번 이하로 꺾을 수 있다)
  • 참고: 프렌즈 사천성은 경로가 세 개 이하의 선분으로 구성되어야 한다는 점이 다르다. (즉, 경로를 두 번 이하로 꺾을 수 있다)
• 경로 상에는 다른 타일 또는 장애물이 없어야 한다.

위의 배열에서 어피치 타일은 직선의 경로로 이을 수 있으므로 제거 가능하다. 라이언 타일 역시 한 번 꺾인 경로로 연결되므로 제거 가능하다. 무지 타일의 경우 다른 타일을 지나지 않는 경로는 두 번 꺾여야 하므로 제거할 수 없는 타일이며, 튜브 타일 역시 직선의 경로 사이에 장애물이 있으므로 제거 가능하지 않다.

타일 배열이 주어졌을 때, 규칙에 따라 타일을 모두 제거할 수 있는지, 그 경우 어떤 순서로 타일을 제거하면 되는지 구하는 프로그램을 작성해보자.

입력 형식

입력은 게임판의 크기를 나타내는 m과 n, 그리고 배치된 타일의 정보를 담은 문자열 배열 board로 주어진다. 이 배열의 크기는 m이며, 각각의 원소는 n글자의 문자열로 구성되어 있다. 입력되는 값의 제한조건은 다음과 같다.

• 1 <= m, n <= 100
• board의 원소는 아래 나열된 문자로 구성된 문자열이다. 각 문자의 의미는 다음과 같다.
  • .: 빈칸을 나타낸다.
  • *: 막힌 칸을 나타낸다.
  • 알파벳 대문자(A-Z): 타일을 나타낸다. 이 문제에서, 같은 글자로 이루어진 타일은 한 테스트 케이스에 항상 두 개씩만 존재한다.
  • board에는 알파벳 대문자가 항상 존재한다. 즉, 타일이 없는 입력은 주어지지 않는다.

출력 형식

해가 존재하는 경우 타일을 제거하는 순서대로 한 글자씩 이루어진 문자열을, 그렇지 않은 경우 IMPOSSIBLE을 리턴한다. 해가 여러 가지인 경우, 알파벳 순으로 가장 먼저인 문자열을 리턴한다.

예제 입출력

예제에 대한 설명

첫 번째 테스트 케이스에서 처음으로 제거 가능한 타일은 A와 C이다. 그리고 모든 가능한 경우를 나열하면 ABCD, ACBD, ACDB, CABD, CADB, CDAB이다. 이 중 알파벳 순으로 가장 먼저인 ABCD가 정답이다.

네 번째 테스트 케이스는 초기 상태에서 제거할 수 있는 타일이 없으므로 타일을 모두 제거하는 것이 불가능하다. 따라서 정답은 IMPOSSIBLE이다.

풀이

문자, x좌표, y좌표를 변수로 가지는 position 구조체를 만든 후, 문자열로 입력된 board를 set을 이용하여 알파벳을 오름차순으로 정리한다. set은 균형이진트리로 nsert 함수를 이용해 삽입된 원소들은 자동으로 정렬되기 때문에 삭제할 타일의 순서대로 바로 정렬할 수 있다. 이 때 set 내에서 사용하는 operator<이 새로 만든 position 구조체에 대해 연산을 수행할 수 없으므로 새로 정의해주어야 한다.

struct position { char c; int x, y; };

bool operator<(const position& a, const position& b) {
	return a.c < b.c;
}

string solution(int m, int n, vector<string> board) {
	string answer = "";
	int i, j, chk;
	set<position> tileList;
	

	//제거할 알파벳 타일 오름차순으로 list에 정렬
	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++) {
			if (board[i][j] >= 'A' && board[i][j] <= 'Z')
				tileList.insert(position{board[i][j], j, i});
		}
	}

BFS를 이용하여 가능한 타일을 탐색한다. 기존 BFS 코드에 두번 이상 꺾을 수 없는 제한을 걸어주면 된다. 큐에 x, y좌표 외에 direction(상/하/좌/우)값을 넣어서 확인한다.

#include <string>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
#include <cstring>

using namespace std;

struct position { char c; int y, x; };
struct q { int y, x, direction; };

bool operator<(const position& a, const position& b) {
	return a.c < b.c;
}

string search(set<position> list, int m, int n, vector<string> board) {
	queue<q> queue;
	string answer = "";
	int visit[100][100][4], dy[] = { 0,1,0,-1 }, dx[] = { 1,0,-1,0 }, tx, ty, after, before;
	bool chk, bend, possible;

	do {
		before = (int)list.size();
		for (auto it = list.begin(); it != list.end(); it++) {
			while (!queue.empty()) queue.pop();	//큐 초기화
			memset(visit, 0x7f, sizeof(visit));	//큰 값으로 visit 배열 초기화

			//첫 번째 노드 (모든 방향을 큐에 삽입, 0:우/1:하/2:좌/3:상)
			for (int i = 0; i < 4; i++) {
				visit[it->y][it->x][i] = 0;	//방향 회전 횟수: 0
				queue.push(q{ it->y, it->x, i });
			}

			chk = 0;	//같은 타일을 만났는지 확인하는 변수

			//큐에 값이 남아있고(방문하지 않은 노드 존재) 같은 타일을 만나지 않았을 때까지 반복
			while (!queue.empty() && !chk) {
				q now = queue.front();
				queue.pop();
				for (int i = 0; i < 4; i++) {
					tx = now.x + dx[i];
					ty = now.y + dy[i];
					bend = (i != now.direction);	//1: 방향이 꺾임/0: 꺾이지 않음

					//보드에서 벗어났는지 확인
					if (0 <= ty && ty < m && 0 <= tx && tx < n) {
						possible = board[ty][tx] != '*' && (board[ty][tx] == '.' || board[ty][tx] == it->c);	//막히지 않고, 빈칸이거나 같은 타일일 경우

						//보드 안에서 접근이 가능하고 두번 이상 꺾이지 않았고 방문하지 않은 노드(방문했을 시 visit direction이 작은 수로 바뀜)
						if (possible && (visit[now.y][now.x][now.direction] + bend < 2) && visit[ty][tx][i] > visit[now.y][now.x][now.direction] + bend) {
							visit[ty][tx][i] = visit[now.y][now.x][now.direction] + bend;	//방향 꺾은 횟수
							queue.push(q{ ty, tx, i });	//방문하지 않았다면 큐에 추가
							//같은 모양의 타일에 접근이 가능할 경우 각 타일을 빈칸으로 바꿈
							if (board[ty][tx] == it->c) {
								chk = 1;
								board[it->y][it->x] = '.';
								board[ty][tx] = '.';
							}
						}
					}
				}
			}
			//같은 타일을 찾은 경우 리스트에서 제거하고 다음 알파벳으로 이동
			if (chk) {
				answer += it->c;
				list.erase(it);
				break;
			}
		}

		after = list.size();

	} while (before != after);	//리스트가 줄어들지 않는 경우(불가능한 경우 + 전부 제거한 경우)

		//리스트가 비어있지 않다면 불가능한 경우
		if (!list.empty()) answer = "IMPOSSIBLE";
		return answer;
}

string solution(int m, int n, vector<string> board) {
	int i, j;
	set<position> tileList;


	//제거할 알파벳 타일 오름차순으로 list에 정렬
	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++) {
			if (board[i][j] >= 'A' && board[i][j] <= 'Z')
				tileList.insert(position{ board[i][j], i, j });
		}
	}

	return search(tileList, m, n, board);
}

모든 경우를 생각해서 코드를 짜다가 너무 길고 더러워져서 BFS 를 이용한 다른분의 코드를 참고해서 공부했다ㅠㅠ 공부 더 열심히 해야지..ㅠㅠ

테스트 1 〉	통과 (305.16ms, 4.33MB)

코드 출처

https://coloredrabbit.tistory.com/58

문제 설명

ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디, 생물 종, 보호 시작일, 보호 시작 시 상태, 이름, 성별 및 중성화 여부를 나타냅니다.

ANIMAL_OUTS 테이블은 동물 보호소에서 입양 보낸 동물의 정보를 담은 테이블입니다. ANIMAL_OUTS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, NAME, SEX_UPON_OUTCOME는 각각 동물의 아이디, 생물 종, 입양일, 이름, 성별 및 중성화 여부를 나타냅니다. ANIMAL_OUTS 테이블의 ANIMAL_ID는 ANIMAL_INS의 ANIMAL_ID의 외래 키입니다.

천재지변으로 인해 일부 데이터가 유실되었습니다. 입양을 간 기록은 있는데, 보호소에 들어온 기록이 없는 동물의 ID와 이름을 ID 순으로 조회하는 SQL문을 작성해주세요.

예시

예를 들어, ANIMAL_INS 테이블과 ANIMAL_OUTS 테이블이 다음과 같다면

ANIMAL_INS

ANIMAL_OUTS

ANIMAL_OUTS 테이블에서

• Allie의 ID는 ANIMAL_INS에 없으므로, Allie의 데이터는 유실되었습니다.
• Gia의 ID는 ANIMAL_INS에 있으므로, Gia의 데이터는 유실되지 않았습니다.
• Spice의 ID는 ANIMAL_INS에 없으므로, Spice의 데이터는 유실되었습니다.

따라서 SQL문을 실행하면 다음과 같이 나와야 합니다.

ANIMAL_IDNAME

본 문제는 Kaggle의 "Austin Animal Center Shelter Intakes and Outcomes"에서 제공하는 데이터를 사용하였으며 ODbL의 적용을 받습니다.

풀이

[MySQL]

SELECT ANIMAL_ID, NAME 
FROM ANIMAL_OUTS
WHERE NOT EXISTS 
(SELECT NULL 
FROM ANIMAL_INS 
WHERE ANIMAL_INS.ANIMAL_ID = ANIMAL_OUTS.ANIMAL_ID)

NOT EXISTS구문은 먼저 ANIMAL_OUTS 테이블에 접근해서 하나의 레코드를 가져온 뒤 해당 레코드에 대해서 NOT EXISTS 이하의 서브 쿼리를 실행하고 서브 쿼리가 존재하지 않는지를 확인한다. 이 구문을 이용하여 존재하지 않느느 ANIMAL_ID를 찾아주면 된다.

[Oracle]

SELECT ANIMAL_ID, NAME 
FROM ANIMAL_OUTS 
WHERE NOT EXISTS 
(SELECT NULL 
FROM ANIMAL_INS 
WHERE ANIMAL_INS.ANIMAL_ID = ANIMAL_OUTS.ANIMAL_ID) 
ORDER BY ANIMAL_ID

이유는 잘 모르겠지만 Oracle에서 NOT EXISTS를 쓰면 틀렸다고 나와서 ANIMAL_ID를 기준으로 정렬을 해줬더니 정답 처리가 되었다.

LEFT OUTER JOIN을 이용한 방법으로도 풀어보자.

SELECT ANIMAL_OUTS.ANIMAL_ID, ANIMAL_OUTS.NAME 
FROM ANIMAL_OUTS 
LEFT OUTER JOIN ANIMAL_INS
ON ANIMAL_INS.ANIMAL_ID = ANIMAL_OUTS.ANIMAL_ID
WHERE ANIMAL_INS.ANIMAL_ID is NULL
ORDER BY ANIMAL_OUTS.ANIMAL_ID

LEFT OUTER JOIN은 왼쪽 테이블을 기준으로 오른쪽 테이블의 레코드를 비교하여 조건이 일치하면 가져와서 JOIN하고 다르면 NULL이 표시된다. ANIMAL_OUTS 테이블을 기준으로 JOIN을 하게 되면 ANIMAL_OUTS에 있지만 ANIMAL_INS에 없는 값들은 NULL로 들어오기 때문에 없어진 기록을 찾을 수 있다.

SELECT ANIMAL_OUTS.ANIMAL_ID, ANIMAL_OUTS.NAME 
FROM ANIMAL_OUTS, ANIMAL_INS
WHERE ANIMAL_OUTS.ANIMAL_ID = ANIMAL_INS.ANIMAL_ID(+)
AND ANIMAL_INS.ANIMAL_ID IS NULL
ORDER BY ANIMAL_OUTS.ANIMAL_ID

Oracle에서 (+)를 이용해서 위와 같이 작성할 수도 있다.

문제 설명

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 "abcabcabcabc6de" 가 됩니다.
문자열을 3개 단위로 자르면 "4abcdededededede" 가 됩니다.
문자열을 4개 단위로 자르면 "abcabcabcabc3dede" 가 됩니다.
문자열을 6개 단위로 자를 경우 "2abcabc2dedede"가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

풀이

def solution(s):
    answer = len(s)
   
   #모든 경우의 수 중 가장 짧은 길이
    for i in range(1, len(s)//2+1):	
        answer = min(compress(s, i), answer)
        
    return answer

def compress(s, num):
    comstr = ''
    count = 1
    
    for i in range(0, len(s), num):
    	#같은 문자열 반복하는 경우
        if s[i:i+num] == s[i+num:i+2*num]:
            count += 1
        #다른 문자열이 나오는 경우
        else:
            if count == 1:
                comstr += s[i:i+num]
            else:
                comstr += str(count) + s[i:i+num]
                count = 1
            
    return len(comstr)

테스트 1 〉	통과 (0.04ms, 10.2MB)
테스트 2 〉	통과 (0.46ms, 10.3MB)
테스트 3 〉	통과 (0.35ms, 10.3MB)
테스트 4 〉	통과 (0.05ms, 10.3MB)
테스트 5 〉	통과 (0.00ms, 10.2MB)
테스트 6 〉	통과 (0.05ms, 10.3MB)
테스트 7 〉	통과 (0.78ms, 10.2MB)
테스트 8 〉	통과 (0.61ms, 10.2MB)
테스트 9 〉	통과 (0.88ms, 10.2MB)
테스트 10 〉	통과 (2.88ms, 10.2MB)
테스트 11 〉	통과 (0.11ms, 10.2MB)
테스트 12 〉	통과 (0.11ms, 10.2MB)
테스트 13 〉	통과 (0.20ms, 10.2MB)
테스트 14 〉	통과 (0.97ms, 10.2MB)
테스트 15 〉	통과 (0.22ms, 10.3MB)
테스트 16 〉	통과 (0.02ms, 10.2MB)
테스트 17 〉	통과 (1.40ms, 10.2MB)
테스트 18 〉	통과 (1.35ms, 10.3MB)
테스트 19 〉	통과 (1.35ms, 10.2MB)
테스트 20 〉	통과 (3.76ms, 10.3MB)
테스트 21 〉	통과 (3.23ms, 10.2MB)
테스트 22 〉	통과 (3.24ms, 10.2MB)
테스트 23 〉	통과 (3.10ms, 10.2MB)
테스트 24 〉	통과 (2.94ms, 10.2MB)
테스트 25 〉	통과 (3.21ms, 10.2MB)
테스트 26 〉	통과 (3.20ms, 10.3MB)
테스트 27 〉	통과 (3.17ms, 10.2MB)
테스트 28 〉	통과 (0.02ms, 10.2MB)

문자열을 1개 단위로 자르는 경우부터 1씩 증가시켜서 반으로 자르는 경우까지 모든 경우 중 가장 작게 압축되는 케이스를 찾는 과정을 solution 함수에서 수행했다.

문자열을 압축하는 과정은 compress라는 함수에서 하는데, 문자열과 함께 문자열을 자르는 단위(num)를 인자로 넘겨주었다. 문자열의 처음부터 끝까지 돌면서 num만큼의 간격으로 앞부분과 뒷부분이 같은지 비교하고 같으면 count를 1만큼 증가시키고 같지 않으면 압축된 문자열을 가리키는 comstr에 반복된 숫자와 문자열을 추가해준다. 이 때, count가 1이라면 숫자를 생략한다. 반복문을 다 돌면 해당 문자열의 길이를 다시 solution에 return해준다.

문제

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
• 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

입출력 예

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리, 2번 폰켓몬 한 마리, 4번 폰켓몬 한 마리를 고르면 되며, 따라서 3을 return 합니다.

입출력 예 #3
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리와 2번 폰켓몬 두 마리를 고르거나, 혹은 3번 폰켓몬 두 마리와 2번 폰켓몬 한 마리를 고르면 됩니다. 따라서 최대 고를 수 있는 폰켓몬 종류의 수는 2입니다.

풀이

C++

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

int solution(vector<int> nums)
{
    int answer = 0;
    int bring = nums.size()/2; //가지고 갈 수 있는 폰켓몬
    
    sort(nums.begin(), nums.end()); //정렬
    nums.erase(unique(nums.begin(), nums.end()), nums.end()); //중복 제거
    
    return bring > nums.size() ? nums.size() : bring; //작은 것 리턴
}

테스트 1 〉	통과 (0.01ms, 3.81MB)
테스트 2 〉	통과 (0.01ms, 3.99MB)
테스트 3 〉	통과 (0.01ms, 3.99MB)
테스트 4 〉	통과 (0.01ms, 4.34MB)
테스트 5 〉	통과 (0.01ms, 3.99MB)
테스트 6 〉	통과 (0.01ms, 3.81MB)
테스트 7 〉	통과 (0.01ms, 3.76MB)
테스트 8 〉	통과 (0.01ms, 4.35MB)
테스트 9 〉	통과 (0.02ms, 3.66MB)
테스트 10 〉	통과 (0.02ms, 3.69MB)
테스트 11 〉	통과 (0.02ms, 4.34MB)
테스트 12 〉	통과 (0.06ms, 3.97MB)
테스트 13 〉	통과 (0.06ms, 3.75MB)
테스트 14 〉	통과 (0.07ms, 3.99MB)
테스트 15 〉	통과 (0.06ms, 3.75MB)
테스트 16 〉	통과 (0.58ms, 3.99MB)
테스트 17 〉	통과 (0.63ms, 4.02MB)
테스트 18 〉	통과 (0.57ms, 4.02MB)
테스트 19 〉	통과 (0.56ms, 3.95MB)
테스트 20 〉	통과 (0.38ms, 4.08MB)

Python3

def solution(nums):
    return min(len(set(nums)), len(nums)/2);

테스트 1 〉	통과 (0.00ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.00ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.1MB)
테스트 6 〉	통과 (0.01ms, 10.2MB)
테스트 7 〉	통과 (0.01ms, 10.2MB)
테스트 8 〉	통과 (0.01ms, 10.1MB)
테스트 9 〉	통과 (0.01ms, 10.2MB)
테스트 10 〉	통과 (0.01ms, 10.2MB)
테스트 11 〉	통과 (0.01ms, 10.3MB)
테스트 12 〉	통과 (0.07ms, 10.2MB)
테스트 13 〉	통과 (0.08ms, 10.3MB)
테스트 14 〉	통과 (0.08ms, 10.4MB)
테스트 15 〉	통과 (0.05ms, 10.3MB)
테스트 16 〉	통과 (0.80ms, 11.1MB)
테스트 17 〉	통과 (0.63ms, 10.6MB)
테스트 18 〉	통과 (0.54ms, 10.7MB)
테스트 19 〉	통과 (0.50ms, 10.3MB)
테스트 20 〉	통과 (0.38ms, 10.4MB)

간단하게 가지고 갈 수 있는 폰켓몬 수와 중복을 제거한 폰켓몬 수(폰켓몬의 종류)를 비교해서 더 작은 값을 return 해주면 된다.

가지고 갈 수 있는 폰켓몬 수가 폰켓몬의 종류보다 적다면 최대한 많은 폰켓몬을 가지고 가야 하기 때문에 각각 다른 폰켓몬을 가지고 갈 것이므로 N/2마리가 그대로 최댓값이 된다. 반대로 폰켓몬의 종류가 더 적다면 아무리 많이 가져간다고 해도 종류의 수를 넘을 수 없기 때문에 폰켓몬의 종류가 최댓값이 된다.

C++에서는 sort, erase, unique 함수를 이용해 중복을 제거한 뒤 삼항 연산자를 이용해서 작은 값을 return했고, Python에서는 중복을 허용하지 않는 set으로 자료형을 바꾼 뒤 길이를 비교하여 작은 값을 return하였다.

gluebyte님 단축어

트위터 공유하기 -> 단축어 사용해서 저장하면 됨

www.icloud.com/shortcuts/e23c068d24f949679fc255fd0a53d9c8

gluebyte.tumblr.com/post/183649601805

문제

임의의 문장을 입력받아 각 단어별로 나눈 후에 단어들의 중복되는 개수를 구하는 프로그램을 작성하시오.

<처리조건>
(1) 입력된 스트링은 글자의 제한은 없다. 즉 공백이나 ', ' 등도 입력으로 들어 올 수 있다.
(2) 입력된 문장에서 각 단어사이의 구분은 공백으로 한다.
(3) 단어에는 공백을 제외한 단어들만이 포함된다.

입력형식

임의의 문장을 입력받는다.(문장의 길이는 200 이하)

하나의 결과가 나온 후에도 계속 새로운 입력을 받다가, "END"가 입력되면 프로그램을 종료한다. (문장의 개수를 30을 넘지 않는다.)

출력형식

각 문장 단위로 단어들의 발생 빈도를 오름차순 크기(아스키코드)순으로 출력한다.

<코드>

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct word{
	char name[100];
	int freq;
}WORD;

typedef struct words{
	int len;
	int capacity;
	WORD *data;
}WORDS;

int compare( const void *n1, const void *n2)
{
	return strcmp((const char *)n1, (const char *)n2);
}

void destroy_words(WORDS *list)
{
	free(list->data);
	list->len = 0;
	list->capacity = 0;

	free(list);
}	

void input(char *name, WORDS *list)
{
	int check = 0;
	
	for(int j=0; j<list->len; j++)
	{
		if(!strcmp(name, list->data[j].name))
		{
			check = 1;
			list -> data[j].freq++;
			break;
		}	
	}
	
	if(!check)
		{
		//full memory
		if(list->capacity == list->len)
		{
			list->data = (WORD*)realloc(list->data, list->capacity * 2 * sizeof(WORD));
			list->capacity *= 2;
		}
		
		strcpy(list->data[list->len].name, name);
		list->data[list->len++].freq = 1;
	}
}

int main()
{
	char arr[200];
	char *ptr;
	
	while(1)
	{
		scanf(" %[^\n]s", arr);
		
		if(!strcmp("END", arr))
			break;
		
		WORDS *list = (WORDS *)malloc(sizeof(WORDS));
	
		list->len = 0;
		list->capacity = 1;
		list->data = (WORD *)malloc(list->capacity*(sizeof(WORD)));
		
		ptr = strtok(arr, " ");

		while (ptr != NULL)
		{
			input(ptr, list);
			ptr = strtok(NULL, " ");
		}
		
		qsort(list->data, list->len, sizeof(WORD), compare);
	
		for(int i=0; i<list->len; i++)
		{
			printf("%s : %d\n", list->data[i].name, list->data[i].freq);
		}
	
		destroy_words(list);
	}
	
	
	
	return 0;
}

문제

최근 농부 창호에게서 메시지를 암호화(encryption)에 대해서 배운 소들은 너무나 신이 나있다. 

그들은 다른 농장의 소들과 미팅을 할 때 은밀한 메시지를 사용할 경우 이 방법을 사용할 수 있을 것이라고 생각했다. 

소들이 사용하는 암호화 방법은 복잡한 DES 혹은 BlowFish 와 같은 좋은 방법이 아니고 단순히 치환 하는 암호화 기법이다.

소들의 경우 복호화(암호를 해독함)하는 시간이 오래 걸리기 때문에, 

소들과 대화를 할 수 있는 당신에게 복호화 키와 암호 문자를 입력으로 받아 원문을 구하는 프로그램을 구현 해주기를 요청했다.

복호화 키는 26개의 소문자로 주어지며, a,b,c,d... 를 순서대로 복호화 키 문자로 대치한다는 것을 뜻한다.

예를 들어, 복호화 키가 "eydbkmiqugjxlvtzpnwohracsf" 와 같이 주어진다고 하자, 

그러면 이는 다음과 같다 - a 문자는 e, b 문자는 y, ..., z 문자는 f로 바꿔 준다.

암호화 된 문자는 대소문자 혹은 공백이 올수 있고 대문자는 대문자로 소문자는 소문자로 치환 규칙에 맞게 출력하고, 공백문자는 그대로 출력한다.

입력형식

첫 줄에는 복호화 키가 26개의 소문자로 주어지고, 다음 줄에는 암호화 된 문자가 최대 80 문자로 입력된다.

출력형식

암호화 된 문장을 복호화 시켜 원문을 출력한다.

<코드>

#include <stdio.h>
#include <string.h>

int main()
{
	char key[27];
	char enc[81], dec[81];
	int i;
	
	scanf(" %s %[^\n]s", key, enc);
	
	for(i=0; i<strlen(enc)-1; i++)
	{
		if(enc[i] == ' ')
		{
			dec[i] = ' ';
			continue;
		}
		else if(enc[i]>='A'&&enc[i]<='Z')
			dec[i] = key[enc[i]-'A']-0x20;
		else if(enc[i]>='a'&&enc[i]<='z')
			dec[i] = key[enc[i]-'a'];
	}
	dec[i] = 0;
	
	printf("%s\n", dec);
	
	return 0;
}