내일은 알고리즘

https://leetcode.com/problems/is-subsequence/

Subsequence는 어떤 String에서 임의의 문자들을 삭제했을때 만들어지는 String이라고 합니다.

s가 t의 Subsequence인지 묻는 문제입니다.

문제 자체는 그리디한 느낌으로 s의 문자들을 차례대로 t에서 찾으면 해결됩니다.

다만 제 풀이코드 기준에서 s와 t의 길이에 따라 index가 범위를 넘어가는 경우가 있어서 예외처리해 주었습니다.

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if(len(s) > len(t)):
            return False
        if(len(s) == 0):
            return True

        idx = 0
        for i in t:
            if(i == s[idx]):
                idx += 1
            if(len(s) == idx):
                return True
        return False

input = [["abc", "ahbgdc"],["axc", "ahbgdc"]]

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

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://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])

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

오늘 푼 다른 문제들과 비슷한 간단한 시뮬레이션 문제입니다.

앞에서부터 입력된 List를 쭉 읽어가면서 영어로 된 숫자가 나오면 변환하고 단어의 길이만큼 점프해 진행했습니다.

숫자가 나오면 바로 answer에 누적해주었습니다.

자릿수 문제는 앞에서부터 List를 읽어가기 때문에 새로운 숫자가 더해지기 전에 기존의 answer에 10을 곱하고 더하는 식으로 구현했습니다. 

List에 각 자릿수의 숫자를 하나씩 append하고 반복문이 끝난 후 마지막에 List를 숫자로 변환시켜도 같은 결과가 나옵니다.

def solution(s):
    answer = 0
    i = 0
    # numList = []
    while(i < len(s)):
        character = ord(s[i])
        num = 0
        if(48 <= character and character <= 57):
            num = int(s[i])
            i += 1
        else : 
            if(s[i] == 'z'): 
                num = 0
                i += 4
            elif(s[i] == 'o'):
                num = 1
                i += 3
            elif(s[i] == 'e'):
                num = 8
                i += 5
            elif(s[i] == 'n'):
                num = 9
                i += 4
            elif(s[i] == 't'):
                if(s[i+1] == 'w'):
                    num = 2
                    i += 3
                else : 
                    num = 3
                    i += 5
            elif(s[i] == 'f'):
                if(s[i+1] == 'o'):
                    num = 4
                    i += 4
                else : 
                    num = 5
                    i += 4
            else :
                if(s[i+1] == 'i'):
                    num = 6
                    i += 3
                else : 
                    num = 7
                    i += 5
        answer = answer * 10
        answer += num
        # numList.append(str(num))
    # print(numList)
    # numString = "".join(numList)
    # answer = int(numString)
    return answer

input = ["one4seveneight","23four5six7","2three45sixseven","123"]

for i in input:
    print(solution(i))

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

문자열이나 문자의 비교, 아스키코드를 알아야 쉽게 풀 수 있는 시뮬레이션 문제입니다.

입력된 문자열을 7단계를 거쳐 요구하는 조건에 맞는 문자열로 변형시켜야 하는데, 한 함수 안에서 동작해도 상관 없지만 구현시에 헷갈리지 않기 위해 7단계를 step 1~7로 쪼개어 각각 구현했습니다.

def solution(new_id):
    
    id = step1(new_id)
    id = step2(id)
    id = step3(id)
    id = step4(id)
    id = step5(id)
    id = step6(id)
    id = step7(id)

    answer = ""
    for i in id:
        answer += i
    return answer

def step1(id):
    result = []
    for i in id:
        character = ord(i)
        if(65 <= character and character <= 90):
            result.append(chr(character + 32))
        else:
            result.append(i)

    return result

def step2(id):
    result = []
    for i in id:
        character = ord(i)
        if((97 <= character and character <= 122) or (48 <= character and character <= 57) or character == 45 or character == 46 or character == 95):
            result.append(i)

    return result

def step3(id):
    result = []
    before = ''
    for i in id:
        if(before == '.' and i == '.'):
            continue
        else :
            result.append(i)
            before = i

    return result

def step4(id):
    if(len(id) > 0 and id[0] == '.'):
        id = id[1:]
    if(len(id) > 0 and id[-1] == '.'):
        id = id[0:-1]
    return id

def step5(id):
    if(len(id) == 0):
        return ['a']
    return id

def step6(id):
    if(len(id) > 15):
        id = id[0:15]
        if(len(id) > 0 and id[-1] == '.'):
            id = id[0:-1]
    return id

def step7(id):
    while(len(id) < 3):
        id.append(id[-1])
    return id


input = ["...!@BaT#*..y.abcdefghijklm","z-+.^.","=.=","123_.def","abcdefghijklmn.p"]
# input = ["...!@BaT#*..y.abcdefghijklm"]

for i in range(len(input)):
    print(solution(input[i]))

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

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

https://nodingco.tistory.com/30 의 시리즈 문제입니다.

1. 이해 (5분) - 1분

A와 B 문제와 언뜻 보면 똑같아보이는 문제입니다. 

하지만 조금 생각해보면 풀이를 위한 접근 방식이 전혀 다른걸 알 수 있습니다. 

앞의 문제에선 연산을 통한 결과가 맨 뒤 알파벳으로 나타나서 역순으로 따라가기만 하면 문제의 풀이가 가능하지만, 해당 문제에선 알파벳을 먼저 붙이고 뒤집기 때문에 맨 뒤 알파벳이 어떤 연산을 통해 나온 것인지 여러 경우가 생깁니다.

