空놀이

일단 쉬운 문제 많이 풀기!!

class Solution:
    def toLowerCase(self, str: str) -> str:
        str = str.lower()  
        return str
        

하지만 이렇게 lower api를 쓰면 너무 쉬우니 아래 처럼 문자열 처리를 해보자 ㅎㅎ

ord api를 사용하면, A라는 char의 ascii값을 얻을 수 있다.

chr api를 사용하면 ascii값을 다시 char로 변환할 수 있다.

class Solution:
    def toLowerCase(self, str: str) -> str:
        ans = ""
        for i in range(len(str)):
            if(ord(str[i]) >= ord('A') and ord(str[i]) <= ord('Z')):
                print("%d" % (ord(str[i]) - ord('A')))
                ans += chr(ord(str[i]) - ord('A') + ord('a'))
            else:
                ans += str[i]
        return ans

19주차 3/10

전체 17/150

O(N^2) 로 풀었다. 

다음에는 O(N)으로 풀자..ㅎㅎ

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ans = []
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if(nums[i] + nums[j] == target):
                    ans.append(i)
                    ans.append(j)
                    print(ans)
                    return ans

쉬운 문제로 자신감 올리기..

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        length = (int)(len(s) / 2)
        for i in range(length):
            k = len(s) - 1 - i
            temp = s[i]
            s[i] = s[k]
            s[k] = temp
        

C++로만 풀다가 파이썬으로 푸니 어색어색..

푸는 속도도 너무 느리다...

그래서 슬럼프가 왔지만 이번 주말에 극복하기로..

올해 19주가 지났고 약 33주가 남았다.

5월 남은 3주는 일주일에 3개씩 문제를 풀고,

6월부터는 다시 주 5개 문제 풀기 해보자.

코드는 아래에..

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        cnt = 1
        data = ""
        for i in range(len(s)):
            if i % (2*k) == 0:
                cnt = (i + k)
                #print("cnt = %d" % cnt)
                for j in range(k):
                    #print("%d %d" % (i, j))
                    if(i+k-1-j < len(s)):
                        data = data + s[i+k-1-j]
                i = j
            elif(i >= cnt):
                data = data + s[i]
        return data

Tree를 문자열로 만들고 문자열을 다시 Tree로 만들기

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:
    def __init__(self):
        self.traversal = []
        
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if root is None:
            self.traversal.append('#')
            return ' '.join(self.traversal)
                
        self.traversal.append(str(root.val))
        self.serialize(root.left)
        self.serialize(root.right)
        
        return ' '.join(self.traversal)
        
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        #print(data)
        def makeTree():
            val = next(vals)
            if val == '#':
                return
            root = TreeNode(int(val)) 
            root.left = makeTree()
            root.right = makeTree()
            return root
            
        vals = iter(data.split())
        
        return makeTree()
            
        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.traversal = []
        
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if root == None:
            return []
        
        self.traversal.append(root.val)
        self.preorderTraversal(root.left)
        self.preorderTraversal(root.right)
        
        return self.traversal
        
        

inorder 트리 구조가 어떤 것인지 알게 되었다.

class Solution:
    def __init__(self):
        self.traversal = []
        
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        
        
        self.inorderTraversal(root.left)
        
        self.traversal.append(root.val)
        
        
        self.inorderTraversal(root.right)
        
        return self.traversal

위키백과에 따르면, 트리 구조는 아래와 같다.

이진 탐색 트리에서

• 전위 순회: F, B, A, D, C, E, G, I, H (root, left, right)
• 중위 순회: A, B, C, D, E, F, G, H, I (left, root, right)
• 후위 순회: A, C, E, D, B, H, I, G, F (left, right, root)
• 레벨 순서 순회: F, B, G, A, D, I, C, E, H

출처 : https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

파이썬 그리고 트리에 익숙해지기

"""
# Definition for a Node.
class Node:
    def __init__(self, val, children):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        traversal = [root.val]
        for child in root.children:
            traversal.extend(self.preorder(child))
        return traversal

-> 뒤에 나오는 것은 리턴 타입이다

즉 List[int] 가 리턴 타입

C++로 코드를 짜려고 했었는데..

이 문제는 Playground에서 C++ 지원이 되지 않았다. 

그래서 자바로 변경해서 디버깅을 하고, 다시 C++로 변경하였다.

한번에 코드를 다 짜면 좋은데,

코드 짜다가 아들 우유 주고, 산책 다녀오고, 밥 먹고 와서 다시 짜다 보니까

중간에 산으로 한번 갔다가 다시 돌아왔다.

핵심을 잘 생각하고, 종이에 먼저 써보고 코딩하는 습관을 들여야겠다.

C++ Code

class Solution {
public:
    vector<vector> visited;
    vector<vector> wall;
    vector<vector> original_board;


    int r_len;
    int c_len;
    
    int printFlag = 0;
    int change(vector<vector>& board, int r, int c, int w){
        
        //if(printFlag == 1)
        //    System.out.println(r + " " + c);
        
        int wall_detected = 0;
        if(r < 0 || r >= r_len || c < 0 || c>= c_len){
            //if(printFlag == 1)
            //    System.out.println(r + " " + c + " return " + 1);
            return 1;
        }
        if(board[r][c] == 'X'){
            //if(printFlag == 1)
            //     System.out.println(r + " " + c + " return " + 0);
            return 0;
        }
        
        if(w == 1)
            wall[r][c] = 1;
        
        if(visited[r][c] == 1){
            //if(printFlag == 1)
            //    System.out.println(r + " " + c + " visited " + wall[r][c] );
        
            //cout << "visited " << wall[r][c] << endl;
            if(wall[r][c] == 0)
                return 0;
            return 1;
        }
       
        if(visited[r][c] == 1){        
            //cout << "visited " << wall[r][c] << endl;
            if(wall[r][c] == 0)
                return 0;
            return 1;
        }
       
        //System.out.println("");
        //cout << endl;
        visited[r][c] = 1;
        
        wall_detected = change(board, r, c-1, wall[r][c]);
        if(wall_detected == 1)
            wall[r][c] = 1;
        wall_detected += change(board, r, c+1, wall[r][c]);
        if(wall_detected == 1)
            wall[r][c] = 1;
        wall_detected += change(board, r-1, c, wall[r][c]);
        if(wall_detected == 1)
            wall[r][c] = 1;
        wall_detected += change(board, r+1, c, wall[r][c]);          
        if(wall_detected == 1)
            wall[r][c] = 1;
        

        if(board[r][c] == 'O' && wall_detected == 0)
            board[r][c] = 'X';
        wall[r][c] = wall_detected;
        //if(printFlag == 1)
        //    System.out.println("return " + r + " " + c + " " + wall_detected );
        return wall_detected;
        
    }
    void solve(vector<vector>& board) {        
        r_len = board.size();
        if(r_len == 0)
            return;
        c_len = board[0].size();
        
        original_board = board;

        for(int i = 0; i < r_len; i++){
            vector wallvector;
            vector visitedvector;
            for(int j = 0; j < c_len; j++){
                wallvector.push_back(0);
                visitedvector.push_back(0);
            }
            wall.push_back(wallvector);
            visited.push_back(visitedvector);

        }
        for(int i = 0; i < r_len; i++){
            for(int j = 0; j < c_len; j++){
                board[i][j] = original_board[i][j];
                visited[i][j] = 0;
                wall[i][j] = 0;
                if(board[i][j] == 'O'){
                    if(i == 3 && j == 3)
                        printFlag = 2;
                    change(board, i, j, 0);
                }
            }
        }
        for(int i = 0; i < r_len; i++){
            for(int j = 0; j < c_len; j++){
                board[i][j] = original_board[i][j];
                visited[i][j] = 0;
                wall[i][j] = 0;
                if(board[i][j] == 'O'){
                    if(i == 3 && j == 3)
                        printFlag = 2;
                    change(board, i, j, 0);
                }
            }
        }

    }
};

Java Code

class Solution {
    //int visited[][];
    //int wall[][];
    int visited[][] = new int[1000][1000];
    int wall[][] = new int[1000][1000];
    char original_board[][] = new char[1000][1000];


    int r_len;
    int c_len;
    
    int printFlag = 0;
    int change(char[][] board, int r, int c, int w){
        
        if(printFlag == 1)
            System.out.println(r + " " + c);
        
        int wall_detected = 0;
        if(r < 0 || r >= r_len || c < 0 || c>= c_len){
            if(printFlag == 1)
                System.out.println(r + " " + c + " return " + 1);
            return 1;
        }
        if(board[r][c] == 'X'){
            if(printFlag == 1)
                 System.out.println(r + " " + c + " return " + 0);
            return 0;
        }
        
        if(w == 1)
            wall[r][c] = 1;
        
        if(visited[r][c] == 1){
            if(printFlag == 1)
                System.out.println(r + " " + c + " visited " + wall[r][c] );
        
            //cout << "visited " << wall[r][c] << endl;
            if(wall[r][c] == 0)
                return 0;
            return 1;
        }
       
        //System.out.println("");
        //cout << endl;
        visited[r][c] = 1;
        
        wall_detected = change(board, r, c-1, wall[r][c]);
        if(wall_detected == 1)
            wall[r][c] = 1;
        wall_detected += change(board, r, c+1, wall[r][c]);
        if(wall_detected == 1)
            wall[r][c] = 1;
        wall_detected += change(board, r-1, c, wall[r][c]);
        if(wall_detected == 1)
            wall[r][c] = 1;
        wall_detected += change(board, r+1, c, wall[r][c]);          
        if(wall_detected == 1)
            wall[r][c] = 1;
        

        if(board[r][c] == 'O' && wall_detected == 0)
            board[r][c] = 'X';
        wall[r][c] = wall_detected;
        if(printFlag == 1)
            System.out.println("return " + r + " " + c + " " + wall_detected );
        return wall_detected;
        
    }
    void solve(char[][] board) {
        
        r_len = board.length;
        if(r_len == 0)
            return;
        c_len = board[0].length;
        
    
        for(int i = 0; i < r_len; i++){
            for(int j = 0; j < c_len; j++){
                wall[i][j] = 0;
                visited[i][j] = 0;
                original_board[i][j] = board[i][j];
            }
        }
        int finish = 0;
        
        for(int i = 0; i < r_len; i++){
            for(int j = 0; j < c_len; j++){
                board[i][j] = original_board[i][j];
                visited[i][j] = 0;
                wall[i][j] = 0;
                if(board[i][j] == 'O'){
                    if(i == 2 && j == 5)
                        printFlag = 2;

                    if(printFlag == 1)
                        System.out.println("Call " + i + " " + j);
                    change(board, i, j, 0);
                }
            }
        }
        for(int i = 0; i < r_len; i++){
            for(int j = 0; j < c_len; j++){
                board[i][j] = original_board[i][j];
                visited[i][j] = 0;
                wall[i][j] = 0;
                if(board[i][j] == 'O'){
                    if(i == 3 && j == 3)
                        printFlag = 2;
                    change(board, i, j, 0);
                }
            }
        }
    }
};

회사 역량 시험은 C, C++, Java 만 가능한데, Java는 재귀 함수 사용 시 메모리 문제가 발생할 수 있다고 해서,

C++로 하기로 결정!!

Number of Islands 를 java로 다시 풀어보았다.

이전과 같이, DFS : Depth First Search 깊이 우선 탐색 알고리즘이며 재귀함수 호출 방식이다.

C++ 문법이 헷깔려서 다른 사람 코드를 언뜻 봤는데, 알고리즘이 좋아서 나도 참조해 보았다.

class Solution {
public:
    int r_length = 0;
    int c_length = 0;
    
    void findOne(vector<vector>& grid, int r, int c){
        if(r < 0 || r >= r_length || c < 0 || c >= c_length)
            return;
        
        if(grid[r][c] == '0')
            return;
        
        grid[r][c] = '0';
        
        findOne(grid, r, c-1);
        findOne(grid, r, c+1);
        findOne(grid, r-1, c);
        findOne(grid, r+1, c);
        
        return;
    }
    int numIslands(vector<vector>& grid) {
        r_length = grid.size();
        
        if(grid.size() == 0)
            return 0;
        c_length = grid[0].size();
        
        int cnt = 0;
        for(int i = 0; i < r_length; i++){
            for(int j = 0; j < c_length; j++){
                if(grid[i][j] == '1'){
                    cnt++;
                    findOne(grid, i, j);
                }
            }
        }
        
        return cnt;
    }
    
};

출처 : https://leetcode.com/problems/number-of-islands/discuss/266379/(98.93-100)-DFS-C%2B%2B