내일은 알고리즘

https://leetcode.com/problems/isomorphic-strings/

상당히 낯선 단어인데 Isomorphic은 동형사상이라는 뜻이라고 합니다.

Isomorphic String은 두 String의 형태가 닮아있는 것을 말하는데요. 예를 들어 glass와 shell이 동형관계입니다.

두 단어는 생김새가 전혀 다르지만 알파벳이 등장하는 순서대로 번호를 매기면 12344, 12344로 구조가 같음을 알 수 있습니다.

반대로 banana와 canada는 단어 생긴건 비슷하지만 번호를 매기면 123232와 123242로 차이가 있습니다.

문제에서 주어진 String을 앞에서부터 읽어가며 처음 만나는 알파벳인 경우 Dictionary에 Index값을 넣어주고, 이미 만났던 알파벳인 경우 Index값을 비교해 같은 구조인지 체크해줬습니다.

물론 알파벳의 내용은 다르므로 Dictionary를 두개 만들어서 따로 저장했습니다.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        sDict = {}
        tDict = {}
        idx = 0

        for i in range(0,len(s)):
            if(not (s[i] in sDict) and not (t[i] in tDict)):
                sDict[s[i]] = idx
                tDict[t[i]] = idx
                idx += 1
            elif(s[i] in sDict and t[i] in tDict):
                if(sDict[s[i]] != tDict[t[i]]):
                    return False
            else: 
                return False
        
        return True

input = [["egg","add"],["foo","bar"],["paper","title"]]

for i in input:
    print(Solution().isIsomorphic(i[0],i[1]))

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

BFS + 비트마스킹으로 풀이하는 문제입니다.

벽부수기 같은 문제처럼 visited 체크를 열쇠의 소유상태에 따라 다르게 해줘야 합니다.

해당 부분을 비트마스킹 Integer로 저장하거나 배열을 통해 저장하거나 편한 방법으로 풀이할 수 있습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class q1194_BOJ_달이차오른다가자 {
	static StringTokenizer st;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int R, C;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		char[][] map = new char[R][C];
		boolean[][][] visited = new boolean[R][C][64];

		Queue<Player> queue = new LinkedList<>();

		for (int r = 0; r < R; r++) {
			String input = br.readLine();
			for (int c = 0; c < C; c++) {
				map[r][c] = input.charAt(c);
				if (map[r][c] == '0') {
					queue.offer(new Player(r, c, 0));
					visited[r][c][0] = true;
					map[r][c] = '.';
				}
			}
		}

		int time = 0;
		boolean flag = false;

		loop: while (!queue.isEmpty()) {
			int size = queue.size();
			time++;
			while (size-- > 0) {
				Player p = queue.poll();
				int x = p.x;
				int y = p.y;
				int key = p.key;

				for (int i = 0; i < 4; i++) {
					int nX = x + delta[i][0];
					int nY = y + delta[i][1];
					if (isIn(nX, nY) && map[nX][nY] != '#' && !visited[nX][nY][key]) {
						if (map[nX][nY] == '.') {
							queue.offer(new Player(nX, nY, key));
							visited[nX][nY][key] = true;
						} else if (map[nX][nY] == '1') {
							flag = true;
							break loop;
						} else if (map[nX][nY] < 'a' && canOpen(map[nX][nY], key)) {
							queue.offer(new Player(nX, nY, key));
							visited[nX][nY][key] = true;
						} else if (map[nX][nY] >= 'a') {
							int nKey = (1 << (map[nX][nY] - 'a')) | key;
							queue.offer(new Player(nX, nY, nKey));
							visited[nX][nY][nKey] = true;
						}
					}
				}
			}

		}

		if (flag) {
			System.out.println(time);
		} else {
			System.out.println("-1");
		}
	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < R && 0 <= y && y < C) {
			return true;
		}
		return false;
	}

	static boolean canOpen(char door, int key) {
		if ((1 << (door - 'A') & key) > 0) {
			return true;
		}
		return false;
	}

	static class Player {
		int x, y, key;

		public Player(int x, int y, int key) {
			this.x = x;
			this.y = y;
			this.key = key;
		}
	}
}

