코딩 이야기

https://blog.naver.com/ndb796/221226803544

https://blog.naver.com/ndb796/221226800661 

안경잡이 개발자 [알고리즘] 강의 기반으로 정리하였습니다.

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

1 10 5 8 7 6 4 3 2 9 

[ 문제 풀이 ]

i, j는 배열의 있는 원소들을 반복적으로 탐색하기 위해서 사용

min은 최소값을 의미, 가장 반복적으로 사용하는 것을 선택해야한다. 

index 가장 작은 원소가 존재하는 위치가 index

temp 특정한 두숫자는 서로 바꾸기 위해서 사용된다. 

10개의 원소를 탐색하기 위해서 10번을 반복한다는 의미로 아래와 같은 코드를 작성한다. 

int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };
for(i = 0; i < 10; i++) {

}

맨처음에 min 값에는 아주 큰 값을 넣어준다. 예를 들면 그대로 9999

min = 9999;

숫자가 만약에 9999보다 큰 숫자가 있다면 이런 식으로 하면 안 되겠죠? 모든 원소들보다 큰 숫자 아무 숫자나

무작위로 넣어줄꺼에요.

min 값은 항상 최소값을 선택해야되기때문에 가장 큰 값을 넣어주죠 

자 이제 j 는 i부터 시작해서 10 까지 반복을 하는데, 이제 여기에서 최소값을 골라주는 거에요. 

현재 탐색하고 있는 그 원소가 현재 최저값보다 더 작다면 -> 최저값을 현재 탐색하고 있는 그 원소로 바꿔준다. 

for(j = i; j < 10; j ++) {
if(min < array[j]) {
	min = array[j];
    index = j;
    }
 }

이코드는 배열중에 가장 작은 값을 선택한다는 코드이다. 이제 그 가장 작은 값을 맨 앞으로 보내는 로직을 보자. 

일단 temp라는 변수에 가장 앞에 있는 값을 넣어주고 array[i];

가장 앞에 있는 원소로 최소값을 넣어준뒤에 array[index];

다시 최소값이 있는 위치에 temp에 들어있는 값을 넣어준다. 아래와 같은 방식은 스왑핑한다. 

두개의 있는 원소를 바꿔준다는 의미이다. 이 3줄은 앞에 있는 값과 최소값을 바꿔준다는 의미이다. 

temp = array[i];
array[i] = array[index];
array[index]  = temp;

 그니깐 처음에

1 10 5 8 7 6 4 3 2 9 를 살펴보고 for문 돌고

5 8 7 6 4 3 2 9 범위 살펴보고 for문 돌고

7 6 4 3 2 9 범위 살펴보고 for문 돌고

6 4 3 2 9 범위 살펴보고 for문 돌고 이런식으로 가장 작은 것을 선택해서 앞으로 보내준다. 이것을 반복하는 소스코드이다. 

이제 정렬이 완성된 코드는 아래와 같이 출력해준다. 

for(i = 0; i < 10; i++) {

printf("%d ", array[i]);

}

선택 정렬의 알고리즘의 단점 : 시간이 많이 걸린다.  N * (N + 1) / 2

=> O(N * N) 특정한 알고리즘의 수행 시간을 시간을 가장 간략하게 표현하는 것이 바로 이 빅오 O 표기법이다. 

특정 알고리즘의 연산횟수를 간략하게 표현했다. O 빅오 표기법. 

선택정렬의 시간 복잡도는 O(N * N )

효율적인지는 고민해볼것!

선택정렬 끝

LeetCode 영어 문제

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

번역

정수 배열 숫자가 주어지면 가장 큰 합계를 가진 연속 된 하위 배열 (하나 이상의 숫자 포함)을 찾아서 그 합계를 반환합니다.

예:

입력 : [-2,1, -3,4, -1,2,1, -5,4],

출력 : 6

설명 : [4, -1,2,1]의 합계는 6입니다.

후속 조치 : O (n) 솔루션을 알아 낸 경우 더 미묘한 나누기 및 정복 방법을 사용하여 다른 솔루션을 코딩 해보십시오.

다른 사람의 풀이

1

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        int accu = nums[0];
        int max = accu;
        for(int i = 1; i < nums.length; i++){
            accu += nums[i];
            if(nums[i] > accu){
                accu = nums[i];
            }
            max = Math.max(max, accu);
        }
        return max;
    }
}

2

