空놀이

C++은 알아서 정렬을 빠르게 해준다.

구조체의 경우도 아래와 같이 가능

#include <algorithm>

#include <vector>

struct st{
int X, ID;//위치, 아이디
};
st AI[50010];

bool myfunction (st i,st j) { 

    return (i.X < j.X); 

}

void main(void){

    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> AI[i].X >> AI[i].ID;
        A.push_back(AI[i]);
    }

    sort (A.begin(), A.end(), myfunction); 

}

출처 : http://www.cplusplus.com/reference/algorithm/sort/ 

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);
                }
            }
        }
    }
};

https://colorscripter.com/

http://google.github.io/styleguide/pyguide.html

잘 익혀두자.

오늘은 LeetCode를 풀 때 필수 문법에 대해 정리해 보겠습니다.

다양한 언어를 접했던 관계로 LeetCode를 풀 때 상황에 따라 언어를 바꾸다 보니 저도 헷깔려서 정리해 봅니다.

(1) Java

a. System.out.println("a + b = " + c);

b. class{

}

c. int 선언 시 new를 해야함

int test[][] = new int[1000][1000];

d. 배열의 길이

test.length

test[0].length

(2) Python2.x

a. print "a + b = %d", (c);

b. 

c. 

d. 리스트의 길이

len(test)

len(test[0])

e. for문

for i in range(len(nums)):

(3) C++

a. cout << "a + b = " << c << endl;

b. class 끝에 세미콜론을 붙인다.

class{

}; 

c. 벡터 선언

// assumes using std::vector for brevity

vector<vector<int>> matrix(RR, vector<int>(CC));

또는

vector<vector<int> > matrix;

for(int i = 0; i<RR; i++) {

    vector<int> myvector;

    for(int j = 0; j<CC; j++)

   {

        int tempVal = 0;

        cout<<"Enter the number for Matrix 1";

        cin>>tempVal;

        myvector.push_back(tempVal);

    }

    matrix.push_back(myvector);

}

d. 벡터의 길이

test.size()

test[0].size()

생각날 때마다 계속 업데이트 하겠습니다.

회사 역량 시험은 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

https://leetcode.com/problems/construct-the-rectangle/submissions/

그냥 질문 그대로 구현했다.

좀 느릴 것 같다.

class Solution {
    public int[] constructRectangle(int area) {
        int value[] = new int[2];
        if(area == 0){
            value[0] = 0;
            value[1] = 0;
            return value;
        }
        else if(area == 1){
            value[0] = 1;
            value[1] = 1;
            return value;
        }

        int difference = area;
        int start = 1;
        int end = area;
        int a, b;
        for(int i = start; i <= end; i++){
            if(area % i == 0){
                a = i;
                b = area / i;
            
                if((a >= b)&&((a-b)<difference)){
                    difference = value[0] - value[1];
                    value[0] = a;
                    value[1] = b;
           
                }
            }
        }
        return value;
    }
}

4. 485 : Max Consecutive Ones

https://leetcode.com/problems/max-consecutive-ones/submissions/

예외 처리에 주의해야겠다.

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        cnt = 0
        max = 0
        
        for i in range(len(nums)):
            if nums[i] == 1:
                cnt += 1
            else:
                if max < cnt:
                    max = cnt
                cnt = 0
        
        if max < cnt:
            max = cnt
                
        return max        
        """
        :type nums: List[int]
        :rtype: int
        """

파이썬은 리스트가 잘 되어 있어서 구현이 쉬웠음

class Solution(object):
    def moveZeroes(self, nums):
        if len(nums) == 0:
            return
        
        for i in range(len(nums)):
            if(nums[i] == 0):
                nums.remove(0)
                nums.append(0)
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """