IT 기술 따라잡기

문장 안에 중복 되는 글자 찾는 코딩이다.

소스 코드는 아래와 같다.

public class DuplicateCharacters {  
     public static void main(String[] args) {  
        String string1 = "Find duplicated letters in a String.";  
        int count;  
          
        //Converts given string into character array  
        char string[] = string1.toCharArray();  
          
        System.out.println("Duplicate characters in a given string: ");  
        //Counts each character present in the string  
        for(int i = 0; i <string.length; i++) {  
            count = 1;  
            for(int j = i+1; j <string.length; j++) {  
                if(string[i] == string[j] && string[i] != ' ') {  
                    count++;  
                    //Set string[j] to 0 to avoid printing visited character  
                    string[j] = '0';  
                }  
            }  
            //A character is considered as duplicate if count is greater than 1  
            if(count > 1 && string[i] != '0')  
                System.out.println(string[i]);  
        }  
    }  
}  

하나 하나 분석해 보겠다.

public class DuplicateCharacters {   // 클래스 이름은 DuplicateCharacters 이다.
     public static void main(String[] args) {  // 실행 하기 위해 main 메소드를 사용한다.
        String string1 = "Find duplicated letters in a String.";  // 이게 입력 되는 스트링이다.
        int count;  // 중복 되는 글자가 몇개나 있는지 담을 인티저 변수이다.
          
        //Converts given string into character array  
        char string[] = string1.toCharArray();  // 스트링을 어레이로 변환한다.
          
        System.out.println("Duplicate characters in a given string: ");  // 입력 값을 프린트 한다.
        //Counts each character present in the string  
        for(int i = 0; i <string.length; i++) {  // 배열내 값의 갯수 즉 스페이스를 포함한 글자의 갯수 만큼 for 문을 돌린다.
            count = 1;  // count를 1로 선언한다.
            for(int j = i+1; j <string.length; j++) {  // 배열 내 값의 갯수 보다 한개 적은 숫자 만큼 for 문을 돌린다. 이중 루프이다.
                if(string[i] == string[j] && string[i] != ' ') {  // 만약에 스페이스가 아닌데 같은 글자가 있으면 이 if 문을 실행한다.
                    count++;  // 같은 글자가 있다면 count를 하나 증가 시킨다.
                    //Set string[j] to 0 to avoid printing visited character  
                    string[j] = '0';  // 해당 되는 같은 글자는 0으로 바꾼다.
                }  
            }  
            //A character is considered as duplicate if count is greater than 1  
            if(count > 1 && string[i] != '0')  // count가 1보다 크고 값이 0이 아니면 if문을 출력한다.
                System.out.println(string[i]);  // 해당 값을 출력한다.
        }  
    }  
}  

코드를 조금 바꿔 봤다.

출력 값을 리스트에 담아서 이 리스트를 출력 하도록 수정했다.

소스 코드는 아래와 같다.

수정한 부분만 주석을 달았다.

import java.util.List; // List 를 사용하기 위해 import 함
import java.util.ArrayList; // ArrayList를 사용하기 위해 import 함

public class DuplicateCharacters {  
     public static void main(String[] args) {  
        String string1 = "Find duplicated letters in a String.";  
        int count;  
          
        //Converts given string into character array  
        char string[] = string1.toCharArray();  
        List<Character> answer = new ArrayList(); // 출력 될 값을 담을 ArrayList를 선언 함. 이름은 answer
          
        System.out.println("Duplicate characters in a given string: ");
        System.out.println();
        //Counts each character present in the string  
        for(int i = 0; i <string.length; i++) {  
            count = 1;  
            for(int j = i+1; j <string.length; j++) {  
                if(string[i] == string[j] && string[i] != ' ') {  
                    count++;  
                    //Set string[j] to 0 to avoid printing visited character  
                    string[j] = '0';  
                }  
            }  
            //A character is considered as duplicate if count is greater than 1  
            if(count > 1 && string[i] != '0')  {
                answer.add(string[i]); // 출력 값을 answer 에 담는다. 
            }
        }  
        
        answer.forEach(System.out::println); // forEach를 사용해 ArrayList answer의 값을 출력한다.

    }  
}  

요즘 Leetcode에서 문자열 reverse 하는 문제를 풀어 봤는데 주말에 한번 더 연습을 해 보았다.
내가 만든 코드와 결과는 아래와 같다.