class Solution {

public int maxSubArray(int[] a) {
    int max_so_far = Integer.MIN_VALUE;
    int max_end = 0;
    
    for(int i = 0; i < a.length; i++) {
        max_end = max_end + a[i];
        if(max_so_far < max_end) {
            max_so_far = max_end;
        }
        if(max_end < 0) {
            max_end = 0;
        }
    }
    return max_so_far;
}
}

3

똑같은 코드를 reduce()가 아닌 forEach() 함수로 적용해보았다.

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) return 0;
        int curr = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curr = Math.max(nums[i], curr + nums[i]);
            max = Math.max(max, curr);
        }
        return max;
    }
}

4

cur라는 변수에 0과 배열의 값을 누적해서 더한 값을 비교하여 더 큰 값을 담는다.

즉, 값이 음수가 되면 0을 return한다. 

내가 if(av < 0) { av = 0; }라고 적은 것과 같은 문장이다.

그리고 max와 cur를 비교해서 더 큰 값을 max에 담는다.

var maxSequence = function(arr){
	var max = 0;
	var cur = 0;
	arr.forEach(function(i){
		cur = Math.max(0, cur + i);
		max = Math.max(max, cur);
	});
	return max;
}

5

var maxSequence = function(arr){
	var max = 0, sum = 0;
	arr.forEach(function(num) {
	sum += num;
		if (sum < 0) {
			sum = 0;
		}
		if (sum > max) {
		max = sum;
		}
	});
	return Math.max(sum, max);
}

풀이

출처 sources

• https://leetcode.com/problems/maximum-subarray/

https://im-developer.tistory.com/70 [Code Playground]

LeetCode 영어 문제

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()" Output: true

Example 2:

Input: "()[]{}" Output: true

Example 3:

Input: "(]" Output: false

Example 4:

Input: "([)]" Output: false

Example 5:

Input: "{[]}" Output: true

번역

'(', ')', '{', '}', '['및 ']'문자 만 포함 된 문자열이 있으면 입력 문자열이 유효한지 판별하십시오.

다음과 같은 경우 입력 문자열이 유효합니다. 열린 브래킷은 동일한 유형의 브래킷으로 닫아야합니다.

열린 브래킷은 올바른 순서로 닫아야합니다. 빈 문자열도 유효한 것으로 간주됩니다.

예 1 : 입력 : "()" 출력 : true

예 2 : 입력 : "() [] {}" 출력 : true

예 3 : 입력 : "(]" 출력 : false

예 4 : 입력 : "([)]" 출력 : false

예 5 : 입력 : "{[]}" 출력 : true

다른 사람의 풀이

class Solution {

  // Hash table that takes care of the mappings.
  private HashMap<Character, Character> mappings;

  // Initialize hash map with mappings. This simply makes the code easier to read.
  public Solution() {
    this.mappings = new HashMap<Character, Character>();
    this.mappings.put(')', '(');
    this.mappings.put('}', '{');
    this.mappings.put(']', '[');
  }

  public boolean isValid(String s) {

    // Initialize a stack to be used in the algorithm.
    Stack<Character> stack = new Stack<Character>();

    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);

      // If the current character is a closing bracket.
      if (this.mappings.containsKey(c)) {

        // Get the top element of the stack. If the stack is empty, set a dummy value of '#'
        char topElement = stack.empty() ? '#' : stack.pop();

        // If the mapping for this bracket doesn't match the stack's top element, return false.
        if (topElement != this.mappings.get(c)) {
          return false;
        }
      } else {
        // If it was an opening bracket, push to the stack.
        stack.push(c);
      }
    }

    // If the stack still contains elements, then it is an invalid expression.
    return stack.isEmpty();
  }
}

class Solution {
    public boolean isValid(String s) {
        if (s.isEmpty()) {
            return true;
        }
        char[] stack = new char[s.length()];
        int head = 0;
        for (char c : s.toCharArray()) {
            switch (c){
                case '{': 
                    stack[head++] = '}'; 
                    break;
                case '[': 
                    stack[head++] = ']'; 
                    break;
                case '(': 
                    stack[head++] = ')'; 
                    break;
                default:
                    if (head == 0 || stack[--head] != c) {
                        return false;
                    }
            }
        }
        return head == 0;
    }
} 

여니여니의 해석

출처 sources

• https://leetcode.com/problems/valid-parentheses/solution/

LeetCode 영어 문제

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"] Output: "fl"

Example 2:

Input: ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

번역

모든 주어진 문자열 배열을 통틀어서 가장 긴 접두사를 구하라. 만약 공통된 접두사가 없으면 ""를 반환해라
예 1 :

입력 : [ "flower", "flow", "flight"]