대신 문자열의 형태를 보고 어느정도 경우를 좁힐 수 있고 문자열의 길이도 앞 문제보다 훨씬 작습니다.

2. 계획 (5분) - 3분

재귀를 통해 뒷 문자열을 만들기 위해 가능한 경우를 역으로 되짚어갑니다.

대신 두가지 경우를 매 번 탐색하는게 아니라, 맨 뒷 문자가 A거나 맨 앞 문자가 B일때만 탐색합니다.

(1번 연산이 진행되면 문자열의 맨 뒤는 무조건 A, 2번 연산이 진행되면 맨 앞이 무조건 B)

그렇게 줄인 문자열의 길이가 앞의 문자열과 같아지면 두 문자열이 같은지, 즉 문제의 조건이 가능한지를 체크하고 그 결과를 저장합니다. 이때 True False에 따라 재귀문을 끝내는 조건을 움직여서 가능여부가 한 번 찾아지면 덮어씌워지지 않게했습니다.

3. 검증 (5분) - 1분

검증내용은 A와B 1번 문제와 유사하기때문에 패스하겠습니다.

4. 풀이 (30분) - 17분

재귀문 구현 부분은 조금 신경썼지만, 문자열을 조정하는 부분은 오히려 앞 문제보다 쉽게 구현 할 수 있었습니다.

5. 채점, 디버깅 

다행히 이번에도 한 번에 통과했습니다. 감사합니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int N;
	static char[] S;

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

		S = br.readLine().toCharArray();
		char[] T = br.readLine().toCharArray();

		N = S.length;

		makeS(T, T.length);

		if (N == 100) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}

	static void makeS(char[] T, int l) {
		if (l < N) {
			return;
		}
		if (l == N) {
			N = (checkS(T)) ? 100 : N;
			return;
		}

		if (T[l - 1] == 'A') {
			char[] newT = new char[l - 1];
			for (int i = 0; i < l - 1; i++) {
				newT[i] = T[i];
			}
			makeS(newT, l - 1);
		}

		if (T[0] == 'B') {
			char[] newT = new char[l - 1];
			for (int i = 0; i < l - 1; i++) {
				newT[i] = T[l - 1 - i];
			}
			makeS(newT, l - 1);
		}
	}

	static boolean checkS(char[] T) {
		for (int n = 0; n < N; n++) {
			if (T[n] != S[n]) {
				return false;
			}
		}
		return true;
	}
}

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

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

1. 이해 (5분) - 2분

원리를 깨달으면 간단한 시뮬레이션 문제입니다.

다만, 문자열 관련해서 코드를 작성할 이해도가 필요할 것 같습니다.

문제는 간단명료합니다. 앞의 문자열에 두 가지 연산을 적용해서 뒤 문자열을 만들 수 있는지를 찾습니다.

간단히 생각하면 앞의 문자에 두가지 연산을 계속 적용해서 가능한 모든 경우의 수를 볼 수도 있겠지만... 

S의 길이가 1이고, T의 길이가 1000이라면? 2^1000가지 경우를 탐색해야 하니 어마어마한 일이겠죠. 

대신 연산의 조건을 파악하고 완성된 문자열에서 거꾸로 짚어가는 식으로 가부를 판단하려고 합니다.

2. 계획 (5분) - 4분

문자열에 적용한 연산 두가지는 모두 뒤쪽에 알파벳을 하나 더 붙입니다.

즉 최종결과에서 가장 뒤에 있는 알파벳은 이전에 적용된 연산이 무엇이었는지를 알려줍니다.

두 번째 문자열이 앞의 문자열보다 더 긴 길이만큼 연산을 거꾸로 적용하면 앞의 문자열과 같은 길이의 가능한 문자열이 나오게 되고 이 문자열을 앞의 문자열과 비교해서 가부를 판단할 수 있습니다.

문자열을 실제로 뒤집어서 풀이해도 되지만 저는 dir라는 boolean타입 변수를 하나 선언해서 투포인터 식으로 앞과 뒤에서 문자열을 줄여가는 방식으로 코드를 작성했습니다.

3. 검증 (5분) - 1분

시간복잡도나 메모리에서 문제가 생길 부분은 없을 것 같고, 구상한 대로 잘 풀이된다면 코드도 문제없이 작동할 겁니다.

4. 풀이 (30분) - 25분

문제의 이해와 계획은 금방 끝났지만 코드 작성에선 시간을 꽤 사용했습니다. 

반복문을 복잡하게 사용하다 보니 디버깅을 사용해서 제대로 동작하는지 검증을 철저히 했습니다.

5. 채점, 디버깅

다행히 제출은 한 번에 통과했습니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

		char[] s1 = br.readLine().toCharArray();
		char[] s2 = br.readLine().toCharArray();

		int N = s2.length - s1.length;

		int front = 0, back = s2.length - 1;
		boolean dir = true;

		for (int n = 0; n < N; n++) {
			if (dir) {
				if (s2[back] == 'A') {
					back--;
				} else {
					back--;
					dir = false;
				}
			} else {
				if (s2[front] == 'A') {
					front++;
				} else {
					front++;
					dir = true;
				}
			}
		}

		boolean answer = true;

		if (dir) {
			for (int n = 0; n < s1.length; n++) {
				if (s1[n] != s2[front + n]) {
					answer = false;
					break;
				}
			}
		} else {
			for (int n = 0; n < s1.length; n++) {
				if (s1[n] != s2[back - n]) {
					answer = false;
					break;
				}
			}
		}

		if (answer) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}
}