코드를 잘 살펴 보자.

class reverse { // 클래스 이름은 reverse이다.
    public static void main(String[] args) { // 실행을 하기 위해 main() 메소드를 사용했다.
        String a = "Hello World"; // 테스트 할 스트링이다.
        char[] b = a.toCharArray(); // 리버스 하기 위해 스트링을 char[] 데이터 타입으로 변환했다.
        
        int left = 0; // left는 0으로 선언
        int right = b.length-1; // right 는 b[] 의 맨 마지막 자리로 선언
        
        while(left < right) { // left가 right보다 작을 때 까지만 while문을 실행한다.
            char temp = b[left]; // 임시로 입력값의 맨 앞자리 값을 temp에 담는다.
            b[left++] = b[right]; // b의 left 자리에 right 자리값을 넣는다.
            b[right--] = temp; // 임시로 저장했던 left 자리의 값을 right에 넣는다.
            // left++ 와 right—의 의미는 이전 글 참조
        }
        
        for(int i = 0; i < b.length; i++){ // for문을 돌려 b[]의 값들을 출력한다.
            System.out.println(b[i]);
        }
        
    }
}

이번 문제는 문제 자체를 이해하기가 좀 어렵다.
문제를 잘 해석해 보면…
우선 Example 1 의 인풋과 아웃풋을 보자

abcdefg 와 2가 인풋이다.
여기서 요구하는 사항은 두번째 글자를 첫번째 글짜와 Reverse 하라는 거다.
그래서 아웃풋을 보면 abcd가 bacd 가 되었다.
그 다음 요구는 각각의 2k 마다 이 일을 하라는 거다.
여기서 인풋 k = 2이기 때문에 2 * 2 = 4 마다 이 일을 하라는 거다.

즉 abcd는 일을 다 끝냈고 그 다음에 남은건 efg 이니까 여기서 두번째 글자와 첫번째 글자의 위치를 바꾸라는 거다.

아래 스크립트로 원하는 답을 얻을 수 있다.

class Solution {
    public String reverseStr(String s, int k) {
        char[] a = s.toCharArray();
        for (int start = 0; start < a.length; start += 2 * k) {
            int i = start, j = Math.min(start + k - 1, a.length - 1);
            while (i < j) {
                char tmp = a[i];
                a[i++] = a[j];
                a[j--] = tmp;
            }
        }
        return new String(a);
    }
}

한줄 한줄 분석해 보자.

class Solution { ==> 클래스 이름은 Solution이다.
    public String reverseStr(String s, int k) {
==> 메소드 이름은 reverseStr이고 입력값으로 스트링 s , int k 를 받는다. return 값은 String이다.
        char[] a = s.toCharArray();
==> 입력받은 스트링을 toCharArray()를 이용해서 배열로 만들고 변수 a 에 할당한다.
        for (int start = 0; start < a.length; start += 2 * k) {
==> 루프를 만들어 start가 배열 아이템 갯수 보다 작을 때 까지 돌린다. start는 초기 값이 0이고 루프 한번 돌면 start 값은 start + 2 * k 만큼 증가한다.
            int i = start, j = Math.min(start + k - 1, a.length - 1);
==> inti 에는 start 값이 대입된다. Int j 에는 start + k 값과 a.length - 1 값 중 작은 값이 대입 된다.
==>
            while (i < j) {
==> i 가 j 보다 작을 때 까지만 while문을 돌린다.  즉 2*k 블럭이 더이상 없으면 while문은 종료한다.
                char tmp = a[i];
==> tmp에 배열의 첫번째 값을 대입한다.
                a[i++] = a[j];
==> a 의 첫번째 값에 j의 값을 대입한다. 그리고 i 에 1을 더해 준다.
                a[j--] = tmp;
==> 배열 맨 마지막에 첫번째 값을 대입한다.
            }
        }
==> 이건 for 와 while이 있는 이중 루프이다.
==> start와 i와 j가 어떻게 증가하는지 이해 해야 한다.
==> start는 k 가 2인경우 0, 4, 8, 12 이렇게 증가한다. k가 3인 경우는 0, 6, 12, 18 이렇게 증가한다.
==> i 는 매번 루프를 돌 때무다 start가 대입 되고 while을 돌 때는 1씩 증가한다.
==> j 는 start + k 와 a.length -1 중 작은 값이 대입 되고 while을 돌 때 마다 1씩 증가한다.
        return new String(a);
==> 배열 a를 스트링 형으로 바꿔서 return 한다.
    }
}

입력값을 위와 같이 바꿔 봤다.

결과 값을 보면 세번째 값인 c가 맨 앞에 왔다. 그 다음 블럭은 ghijkl 이다.
두번째 블럭 세번째 값인 i 가 맨 앞으로 왔다.
세번째 블럭은 mn 이다.
여기서 두번째 값인 n이 앞으로 왔다.
이건 요구 조건 충족이 되는건가?
하여간 Expected 와 결과값이 같으니까 통과 하긴 했는데…
왜 두번째 값인 n이 앞으로 왔는지 모르겠다. 입력값은 3이니까 세번째 값이 와야 되는데… 그런데 세번째 값이 없으니…. 맨 마지막 값이 앞으로 와 버렸다.
로직상 이렇게 작동하는건 맞긴 한데…
이게 요구 조건에 충족되는 건지는 모르겠다.

파이썬 코드는 아래와 같다.

class Solution(object):
    def reverseStr(self, s, k):
        a = list(s)
        for i in xrange(0, len(a), 2*k):
            a[i:i+k] = reversed(a[i:i+k])
        return "".join(a)

오늘의 Leetcode 연습문제는 Reverse String 이다.
아래 input과 output이 있다.

코드는 아래와 같다.

class Solution {

    public void reverseString(char[] s) {

        int left = 0;

        int right = s.length - 1;

        while (left < right) {

            char temp = s[left];

            s[left++] = s[right];

            s[right--] = temp;

        }

    }

}

한 줄 한 줄 살펴 보겠다.

class Solution {

==> 클래스 이름은 Solution있다.

    public void reverseString(char[] s) {

==> 메소드 이름은 reverseString 이고 input 은 char[] s 이며 return 값은 없다. 그냥 입력 String 을 reverse 하는 기능만 있다. 

        int left = 0; ==> left 라는 int 변수에 0을 대입한다.

        int right = s.length - 1; ==> right 라는 int 변수에 입력 값 s의 맨 마지막 글자가 대입된다.

        while (left < right) { ==> left 가 right 보다 작을 경우에만 실행하고 그렇지 않으면 while 문을 종료한다.

            char temp = s[left]; ==> temp 라는 캐릭터에 s[left] 값을 대입한다.

            s[left++] = s[right];

==> 이 부분을 잘 이해 해야 한다.

==> left++ 는 left = left+1과 같다. 첫번째는 left 가0이다. 그리고 left + 1을 하면 left 가 1이 된다.

==> 실행 순서는 s[0] = s[right]을 먼저 실행 한 다음에 left = left+1이 된다.

==> 그렇게 되면 s[0]에 s의 맨 마지막 값이 대입되고 난 후 left는 1이 된다.

==> 다음 while 문 돌 때는 left가 0 이 아니라 1 이 된다.

            s[right--] = temp;

==> 이것도 마찬가지 right-- 는 right = right -1 과 같다.

==> 위에서 설명한 대로 s[right] = temp 가 먼저 실행 된다. 즉 s[right]에 s 의 맨 처음 값이 대입 된다.

        }

    }

}

While 문을 처음 되면은 s 의 처음 값이 맨 마지막으로 가고 맨 마지막 값이 맨 처음으로 오게 된다.

두번째 while 문에서는 s의 두번 째 값이 끝에서 두번째로 가고 끝에서 두번째 값이 두번째로 오게 된다.

이 while 문은 배열의 중간까지 오게 되면 left가 right보다 작지 않으므로 멈춘다.

그러므로 배열의 중간을 기준으로 reverse 되게 된다.

즉 해당 requirement를 충족하게 된다.

파이썬에서는 아주 간단하게 해결 할 수 있다.

class Solution:
    def reverseString(self, s):
        s.reverse()

Recursive 기능을 구현한 Helper를 사용해서 아래와 같이 코딩을 할 수 있다.

class Solution {
  public void helper(char[] s, int left, int right) {
    if (left >= right) return;
    char tmp = s[left];
    s[left++] = s[right];
    s[right--] = tmp;
    helper(s, left, right);
  }

  public void reverseString(char[] s) {
    helper(s, 0, s.length - 1);
  }
}

helper 메소드 내에서 자신을 호출함으로서 루프 효과를 내고 있다.