https://leetcode.com/problems/find-pivot-index/

좌측합과 우측합을 같게 만드는 중심을 찾는 꽤 재밌는 문제였습니다.

슬라이딩 윈도우와 비슷한 느낌으로 구현했는데, 좌측합이 0, 우측합이 모든 누적합인 상태로 시작해서 이번 턴에 중심으로 테스트하는 값을 우측합에서 빼고 이전 턴에 테스트한 값을 좌측합에 더하는 식으로 구현했습니다.

testcase 1번값의 풀이진행을 그림으로 나타내면 아래와 같습니다.

class Solution:
    # def pivotIndex(self, nums: List[int]) -> int:
    def pivotIndex(self, nums: list) -> int:
        pivot = -1
        idx = 0
        leftSum = 0
        rightSum = self.getRightSum(nums)

        while(idx < len(nums)):
            rightSum -= nums[idx]
            if(idx > 0):
                leftSum += nums[idx-1]
            
            if(leftSum == rightSum):
                pivot = idx
                break
            idx += 1

        return pivot
    
    def getRightSum(self, nums:list):
        rightSum = 0
        for i in nums:
            rightSum += i

        return rightSum


input = [[1,7,3,6,5,6],[1,2,3],[2,1,-1]]
for i in input:
    print(Solution().pivotIndex(i))

https://leetcode.com/problems/running-sum-of-1d-array/

LeetCode의 14일짜리 코스를 시험삼아 시작해봤습니다.

하루에 2문제씩 14일간 28문제를 푸는 코스네요.

배열의 누적합 문제입니다.

딱히 설명할 부분은 없는 간단한 문제였습니다.

LeetCode에서 주어지는 Example 코드가 Python 3.5 이상에서만 돌아가는 코드여서 주석처리 했습니다.

class Solution:
    # def runningSum(self, nums: List[int]) -> List[int]:
    def runningSum(self, nums: list) -> list:
        sum = 0
        answer = []
        for i in nums:
            sum += i
            answer.append(sum)
        
        return answer


input = [[1,2,3,4],[1,1,1,1,1],[3,1,2,10,1]]
for i in input:
    print(Solution().runningSum(i))

https://leetcode.com/problems/roman-to-integer/

최근에 추천받았던 LeetCode라는 외국 PS사이트입니다.

디자인도 예쁘고 개인이 사용한 자료구조, 알고리즘 통계나 문제 풀이 코스같이 특정 기간동안 스케쥴 관리 해주는 기능이 참 좋아보이네요.

LeetCode는 Easy - Medium - Hard 3단계로 문제의 난이도가 구분되어 있습니다. 회원가입하자마자 문제 리스트를 추천받았는데 가장 위에 있던 문제입니다. 

문제 자체는 문자열을 조건에 맞추어 숫자로 변환하기만 하면 되는데요, if문을 중첩하거나 switch-case를 쓰거나 여러가지 방법이 있을겁니다.

Python의 Dictionary를 이용해서 두가지 방법으로 풀었는데요.

첫 코드는 if문을 여러개 쪼개서 조건을 구분한 코드인데 통과는 되었지만 코드라인도 길고 깔끔하지 않아서 Dictionary를 좀 더 사용하는 코드로 다시 작성했습니다.

class Solution(object):
    def romanToInt(self, s: str) -> int:
        sum = 0
        i = 0
        symbol = {'I': 1, 'V': 5,'X': 10,'L': 50,'C': 100,'D': 500,'M': 1000}

        while(i < len(s)):
            if( i < len(s) - 1) :
                if(s[i] == 'I'):
                    if(s[i+1] == 'V'):
                        sum += 4
                        i += 1
                    elif(s[i+1] == 'X'):
                        sum += 9
                        i += 1
                    else : 
                        sum += symbol[s[i]]
                elif(s[i] == 'X'):
                    if(s[i+1] == 'L'):
                        sum += 40
                        i += 1
                    elif(s[i+1] == 'C'):
                        sum += 90
                        i += 1
                    else : 
                        sum += symbol[s[i]]
                elif(s[i] == 'C'):
                    if(s[i+1] == 'D'):
                        sum += 400
                        i += 1
                    elif(s[i+1] == 'M'):
                        sum += 900
                        i += 1
                    else : 
                        sum += symbol[s[i]]
                else : 
                    sum += symbol[s[i]]
            else:
                sum += symbol[s[i]]
            i += 1
        return sum