출력 : "fl"

예 2 :

입력 : [ "dog", "racecar", "car"]

출력 : "" 설명 : 입력 문자열 사이에 공통 접 두부가 없습니다. 노트 : 주어진 모든 입력은 소문자 a-z입니다.

다른 사람의 풀이

1

 public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++)
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }        
    return prefix;
}

2

간단한 문제다. 각 문자열의 문자를 가르키는 공통된 인덱스 변수를 두고 그 변수를 따라서 공통 접두사를 구하면 된다.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size() == 0)
            return "";
 
        int loc=0;
        int minSize = 9999999;
        for(string s : strs){
            minSize = std::min(minSize, (int)s.size());
        }
 
        string ret="";
        bool flag = true;
        for(int i=0; i<minSize; ++i){
            char currentChar = strs[0][i];
            flag = true;
            for(int j=0; j<strs.size(); ++j){
                if(currentChar != strs[j][i]){
                    flag = false;
                    break;
                }
            }
            if(!flag)
                break;
            ret += strs[0][i];
        }
         
        return ret;
    }
};

풀이

출처 sources

• https://leetcode.com/problems/longest-common-prefix/

https://engkimbs.tistory.com/652

https://engkimbs.tistory.com/652

LeetCode 영어 문제

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III" Output: 3

Example 2:

Input: "IV" Output: 4

Example 3:

Input: "IX" Output: 9

Example 4:

Input: "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

번역

[로마숫자를 정수로 바꾸는 문제]

로마 숫자는 I, V, X, L, C, D 및 M의 7 가지 기호로 표시됩니다. 기호 값 I 1 V 5 X 10 L 50 C 100 D 500 M 1000

예를 들어, 두 개는 로마 숫자로 II로 표기되며 두 개만 더해집니다. 12 개는 XII로 작성되는데 이는 단순히 X + II입니다.

숫자 27은 XXVII로 쓰여지며 XX + V + II입니다. 로마 숫자는 일반적으로 왼쪽에서 오른쪽으로 가장 크거나 가장 작습니다.

그러나 4의 숫자는 IIII가 아닙니다. 대신, 숫자 4는 IV로 작성됩니다.

하나는 5 앞에 있기 때문에 우리는 4를 뺍니다. 같은 원칙이 9 번에 적용되며 IX로 작성됩니다.

빼기가 사용되는 6 가지 경우가 있습니다. V (5)와 X (10) 앞에 배치하여 4와 9를 만들 수 있습니다.

X는 L (50)과 C (100) 앞에 위치하여 40과 90을 만들 수 있습니다.

C는 D (500)와 M (1000) 앞에 위치하여 400과 900을 만들 수 있습니다. 로마 숫자가 주어지면 정수로 변환하십시오.

입력은 1-3999 범위 내에 있어야합니다.

예 1 : 입력 : "III"출력 : 3

예 2 : 입력 : "IV"출력 : 4

예 3 : 입력 : "IX"출력 : 9

예 4 : 입력 : "LVIII"출력 : 58 설명 : L = 50, V = 5, III = 3

예 5 : 입력 : "MCMXCIV"출력 : 1994 설명 : M = 1000, CM = 900, XC = 90 및 IV = 4

다른 사람의 풀이

1

class Solution {
    public int romanToInt(String s) {
        int result = 0;
        int temp = 0;
        int[] answer = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'I') answer[i] = 1;
            else if (s.charAt(i) == 'V') answer[i] = 5;
            else if (s.charAt(i) == 'X') answer[i] = 10;
            else if (s.charAt(i) == 'L') answer[i] = 50;
            else if (s.charAt(i) == 'C') answer[i] = 100;
            else if (s.charAt(i) == 'D') answer[i] = 500;
            else if (s.charAt(i) == 'M') answer[i] = 1000;   
        }
        for (int i = s.length()-1; i >= 0; i--) {
            if (answer[i] >= temp) result += answer[i];
            else result -= answer[i];
            temp = answer[i];
        }
        return result;
    } 
}

2

class Solution {
    public int romanToInt(String s) {
        int smallestVal = 1000;
        int total = 0;
        int current = 0;
        for (char c : s.toCharArray()) {
            if (c == 'M') {
                current = 1000;
            } else if (c == 'D') {
                current = 500;
            } else if (c == 'C') {
                current = 100;
            } else if (c == 'L') {
                current = 50;
            } else if (c == 'X') {
                current = 10;
            } else if (c == 'V') {
                current = 5;
            } else if (c == 'I') {
                current = 1;
            }
            if (current > smallestVal) current -= (2 * smallestVal);
            else if (current < smallestVal) smallestVal = current;
            total += current;
        }
        return total;
    }
}

3

문제는 어렵지 않은데 예외처리를 일일이 해줘야하는게 귀찮았음.

먼저 각각 문자가 뜻하는 숫자를 roman에 담고, 특별한 경우를 따로 special에 담는다.

우선 길이가 1개일 때 roman에서 매칭되는 값을 리턴해주고

길이가 2개 이상인 경우에는 먼저 special에 해당하는 문자가 있는지 찾아서 result에 더해준 뒤에 문자열에서 삭제해주는 포문을 하나 돌리고

남은 값들을 roman에서 매칭시켜 result에 더해주고 리턴하면 끝

객체로 묶는 생각을 바로 못해서 일일이 if문으로 했다가, 나중에 수정했음

const romanToInt = s => { 
	const roman = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000};
	if ( s.length === 1 ) {
	return roman[s] 
	} let result = 0; const special = { 
	'IV': 4, 'IX': 9, 'XL': 40, 'XC': 90, 'CD': 400, 'CM': 900 
	} for ( let i = 0; i < s.length-1; i++ ) 
	{ if ( special[s[i]+s[i+1]] ) 
	{ result += special[s[i]+s[i+1]]; s = s.replace(s[i]+s[i+1], ''); i = -1 } } 
	for ( let j = 0; j < s.length; j++ ) {
    result += roman[s[j]] } return result };

풀이

for문을 통해 따로 sum 에 더해주는 방식으로 처리했다. 그리고 현재 문자가 다음 문자보다 작으면 오히려 빼주는데, 그렇게 하면 4내지는 9가 나오게 된다.

출처 sources

• https://leetcode.com/problems/roman-to-integer/

• https://takeuu.tistory.com/164?category=760767 [워너비스페셜]

LeetCode 영어 문제

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123 Output: 321

Example 2:

Input: -123 Output: -321

Example 3:

Input: 120 Output: 21

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

번역

32 비트 부호있는 정수가 주어지면 정수의 반대 자릿수입니다.

예 1 : 입력 : 123 출력 : 321

예 2 : 입력 : -123 출력 : -321

예 3 : 입력 : 120 출력 : 21

노트 : 32 비트 부호있는 정수 범위 [-231, 231-1] 내의 정수만 저장할 수있는 환경을 처리한다고 가정합니다. 이 문제의 목적을 위해, 역 정수가 오버 플로우 될 때 함수가 0을 리턴한다고 가정하십시오.

다른 사람들의 풀이

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

    public int reverse(int x) {
        int result = 0;
        while(x != 0){
            int remain = x % 10;
            int tmp = result * 10 + remain;
            if(result != (tmp - remain) /10) {
                return 0;
            }
            result = tmp;
            x = x / 10;
        }
        return result;
    }

class Solution {
    public int reverse(int x) {
        long rev = 0;
        while (x != 0) {
            rev = 10 * rev + x % 10;
            x = x / 10;
        }
        return rev > Integer.MAX_VALUE || rev < Integer.MIN_VALUE
               ? 0
               : (int) rev;
    }
}

class Solution {
    public int reverse(int x) {
        int prevRev = 0;
        int rev = 0;
        while (x != 0) {
            rev = 10 * rev + x % 10;
            if ((rev - x % 10) / 10 != prevRev) {
                return 0;
            }
            prevRev = rev;
            x = x / 10;
        }
        return rev;
    }
}

풀이

출처 sources

• https://leetcode.com/problems/reverse-integer/

LeetCode 영어 문제

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

번역

정수 배열이 주어지면 두 숫자의 인덱스를 반환하여 특정 목표에 합산합니다.

각 입력에 정확히 하나의 솔루션이 있다고 가정하고 동일한 요소를 두 번 사용할 수 없습니다.

예:

주어진 숫자 = [2, 7, 11, 15], target = 9, 숫자 [0] + 숫자 [1] = 2 + 7 = 9이므로 [0, 1]을 반환합니다.

다른 사람의 풀이

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

풀이

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

2 + 7 = 9을 예제로 들면, i 가 2 이고 j 가 7 이고 9가 target이라고 가정했을때

i + j = target

j = target - i 가 된다. 그래서 이중포문안에 

if (nums[j] == target - nums[i]) {

 return new int[] { i, j };

} 가 들어간다.

출처 sources

• https://leetcode.com/problems/two-sum/solution/