String을 reverse 하는 로직을 똑 같다.

파시썬으로는 아래와 같이 할 수 있다.

class Solution:
    def reverseString(self, s):
        def helper(left, right):
            if left < right:
                s[left], s[right] = s[right], s[left]
                helper(left + 1, right - 1)

        helper(0, len(s) - 1)

오늘의 Leetcode 문제는 118번 Pascal’s Triangle 이다.
난이도는 Easy. 전혀 Easy 하지 않은 것 같은데.
아래가 풀어야 할 문제이다.

우선 패턴을 분석하면 첫줄은 숫자가 한개이고 그 값은 1이다.
두번째 줄은 숫자가 두개이고 그 값은 1과 1이다.
세번째 줄은 숫자가 세개이고 그 값은 1, 2,1 이다. 여기서 2는 윗줄의 1과 1을 더한 것이다.
네번째 줄은 숫자가 네개이고 그 값은 1, 3, 3, 1 이다.
첫번째 3은 윗줄의 첫번째 값 1과 두번째 값 2을 더한 값이다.
두번째 3은 윗줄의 두번째 값 2와 세번째 값 1을 더한 값이다.
다섯번째 줄은 숫자가 다섯개이고 그 값은 1, 4, 6, 4, 1 이다.
첫번째 4는 윗줄의 첫번쨰 숫자 1과 두번째 숫자 3을 더한 값이다.
그 다음 6은 윗줄의 두번째 숫자 3과 세번째 숫자 3을 더한 값이다.
그 다음 4는 윗줄의 세번째 숫자 3과 네번째 숫자 1을 더한 값이다.

이제 패턴을 알 것 같다.
1. 줄이 늘어날 수록 숫자의 갯수는 1씩 증가한다. 첫번째 줄은 한개의 숫자가 있고 그 값은 1이다.
2. 맨 처음 값과 맨 마지막 값은 각각 1이다.
3. 나머지 값들은 윗줄의 (col -1) + 윗줄의 col 값이다. 여기서 col은 해당 숫자가 그 줄의 몇번째에 있는지를 나타내는 것이다.

그럼 각 줄의 맨 처음과 맨 마지막을 제외한 나머지의 값을 구하는 공식은 다음과 같다.

triangle[row][col] = triangle[row-1][col-1] + triangle[row-1][col]

이제 패턴과 그 패턴에 따른 해당 값을 구하는 공식을 완성했으니 코딩을 시작할 차례다.

Example 1의 Output을 보면 그 값은 이중배열이다.

아래와 같이 코딩을 하면 요구 조건을 충족할 수 있다.

class Solution {
   public List<List<Integer>> generate(int numRows) {
       List<List<Integer>> triangle = new ArrayList<>();
       triangle.add(new ArrayList<>());
       triangle.get(0).add(1);
       for(int rowNum =1; rowNum  < numRows; rowNum++) {
           List<Integer> currRow = new ArrayList<>();
           List<Integer> prevRow = triangle.get(rowNum -1);
           currRow.add(1);
           for (int col = 1; col < prevRow.size(); col++) {
               currRow.add(prevRow.get(col-1) + prevRow.get(col));
           }
           currRow.add(1);
           triangle.add(currRow);
       }
       return triangle;
   }
}

한줄 한줄 분석해 보자.