input = ["III","LVIII","MCMXCIV"]

for i in input:
    print(Solution().romanToInt(i))

# Solution().romanToInt(input[2])

class Solution(object):
    def romanToInt(self, s: str) -> int:
        symbolValue = {'I': 1, 'IV':4, 'V': 5, 'IX':9, 'X': 10, 'XL':40, 'L': 50, 'XC':90, 'C': 100, 'CD': 400, 'D': 500, 'CM': 900, 'M': 1000}
        sum = 0
        i = 0

        while(self.indexInString(i, s)):
            if(self.indexInString(i+1, s) and s[i: i+2] in symbolValue):
                sum += symbolValue[s[i: i+2]]
                i += 2
            else:
                sum += symbolValue[s[i]]
                i += 1
        return sum

    def indexInString(self, i: int, s:str)-> bool:
        return i < len(s)



input = ["III","LVIII","MCMXCIV"]

for i in input:
    print(Solution().romanToInt(i))

# Solution().romanToInt(input[2])

순열은 어떤 집합의 원소들을 중복없이 뽑아 순서에 상관있게 나열하는것입니다.

n개의 원소를 가진 집합에서 r개를 뽑아 순열을 만든다고 하면 nPr 과 같이 나타냅니다.

원소를 넣을지 말지를 정했던 부분집합과 달리 순열은 이 위치에 이 원소를 넣을지 말지를 나누어서 진행됩니다.

{1,2,3,4}로 4개의 원소를 가진 집합에서 4개를 뽑아 만들 수 있는 순열을 모두 구한다고 해봅시다. = 4P4

우선 첫번째 위치에 1이 들어갑니다.

이 과정에서 우리는 1로 시작하는 모든 순열을 구하게 됩니다. (1로 만들수 있는 경우)

중복이 허용되지 않기 때문에 이미 사용된 1을 제외한 나머지 원소들 중에서 두번째 자리에 들어갈 것을 정해야합니다.

순서대로 2를 넣어줍니다. (1-2로 만들수 있는 경우)

같은 방식으로 중복이 되지 않게 다음 자리에 넣어질 수를 구해봅시다.

이때 재귀 호출된 함수는 이런 상태입니다. 

가장 위쪽에서부터 하나씩 숫자를 선택하며 4번째 같은 함수를 호출했습니다.

원했던 4개의 원소를 뽑았으므로 1-2-3-4 순열이 완성됩니다. (1-2-3 으로 만들수 있는 경우)

이제 4번째 함수는 종료되고 세번째 함수로 돌아갑니다. (1-2로 만들수 있는 경우)

세번째 자리에 3을 넣은 경우는 앞에서 시행했으므로 이번엔 4가 들어갑니다.

같은 방식으로 진행해서 이번엔 1-2-4-3 이라는 순열을 완성했습니다. (1-2-4 로 만들수 있는 경우)

순열은 구성한 원소가 같더라도 순서가 다르면 다른 것으로 보기때문에 1-2-3-4와 1-2-4-3은 다른 순열입니다.

첫 자리와 두번째 자리가 각각 1, 2인 경우는 모두 탐색되었습니다.

이제 두번째 자리가 달라지는 경우를 찾습니다.

두번째 자리에 3이 들어가는 경우가 시작됩니다.

위와 같은 방식으로 진행해서 1-3-2-4 순열을 얻었습니다.

같은 방식으로 진행하면 위와 같은 순서로 24개의 순열을 얻습니다.

처음 시작할때 원소들이 오름차순 정렬된 상태였으므로 결과들도 오름차순으로 정렬된 순서로 나옵니다.

