베카의에러뿌시기

LeetCode 문제 중 난이도 Easy인 Unique Morse Code Words 이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제 해석

국제 모스 부호는 다음과 같이 각 알파벳 문자가 일련의 점과 대시에 매핑되는 표준 인코딩을 정의한다.

"a"는 ".-", "b"는 "-...", "c"는 "-.-." 등등..

편의를 위해서 알파벳 전체 26문자의 표는 아래를 참고한다.

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

주어진 단어들의 리스트에서 각 단어들은 각각의 알파벳의 모스부호를 연결해서 쓰여질 수 있다. 예를 들어 "cba"는 "-.-." + "-..." + ".-"인 "-.-.-....-"가 된다. 이렇게 이어진것을 단어 변환이라고 부른다. words중에서 그런 서로 다른 변환의 가짓수를 리턴하라.

* 원본문제의 모스부호 변환 예시가 살짝 틀렸는데 그냥 무시하면 된다. 어쨌든 입력값 words을 모스부호로 변환시 나오는 가짓수를 리턴하면 된다.

이 문제는 그냥 직관적으로 풀면 된다. 단어를 모스부호로 나타냈을 때 나올 수 있는 경우의수가 몇가지인지 알기 위해서는 먼저 input으로 받은 words를 모스부호 문자표를 이용해서 변환해야 한다. 그 다음 변환된 결과들 중에서 중복을 제거한 후 총 나오는 가짓수가 몇개인지 세면 된다.

encoded라는 새로운 배열을 생성해서 words의 단어들을 모스부호화 시켜 저장했다. 그 다음 words를 Set 자료형에 담아 중복값을 제외한다. 마지막으로 Set의 사이즈를 리턴하면 된다. 

12번째줄의 words[i].charAt(j)-'a' 는 알파벳의 아스키코드를 이용한 것이다. 알파벳의 모스부호가 morse배열에 a부터 z까지 순서대로 들어가 있으므로 해당 알파벳-'a'를 하면 그 알파벳이 a부터 몇 번째 뒤에 있는지 알 수 있다. 지난번에 풀었던 Valid Anagram 문제의 두번째 풀이와 같은 원리이다.

2019/04/09 - [프로그래밍문제풀기] - [코딩연습] Valid Anagram 유효한 애너그램인지 체크하기

위 코드의 시간복잡도는 O(S), 공간복잡도는 O(S)이다. 여기서 S는 input인 words배열에 들어있는 단어들의 길이의 합을 말한다.

문제 출처 - https://leetcode.com/problems/unique-morse-code-words/

LeetCode 문제 중 난이도 Easy인 Largest Number At Least Twice of Others이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

정수배열인 nums는 딱 하나의 가장 큰 값을 가지고 있다.

다른 모든 숫자들보다 두배이상 큰 가장 큰 수가 있다면 인덱스 값을 리턴하라. 그렇지 않으면 -1을 리턴한다.

가장 큰 값이 모든 값보다 두배 이상 큰지 보려면 두번째로 큰 값보다 두배 이상 큰지 확인하면 된다. 배열을 돌면서 가장 큰 값(largest)과 두번째로 큰 값(secondLargest)의 인덱스를 탐색한다.

맨 처음에 0,1을 넣고 nums[2]부터 돌면서 i가 largest보다도 큰 가장 큰 값이면 largest의 값을 secondLargest에 넣고 i의 값을 largest에 넣는다. largest보다는 크지 않지만 secondLargest보다 크면 secondLargest를 i로 바꿔준다. 마지막까지 배열을 탐색한 후 nums[secondLargest]*2≤를 만족하면 largest를 리턴하고 아니면 -1을 리턴한다.

마지막 리턴값의 A ? B : C 는 삼항연산자라고 부르고 A가 참이면 B를, A가 거짓이면 C를 반환한다.

배열을 한번 전체탐색하고 추가적인 메모리는 사용하지 않으므로 이 방법의 시간복잡도는 O(n), 공간복잡도는 O(1)이다.

문제 출처 링크 - https://leetcode.com/problems/largest-number-at-least-twice-of-others/

LeetCode 문제 중 난이도 Easy인 Find the Town Judge이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

마을엔 1부터 N으로 표기되는 N명의 사람들이 있다. 이들 중 한사람이 비밀스러운 마을 판사라는 소문이 있다.

만약 마을판사가 존재한다면

1. 마을판사는 아무도 신뢰하지 않는다.

2. 모든사람들(마을판사를 제외한)은 마을판사를 신뢰한다.

3. 위의 1,2 조건을 만족하는 사람은 딱 한명 뿐이다.

입력으로 trust 배열이 주어진다. trust[i]=trust[a,b]는 a가 b를 신뢰한다는 의미이다.

마을판사가 존재한다면 그사람의 번호를 리턴하고 존재하지 않는다면 -1을 리턴하라.

* 1 ≤ N ≤ 1000

* trust.length ≤ 10000

* trust[i] are all different

* trust[i][0] != trust[i][1]

* 1 ≤ trust[i][0], trust[i][1] ≤ N

마을판사가 존재하고 x라고 하자. 모두가 x를 신뢰해야 하므로 ①trust배열 안에 [1,x],[2,x],[3,x]....[n,x]가 전부 있어야 하고 x는 아무도 신뢰하지 않으므로 ②[x,n]은 있으면 안된다.

이 값을 계산하기 위해 tsum[N] 배열을 만들어서 tsum[x-1]에 x를 믿는 사람들의 번호의 합을 저장한다. x가 마을판사이려면 자기자신인 x를 제외한 1~N의 사람들이 전부 x를 신뢰해야 하므로 tsum[x-1][1]은 1~N의 합-x 어야 한다. 그리고 x는 아무도 믿지 않으므로 [x,b]일 때 tsum[x-1]의 값에 -1을 집어넣는다.

이렇게 하면 x를 제외한 모두가 x를 믿는다고 해도 tsum[x-1]의 값은 1~N-x보다 작아진다. -1대신에 아무 음수 또는 N(N+1)/2보다 큰값을 집어넣어도 된다. 코드는 다음과 같다.

이 방법의 시간복잡도는 O(n) 공간복잡도도 O(n)이다.

문제 출처 - https://leetcode.com/problems/find-the-town-judge