[python code review] 1주차 ( longest-substring-without-repeating-characters, 괄호의 값, zigzag-conversion)

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

 

1. 구현하였으나 성공하지 못한 코드 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        maxLen = 1
        ss = []
        # 0부터 n-1에 대해
        for start in range(0, n):
            # 부분 문자열에 등장한 단어인 경우
            if s[start] in ss:
                # 그 위치까지 이전 s를 자른다
                idx = ss.index(s[start])
                ss = ss[idx:]
            # 등장하지 않은 경우
            else:
                # 부분문자열에 붙인다
                ss.append(s[start])
            maxLen = max(maxLen, len(ss))
            print(ss)
        return maxLen

- maxLen = 0으로 초기화해야 

  입력값이 s = ""인 경우, 실패

- ss[idx:] => ss[idx+1:]로 구현 

- if문에도 ss.append(s[start]) 동작하도록 구현해야 

  else문을 제거하고 ss.append(s[start]) shift + tab 

 

2. 코드 구현 (난이도 중하)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        maxLen = 0
        ss = []
        # 0부터 n-1에 대해
        for start in range(0, n):
            # 부분 문자열에 등장한 단어인 경우
            if s[start] in ss:
                # 그 위치까지 이전 s를 자른다
                idx = ss.index(s[start])
                ss = ss[idx+1:]   
            # 리스트에 해당 원소 추가 
            ss.append(s[start])
            maxLen = max(maxLen, len(ss))
        return maxLen

 

 

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

2504번: 괄호의 값

- stack을 사용하는 문제 

 

 

1. 구현하였으나 성공하지 못한 코드 

def solution(s):
    n = len(s)
    result = 1
    answer = 0
    for i in range(n):
        if s[i] == '(':
            result *= 2
        elif s[i] == ')':
            if s[i-1] == '[':
                return 0
            elif s[i-1] == '(':
                answer += result
            result //= 2
        elif s[i] == '[':
            result *= 3
        else:
            if s[i-1] == '(':
                return 0
            elif s[i-1] == '[':
                answer += result
            result //= 3

    return answer

# print(solution(input()))
data = list(input())
print(solution(data))

- 반례 : [[()]]()]]
- why? stack을 사용하지 않으면 짝이 없는 마지막-1, 마지막 번째의 ']' 에 대한 문제 인식 불가능

 

2. 코드 구현 (난이도 중)

def solution(s):
    n = len(s)
    result = 1
    answer = 0
    # stack 생성
    stack = []
    for i in range(n):
        if s[i] == '(':
            stack.append('(')
            result *= 2
        elif s[i] == ')':
            # s[i-1] -> stack[-1]로 구현
            # 위치를 바꾸어 구현하면 indexError 발생 ☆
            # if (stack[-1] == '[' and stack) or not stack:
            if not stack or stack[-1] == '[':
                return 0
            elif s[i-1] == '(':
                answer += result
            result //= 2
            stack.pop()
        elif s[i] == '[':
            result *= 3
            stack.append('[')
        else:
            if not stack or stack[-1] == '(':
                return 0
            elif s[i-1] == '[':
                answer += result
            result //= 3
            stack.pop()
    if stack:
        return 0
    return answer

data = input()
print(solution(data))

 

 

https://leetcode.com/problems/zigzag-conversion/

Zigzag Conversion - LeetCode

 

1. 코드 구현 (난이도 중)

from math import ceil
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        arr = [[] for _ in range(numRows)]
        n = len(s)
        gap = numRows*2-2
        p1 = 0
        p2 = gap
        # numRows 값이 1인 경우
        if gap == 0:
            return s
        # numRows 값이 2이상인 경우 반복문 동작
        for _ in range(ceil(n/gap)):
            # 지그재그 중 '|' 부분
            for i in range(0, numRows):
                if p1+i < n:
                    arr[i].append(s[p1+i])
            p1 += gap
            # 지그재그 중 '/' 부분
            for i in range(numRows-2, 0, -1):
                if p2-i < n:
                    arr[i].append(s[p2-i])
            p2 += gap
        result = ''
        # 각 행에 담긴 문자열을 하나로 합치기 
        for i in range(numRows):
            result += "".join(arr[i])
        return result

s = "PAYPALISHIRING", numRows = 4일 때 위와 같이 문자가 들어오는데, matrix를 이용하여 행별로 문자를 담고자 하였다. 그래서 이중배열 arr을 선언하였는데 행 길이는 numRows로 맞춰주었다.

 

만약 numRows 값이 1이라면 지그재그 형태가 될 수 없기에 문자열을 그대로 반환해주면 된다. 따라서 gap이 0인 경우, 문자열을 그대로 반환해주었다.

그리고나서 지그재그 중 '|' 부분과 '\' 부분을 나누어 코드로 구현하였다. 

 

(1) 지그재그 중 '|' 부분

(1) 지그재그 중 '/' 부분

이제 원하는 지그재그 문자열을 구하기 위해 완성된 (1), (2) 코드를 몇번 동작시켜야 하는지가 궁금했다. 이게 무슨 말이냐면 문자열에서 '|'와 '/' 덩어리가 문자열에서 몇번 반복되는지를 알아야 반복문을 돌려 지그재그 문자열을 구하는 것이 가능했다. 아래 그림처럼 생각하여 ceil 함수를 통해 반복문의 횟수를 구할 수 있었다.