Partially Committed

오늘 풀어볼 문제 상황은 Tournament Winner 이다. Problem solving 실력을 겨루는 Tournament Winner 는 아래의 규칙을 따른다. 각각의 team 은 서로 다른 언어(C#, Python ...)를 사용한다. 경기 방식은 round-robin 리그제이며 각 경기 당 home team, away team 이 지정된다. 대진표는 competitions 2차원 배열에 제시되며 경기 결과는 results 배열로 주어진다. competitions = [ ["HTML", "C#"], ["C#", "Python"], ["Python", "HTML"], ] results = [0, 0, 1] 위와 같이 주어졌을 때, 각각의 대진표의 앞의 팀은 home, 뒤에 팀은 away 이다. 그리..

오늘은 보다 간단한 문제에 대해서 알아보자. Ascending order 로 정렬된 input array 가 주어졌을 때, Sorted Sqaured output array 를 반환하라는 문제 상황이다. 예를 들어 [1,2,3,4,5] 가 주어지면 [1,4,9,16,25] 를 반환한다. 가장 쉽게 떠오르는 것은 그냥 input array 를 순회하며 squared value 를 원소로 가지는 배열을 만든 다음 sorting 해서 반환해주는 방법이다. 이렇게 구현한 경우에는 시간 복잡도는 O(NlogN) 이고 공간 복잡도는 O(N) 이다. #include using namespace std; // time : O(NlogN) // space : O(N) vector sortedSquaredArray(vec..

오늘은 보다 간단한 상황에 대해서 공부해보자. 바로 Subsequence 판단 문제인데, Subsequence 의 정의는 아래와 같다. In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. - wiki 배열이 주어졌다고 가정하면, 원소의 순서를 바꾸는 행위 없이 일부 원소만 delete 하여 origin array 로부터 subsequence 을 만들어낼 수 있다. 예를 들어 [1,5,7,9] 에 대해서 [1, 5]..

배열이 주어지고, 배열 내에서 특정 조건을 만족하는 원소 쌍을 검색하는 문제 상황을 해결하는 방법에 대하여 공부해보자. 가령, 이런 상황이다. 유한 길이의 1 - d array 가 주어졌을 때, 두 원소의 합이 targetNum 이 되도록 하는 원소 쌍을 찾아라. 어떠한 조합으로도 targetNum 을 만들 수 없다면 empty vector 을 반환하라. 두 원소의 합이 targetNum 이 되도록 하는 원소 쌍은 유일하다. 면접에서 이 문제를 물어봤다고 가정하고, 차근차근 논리를 전개해보자. 먼저, 역으로 물어봐야 할 것은 어느 정도의 시간과 메모리를 허용하는지, 당연한 소리겠지만 원소의 타입은 integer 인지 그리고 2개의 원소에 대해서 조건을 만족하면 되는지, 반환해야하는 vector 내의 원소..

TITLE : 496. Next Greater Element I Description : The next greater element of some element x in an array is the first greater element that is to the right of x in the same array. You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2. For each 0

TITLE : 1790. Check if One String Swap Can Make Strings Equal Description : You are given two strings s1 and s2 of equal length. A string swap is an operation where you choose two indices in a string (not necessarily different) and swap the characters at these indices. Return true if it is possible to make both strings equal by performing at most one string swap on exactly one of the strings. Ot..

TITLE : 202.Happy Number Description : Write an algorithm to determine if a numbernis happy. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for whic..

TITLE : 1502. Can Make Arithmetic Progression From Sequence Description : A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same. Given an array of numbers arr, return true if the array can be rearranged to form an arithmetic progression. Otherwise, return false. Example 1: Input: arr = [3,5,1] Output: true Explanation: We can..