아래는 위 아이디어를 구현한 Java와 Python코드입니다.

size 변수를 number배열의 원소 갯수보다 작게 조절하면 부분순열이 됩니다.

순열을 만드는 방법은 아래와 같이 재귀를 이용한 것과 반복문을 이용한 nextPermutation이란것이 있는데 후자는 다른 포스팅에서 얘기해보도록 하겠습니다.

public class algo_02_permutation {
	static int[] number = { 1, 2, 3, 4, 5, 6 };
	static int size = 6;

	public static void main(String[] args) {
		makePermutation(0, new int[size], new boolean[number.length]);
	}

	public static void makePermutation(int count, int[] picked, boolean[] used) {
		if (count == size) {
			printPermutation(picked);
			return;
		}
		
		for(int i = 0; i < number.length; i++) {
			if(!used[i]) {
				picked[count] = number[i];
				used[i] = true;
				makePermutation(count+1, picked, used);
				used[i] = false;
			}
		}
		
	}

	public static void printPermutation(int[] picked) {
		StringBuilder sb = new StringBuilder();
		sb.append("{ ");
		for (int i = 0; i < size; i++) {
			sb.append(picked[i]).append(" ");
			}
		sb.append("}");
		System.out.println(sb.toString());
	}
}

def makePermutation(count, picked, used):
    global size
    global number

    if(count == size):
        printPermutation(picked)
        return
    
    for i in range(0, len(number)):
        if(not used[i]):
            picked[count] = number[i]
            used[i] = True
            makePermutation(count+1, picked, used)
            used[i] = False
    

def printPermutation(picked):
    global size
    msg = "{ "
    for i in range(0,size):
            msg += str(picked[i])
            msg += " "
    msg += "}"
    print(msg)

number = [1,2,3,4,5,6]
size = 6

makePermutation(0, [0]*size, [False]*len(number))

오랜만에 다시 쓰는 알고리즘 글입니다.

오늘은 부분집합을 만드는 법에 대해 알아보겠습니다.

제가 수학 전공은 아니기 때문에 집합, 부분집합에 관한 기본적인 수학적 지식은 넘기고 설명을 하겠습니다.

부분집합은 어떤 집합에 속한 원소들로만 이루어진 집합입니다.

멱집합은 어떤 집합에서 만들 수 있는 모든 부분집합들을 모은 집합입니다.

보통 부분집합을 응용하는 PS는 이런 멱집합을 구하고 풀이하는 경우가 많습니다.

N개의 원소를 가진 집합의 부분집합의 개수는 2^N개입니다.

부분집합을 만들 때 집합의 어떤 원소를 넣던가 넣지 않던가 두 가지 선택이 가능하고 이런 원소가 N개 있으므로 2^N개의 부분집합이 생기는 것도 당연할 겁니다.

멱집합을 만드는 코드도 이 아이디어를 이용해서 진행합니다.

1~6까지의 숫자를 가진 집합이 있다고 생각해 봅시다.

이 집합의 부분집합으로 하나의 원소를 가진 부분집합 {1}, 여러 원소를 가진 부분집합 {1,2,3}, 공집합 { }, 집합 전체와 같은  {1,2,3,4,5,6}등 여러 종류가 있을 겁니다.

위에서 얻은 아이디어대로 하나의 원소를 넣고 빼는 두 가지 경우를 체크하며 부분집합을 만들어 봅시다.

6개의 원소가 있는 집합이지만 첫 번째 원소 1만 가졌다고 생각해 봅시다.

이 집합의 부분집합은 1이 들어있거나 안 들어있는 두 가지 경우로 나뉩니다.

이 두가지 경우에 대해 우리는 {1}과 { }라는 두 개의 부분집합을 만들 수 있습니다.

두 번째 원소 2를 더해 생각해볼까요?

1과 2 두 개의 원소를 가진 집합의 부분집합은 앞에서 구한 부분집합들에 2가 들어가거나 안 들어가는 두 가지 경우로 생각할 수 있습니다.

