알고리즘 day
LeetCode 1. Two Sum
배열이 주어지고, 요소들의 합으로 만들어진 target이 주어진다.
해결방법은 하나 뿐, 요소는 한번만 쓰일 수 있다.
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for (int i = 0; i < nums.length - 1; i++) {
for (int j = 1; j < nums.length; j++){
if(target == nums[i] + nums[j] && i != j){
result[0] = i;
result[1] = j;
return result;
}
}
}
return null;
}
}LeetCode 7. Reverse Integer
32bit 정수 , 뒤집혀서 출력
는 int 범위 안, 범위를 벗어나면 return 0
class Solution {
public int reverse(int x) {
int result = 0;
String str = String.valueOf(Math.abs(x));
String reversedStr = "";
for (int i = str.length() - 1; i >= 0; i--) {
reversedStr += str.charAt(i);
}
try {
return result = x > 0 ? Integer.valueOf(reversedStr) : Integer.valueOf(reversedStr) * -1;
} catch (NumberFormatException e) {
return 0;
}
}
}Integer.valueOf() 부분에서 reversedStr 이 정수 범위를 벗어나게 되면 오류가 발생해서 이부분에서 헤매었다. → 예외처리로 해결
int의 최대값과 최소값
찾아보니 Integer.MAX_VALUE, Integer.MIN_VALUE 라는 것이 있다.
정수의 최대값과 최소값을 바로 얻을 수 있다.
문자열 거꾸로 출력하기 (reverse String)
StringBuffer 사용, for문 사용 두가지 방법이 있다.
for (int i = str.length() -1; i>=0; i--) {
System.out.print(str.charAt(i));
}LeetCode 83. Remove duplicates from sorted List
Remove Duplicates from Sorted List - LeetCode
주어진 정렬된 링크드 리스트에서 중복된 값을 제거한다.
결과값도 정렬된 링크드 리스트이어야 함
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode current = head;
while(current != null && current.next != null){
if(current.val == current.next.val){
ListNode tmp = current.next;
current.next = tmp.next;
} else current = current.next;
}
return head;
}
}-
while(current.next ! = null) 부분에서 NullPointerException 이 뜬다.
→ while(current != null && current.next != null) 로 변경하니 해결됨
-
solution을 살짝 봤는데 return head; 인데 왜 head 를 리턴하는지... 몰랐었는데 알겠다. 어차피 head 뒤에 next 들이 연결되어 있으니까!
-
처음에 current = curret.next; 를 else로 안했는데 꼭 else로 묶어주어야 한다.
-
처음에 if 구문에서 겹치는 노드를 없애고, current가 다음 칸으로 옮겨져서 다음 칸에서 또 next의 val 과 비교하는 것을 수행해야 한다고 생각해서 else 구문을 else 로 감싸지 않고 그냥 넣었다.
노트에 그림을 그려보니, 같은 val 를 가진 노드가 2개보다 더 많을 수 있는 경우에는 current 가 다음 칸으로 넘어가지 않고, next 랑 또 비교를 해주어야 같은 val을 가진 노드가 3개 혹은 그 이상일 때도 그 노드를 없앨 수 있다는 것을 이해했다.
따라서, else 로 감싸주어야 한다.
예) [1, 1, 1, 2, 2] 그림그려서 해보기
-
LeetCode 9.Palindrome Number
class Solution {
public boolean isPalindrome(int x) {
String str = "" + x;
String reversedStr = "";
for(int i = str.length()-1; i >= 0; i--){
reversedStr += str.charAt(i);
}
if(str.equals(reversedStr)) return true;
else return false;
}
}LeetCode 14. Longest Common Prefix
Longest Common Prefix - LeetCode
주어진 String 들 중 공통 접두사 찾기
- 아직 미해결.. 어렵군
자바의 정석 ch7 객체지향 프로그래밍 2
인터페이스(interface)
-
추상 클래스와 인터페이스의 공통점은?
- 추상 메서드를 가지고 있다. (미완성 설계도)
-
추상 클래스와 인터페이스의 차이점은? (면접 문제로 출제된 적 있음)
-
추상 클래스는 생성자, 멤버변수를 갖고 있는 일반 클래스에 추상메서드를 포함하고 있는 것
-
인터페이스는 추상 메서드의 집합, 상수와 추상메서드만 가질 수 있음
인스턴스 변수와 인스턴스 메서드, 생성자를 가질 수 없다.
(단, jdk1.8 부터는 static 메서드와 default 메서드를 추가할 수 있다. 하지만 원래 규칙도 알아야 함)
-
인터페이스란?
- 추상 메서드의 집합
- 구현된건 아무것도 없는 껍데기
인터페이스의 작성
-
interface 키워드
-
상수만 선언 가능, 무조건 public static final 이기 때문에 제어자를 생략할 수 있다.
→ 멤버변수(cv, iv)는 가질 수 없다.
-
메서드는 무조건 public abstract 이어야 하며, 제어자 생략 가능
(단, JDK1.8 부터는 static메서드와 default 메서드 포함 가능)
인터페이스의 상속
- interface의 조상은 interface만 가능
- 클래스와 달리 Object 클래스와 같은 최고 조상이 없다.
- 다중상속이 가능하다.(클래스는 안됨)
- 다중 상속의 문제는 메서드의 충돌인데, 클래스는 여러개의 조상을 한번에 상속받을 수 없지만, 인터페이스는 추상메서드의 집합이여서 추상메서드는 선언부만 구현되어 있어서 충돌할 문제가 없기때문에 다중 상속이 가능하다.
인터페이스의 구현
- 인터페이스에 정의된 추상 메서드를 완성하는 것
- 키워드 implements(구현한다는 의미) 사용 (클래스는 extends)
- 만약 인터페이스를 구현한 클래스가 인터페이스의 메서드 중 일부만 구현한다면, 그 클래스는 추상클래스(abstract)로 선언해야 한다.
- 인터페이스의 이름은 주로 ~able 임
public class Practice {
public static void main(String[] args) {
Fighter f = new Fighter();
if(f instanceof Unit) System.out.println("f는 Unit의 자손입니다.");
if(f instanceof Fightable) System.out.println("f는 Fightable 인터페이스를 구현하였습니다.");
if(f instanceof Movable) System.out.println("f는 Movable 인터페이스를 구현하였습니다.");
if(f instanceof Attackable) System.out.println("f는 Attackable 인터페이스를 구현하였습니다.");
if(f instanceof Object) System.out.println("f는 Object의 자손입니다.");
}
}
class Fighter extends Unit implements Fightable {
@Override
public void move(int x, int y) {
System.out.println("move");
}
@Override
public void attack(Unit u) {
System.out.println("attack");
}
}
class Unit {
int currentHP;
int x;
int y;
}
interface Movable { void move(int x, int y); }
interface Attackable { void attack(Unit u); }
interface Fightable extends Movable, Attackable {}- 위의 예시 코드에서 중요한 점은 Movable 인터페이스에 정의된 move()를 Fighter 클래스에서 구현할 때 접근 제어자가 public 이라는 것이다.
- 오버라이딩할 때는 조상의 메서드보다 넓은 범위의 접근 제어자를 지정해야 한다.
- Movable에서의 move()는 사실 public abstract 이고, 이것이 생략되어 있는 것이기 때문에 실제로는 public abstract void move(int x, int y) 이다.
- 따라서, Fighter 클래스에서는 이를 public 으로 구현해주어야 한다.
인터페이스를 이용한 다형성 (중요!) (387p)
-
다형성이란?
- 조상 타입의 참조변수로 자손 클래스의 객체를 가르키는 것
- 예) Tv t = new SmartTv();
-
인터페이스도 엄밀히 말하면 이 인터페이스를 구현한 클래스의 조상이라고 할 수 있다.
-
해당 인터페이스 타입의 참조변수로 이 인터페이스를 구현한 클래스의 인스턴스를 참조할 수 있다.
- Fightable f = new Fighter();
- 여기서 f로는 Fightable에 정의된 멤버들만 호출 가능하다.
-
인터페이스는 메서드의 매개변수 타입으로 사용될 수 있다.
- void attack(Fightable f) { ... }
- 해당 인터페이스를 구현한 클래스의 인스턴스를 매개변수로 제공해야 한다는 의미 (중요**)
- attack() 메서드를 호출할 때는 매개변수로 Fightable 을 구현한 클래스의 인스턴스를 넘겨주어야 한다.
- class Fighter extends Unit implements Fightable { ... }
- attack()의 매개변수로 위에 있는 Fighter의 인스턴스를 넘겨줄 수 있다.
- 즉, attack(new Fighter()); 와 같이 실행할 수 있다.
인터페이스의 장점
- 인터페이스
- 두 대상(객체 간의) '연결, 대화, 소통'을 돕는 '중간 역할'을 한다.
- 장점
- 개발시간을 단축시킬 수 있다.
- 일단 인터페이스가 작성되면 이를 사용해서 프로그램 작성이 가능하므로 개발시간 단축 가능
- 표준화가 가능하다.
- 기본 틀을 인터페이스로 작성하면 일관되고 정형화된 프로그램 개발이 가능하다.
- 서로 관계 없는 클래스들에게 관계를 맺어줄 수 있다.
- 서로 상속 관계에 있지도 않고, 같은 조상클래스를 갖고 있지 않아도 인터페이스를 공통적으로 구현하도록 함으로써 관계를 맺어 줄 수 있다.
- 독립적인 프로그램이 가능하다.
- 선언과 구현을 분리 시킬 수 있다.
- 변경에 유리한 설계가 가능하다, 유연한 코드
- 개발시간을 단축시킬 수 있다.
오늘 한 일
- LeetCode 알고리즘 풀었다, 14번 풀다가 막혔지만 꼭 다시 풀어봐야지
- 알고리즘 잘 안 풀려서 자바의 정석 인터페이스 부분 강의듣고 학습했다. 예제코드 작성해보고 이해는 했지만 다른 부분처럼 익숙하진 않아서 여러번 반복해야겠다. 뒤에 디폴트 메서드와 static 메서드 파트는 훑어보고 따로 학습정리를 하진 않았다.
- 오늘부터 한 조원분이 진행하고 있다는 자바의 정석 스터디에 참여하게 되었다. 매일매일 자바 실력을 키운다는 느낌으로 무리없이 임하자.
- 지금 하는 cs10 도 중요하지만 지금 미션을 잘 구현하기 위해서, 그리고 이후에 진행할 과정을 위해서 자바의 실력을 키워야겠다.
- github에 알고리즘 저장소 생성
Todo
- 인터페이스의 다형성 부분 여러번 반복해서 학습하자(특히 Parser예제 부분 이해가 가긴 하지만 좀 어렵다.)
어제 공부 엄청 많이하셨네요. 알고리즘도 4개나 해결하셨군요..👏