class Solution { ==> 클래스 이름은 Solution이다.
   public List<List<Integer>> generate(int numRows) { ==> 메소드 이름은 generate이다.
==> input 값으로 numRows를 받는다.
==> return 값은 List<List<Integer>>이다.  배열 갯수를 마음대로 변경할 수 있도록 하기 위해서 List를 사용한다.
==> Expected Output 값이 이중 배열이기 때문에 List 안에 또 List를 넣었다. 배열내 값의 데이터 타입은 Integer이다.

       List<List<Integer>> triangle = new ArrayList<>();
==> 결과 값을 저장할 변수를 만든다. 이 변수 이름은 triangle이다.
==> List를 사용하기 위해서는 ArrayList, LinkedList, Vector, Stack 클래스들로 인스턴스 화 할 수 있다.
==> 이 중에서 ArrayList를 생성해서 인스턴스 화 시켰다.

       triangle.add(new ArrayList<>());
==> 이중 배열이기 때문에 triangle안에 ArrayList를 add 했다.

       triangle.get(0).add(1);
==> triangle의 첫 줄에는 값 1을 hardcoding으로 집어 넣었다.

       for(int rowNum =1; rowNum  < numRows; rowNum++) {
==> 결과 값을 만들기 위해 for문을 만들었다. 이 메소드의 input 값인 numRows가 결과 값의 줄의 갯수를 의미하는 것이니, 그 갯수만큼 줄을 만들기 위해서 numRows만큼만 for 문을 돌린다.

           List<Integer> currRow = new ArrayList<>();
==> 현재의 줄을 ArrayList로 인스턴스 화 한다. 이름은 currRow

           List<Integer> prevRow = triangle.get(rowNum -1);
==> 계산을 해서 현재 Row의 각 컬럼의 값을 얻기 위해서 이전 줄의 값을 가져와야 한다. prevRow에 이전 줄의 값들을 저장한다.

           currRow.add(1);
==> 현재 줄의 첫번째 값은 항상 1이다. 이 값을 하드코딩으로 집어 넣었다.

           for (int col = 1; col < prevRow.size(); col++) {
==> 현재 줄의 첫번째 값과 마지막 값을 제외한 중간에 위치한 컬럼의 값을 구하기 위해 for문을 만들었다.
==> 이전 줄의 size보다 한개 작은 숫자 만큼 돌린다.
               currRow.add(prevRow.get(col-1) + prevRow.get(col));
==> 이 코드가 핵심이다.
==> 현재 줄의 현재 컬럼에 이전줄의 현재 컬럼 -1 의 값 + 이전줄의 현재 컬럼 값을 넣어 준다.
           }
           currRow.add(1);
==> 현재 줄의 맨 마지막에는 값 1을 하드코딩으로 넣어 준다.

           triangle.add(currRow);
==> triangle에 현재 줄의 값을 add 한다.
       }

       return triangle;
==> 이중 for 문에서 구한 결과 값을 리턴한다.
   }
}

이렇게 하면 원하는 결과를 얻을 수 있다.
참고로 첫번째 for문은 결과 값이 몇줄이 될 것인지 정하는 것이고,
두번째 for 문은 각 줄에 값들을 구하기 위해 만들어진 것이다.

약간 다른 방법으로는 아래와 같이 할 수도 있다.

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();

        // Base case; first row is always [1].
        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);

        for (int rowNum = 1; rowNum < numRows; rowNum++) {
            List<Integer> row = new ArrayList<>();
            List<Integer> prevRow = triangle.get(rowNum-1);

            // The first row element is always 1.
            row.add(1);
==> 여기 까지는 위와 같다.

            // Each triangle element (other than the first and last of each row)
            // is equal to the sum of the elements above-and-to-the-left and
            // above-and-to-the-right.
            for (int j = 1; j < rowNum; j++) {
==> 위 코드와 다른 것인 이 한 줄이다.
==> 두번째 for문을 rowNum보다 작을 때까지 돌린다.
==> rowNum은 두번째 줄이 1이다. (위 에서 첫번쨰 줄에는 1을 하드 코딩했고 첫번째 for문에서 그 다음 줄을 rowNum = 1 을 했기 때문이다.)
==> 그리고 두번째 for 문에서는 이 rowNum보다 작을 때까지 for문을 돌린다.
==> 그러니까 실질 적으로는 두번째 에서는 줄 -2 만큼 돌리게 된다.
==> 즉 4번째 줄은 4-2 이니까 두개의 값만 구하게 된다.
==> 요구 조건을 충족 시키는 방법이다. 위 코드와는 조금 다르지만 결과 값은 똑 같다.
                row.add(prevRow.get(j-1) + prevRow.get(j));
            }

            // The last row element is always 1.
            row.add(1);
            triangle.add(row);
        }
        return triangle;
    }
}

Python 3의 코딩은 아래와 같다.

class Solution:
    def generate(self, num_rows: int) -> List[List[int]]:
        triangle = []

        for row_num in range(num_rows):
            # The first and last row elements are always 1.
            row = [None for _ in range(row_num + 1)]
            row[0], row[-1] = 1, 1

            # Each triangle element is equal to the sum of the elements
            # above-and-to-the-left and above-and-to-the-right.
            for j in range(1, len(row) - 1):
                row[j] = triangle[row_num - 1][j - 1] + triangle[row_num - 1][j]

            triangle.append(row)

        return triangle