즉 우리는 {1,2} {1}, {2}, { }라는 4개의 부분집합을 얻을 수 있습니다.

집합의 원소가 늘어날 때마다 부분집합의 개수는 2배로 늘어나는 것이죠.

3을 포함시켜 {1,2,3}이라는 집합의 부분집합을 구해본다면 앞에서 구한 {1,2} {1}, {2}, { } 4개의 부분집합에 3이 들어가거나 안 들어가는 두 가지 경우로 {1,2,3} {1,3}, {2,3}, {3}, {1,2} {1}, {2}, { } 8개의 부분집합을 만들 수 있을 겁니다.

이렇게 구한 모든 부분집합의 집합을 멱집합이라고 부릅니다.

이 진행과정을 Java와 Python 두 개로 구현해 보았습니다.

부분집합, 조합, 순열 등의 개념을 응용하는 문제는 무척 많기 때문에 익숙해지시면 유용하게 쓰실 수 있습니다.

Java

public class algo_01_subset {
	static int[] number = {1,2,3,4,5,6};
	static int size = 6;
	public static void main(String[] args) {
		makeSubset(0, new boolean[size]);
	}
	
	public static void makeSubset(int idx, boolean[] used) {
		if(idx == size) {
			printSubset(used);
			return;
		}
		
		used[idx] = false;
		makeSubset(idx+1, used);
		used[idx] = true;
		makeSubset(idx+1, used);
	}
	
	public static void printSubset(boolean[] used) {
		StringBuilder sb = new StringBuilder();
		sb.append("{ ");
		for(int i = 0; i < size; i++) {
			if(used[i]) {
				sb.append(number[i]).append(" ");
			}
		}
		sb.append("}");
		
		System.out.println(sb.toString());
	}
}

Python

def makeSubset(idx, used):
    global size
    if(idx == size):
        printSubset(used)
        return
    
    used[idx] = False
    makeSubset(idx+1, used)
    used[idx] = True
    makeSubset(idx+1, used)

def printSubset(used):
    global size
    global number
    msg = "{ "
    for i in range(0,size):
        if(used[i]):
            msg += str(number[i])
            msg += " "
    msg += "}"
    print(msg)

number = [1,2,3,4,5,6]
size = 6

makeSubset(0, [False]*size)

https://school.programmers.co.kr/learn/courses/30/lessons/42576

참가자와 완주자 사이에 맞지 않는 한 명을 찾는 문제입니다.

HashMap (파이썬의 Dictionary)자료구조를 사용해 풀이했습니다.

문제를 처음 보면 참가자들을 저장하고, 완주자들을 제외 한 뒤 남은 한 명을 구하는 식으로 구현해야할것 같습니다.

하지만 가만히 생각해보면 완주자들을 저장한 뒤 참가자들을 순회하면서 완주자 목록에 없는 사람을 찾는 역순으로 구현하는게 더 간단합니다. 

완주자들의 이름을 key로 Dictionary에 넣어 존재하지 않는다면 value를 1로 저장하고 동명이인이 있다면 value+1로 갱신해줍니다.

이후 참가자들의 이름을 완주자를 저장한 Dictionary에서 확인하면서 하나씩 지워주다가 존재하지 않는 이름이나 완주 목록이 이미 0이 된 이름이 나오면 그 참가자가 우리가 찾는 답이 됩니다.

def solution(participant, completion):
    map = {}

    for i in completion :
        if(i in map):
            map[i] = map.get(i) + 1
        else : 
            map[i] = 1

    for i in participant:
        if(i in map and map[i] > 0):
            map[i] = map.get(i) - 1
        else : 
            return i


participant = [["leo", "kiki", "eden"], ["marina", "josipa", "nikola", "vinko", "filipa"], ["mislav", "stanko", "mislav", "ana"]]
completion = [["eden", "kiki"], ["josipa", "filipa", "marina", "nikola"], ["stanko", "ana", "mislav"]]

for i in range(0,3):
    print(solution(participant[i], completion[i]))