이 문제는 스택을 사용하면 효율적으로 해결할 수 있습니다. 스택을 사용하기전 단순하게 접근을 했을떄, 직관적인 해결법은 왼쪽으로 모든 이전 탑을 확인하며, 자신보다 높은 첫 번째 탑을 찾는 것입니다.
예: 5번 탑(높이 4)의 경우, 4번(7), 3번(5), 2번(9), 1번(6)을 순서대로 확인.
4번 탑(높이 7)이 높이 4보다 크므로 여기서 수신.
위 내용이 이해가 되셨다면 이 문제가 왜 완전 탐색이 비효율적인지 알아봅시다
N=500,000 N = 500,000 N=500,000일 때, 500,000×500,000≈250,000,000,000 500,000 \ times 500,000 \approx 250,000,000,000 500,000×500,000≈250,000,000,000 연산.
이는 일반적인 시간 제한(1~2초) 내에 처리하기 어렵습니다. 즉 따라서 더 효율적인 방법을 찾아야 합니다.
완전탐색이 비효율적인것은 확인했습니다. 그렇다면 스택은 왜 적합할까요 ? 문제 분석을 정확히 했다면 우리는 이전 탑들 중 더 높은 탑만 유지하면 됩니다. 스택은 가장 최근의 데이터를 빠르게 접근하고, 불필요한 데이터를 제거하는 데 최적입니다.
스택에 탑의 높이와 인덱스를 저장.
새 탑을 처리할 때, 스택의 top 탑이 현재 탑보다 낮으면 pop (이 탑은 더 이상 필요 없음).
스택의 top 탑이 현재 탑의 레이저를 수신.
현재 탑을 스택에 push.
이 패턴을 이해했을경우 왜 낮은 탑을 스택에서 제거하나? 라고 질문이 나올수있습니다. 만약 스택의 top 탑이 현재 탑보다 낮다면, 이후 탑들의 레이저는 현재 탑에서 먼저 수신되거나, 더 높은 탑을 찾을 것이므로 그 탑은 더 이상 필요 없습니다.
예: 높이 [6, 9, 5]에서, 3번 탑(높이 5)을 처리할 때 2번 탑(높이 9)이 스택에 있으면 1번 탑(높이 6)은 제거됨. 이유는 2번 탑이 더 가까우면서도 높기 때문입니다.
시간 복잡도는 최대 한번 push 되고 최대 한 번.pop 됩니다. 따라서 O(N) 압나다
코드를 보시면 아시겠지만 레이저는 왼쪽 방향으로 나아가는데 왜 정방향으로 탐색하나? 라고 생각될수있습니다.
문제는 탑을 왼쪽부터 오른쪽으로 번호를 매기고, 레이저도 왼쪽으로 발사됩니다. 정방향(1번 탑부터)으로 탐색하면, 스택에 이전 탑들을 순서대로 쌓고, 필요 없는 탑을 제거하며 자연스럽게 수신 탑을 찾을 수 있습니다. 역순 탐색도 가능하지만, 정방향이 문제의 흐름과 더 직관적이고 가독성이 좋습니다.
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br;
static int[] towerHeights;
static class Tower {
int index;
int height;
public Tower(int index, int height) {
this.index = index;
this.height = height;
}
}
static void input() {
try {
// 배포용 표준 입력
br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
towerHeights = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine().trim());
for (int i = 0; i < n; i++) {
int height = Integer.parseInt(st.nextToken());
towerHeights[i] = height;
}
} catch (IOException e) {
System.err.println("입력 오류: " + e.getMessage());
}
}
static int[] solve() {
int n = towerHeights.length;
int[] receivers = new int[n];
Stack<Tower> stack = new Stack<>();
for (int i = 0; i < n; i++) {
// 현재 탑보다 높이가 낮은 탑은 스택에서 제거
while (!stack.isEmpty() && stack.peek().height <= towerHeights[i]) {
stack.pop();
}
// 스택이 비어 있으면 수신 탑 없음(0), 아니면 스택의 top 탑이 수신 탑
receivers[i] = stack.isEmpty() ? 0 : stack.peek().index;
// 현재 탑을 스택에 추가 (1-based 인덱스)
stack.push(new Tower(i + 1, towerHeights[i]));
}
return receivers;
}
public static void main(String[] args) {
input();
int[] receivers = solve();
// StringBuilder로 출력 최적화
StringBuilder sb = new StringBuilder();
for (int receiver : receivers) {
sb.append(receiver).append(" ");
}
System.out.println(sb.toString().trim());
}
}
DIP (Dependency Inversion Principle) 는 의존성 역전 준말로 아래와 같은 원칙을 가지고 있습니다.
A. 상위 모듈은 하위 모듈에서 아무것도 가져오지 않아야 한다. B. 추상화는 세부 사항에 의존해서는 안 됩니다. 세부 사항(구체적 구현)은 추상화에 의존해야 합니다.
DIP 원칙을 처음 봤을 때 구현에 의존하지 말고 추상화 계층에 의존을 하라는 이전의 원칙과 비슷하게 느꼈습니다. 하지만 DIP는 단순히 인터페이스에 의존하는 것을 넘어, 고 수준 모듈과 저 수준 모듈의 관계까지 아우르는 원칙입니다. 즉 전체 시스템의 모듈들이 구체적인 구현에 의존하지 않는다면 유연하게 소프트웨어를 확장을 할 수 있습니다.
DIP 관련 예시를 살펴 보겠습니다.
알림이라는 클래스가 이메일 서비스와 SMS 서비스 라는 구체적인 하위 모듈이 직접적으로 의존을 하고 있습니다. 코드로 구현을 한다면 아래와 같습니다.
class EmailService {
public void sendEmail(String message) {
System.out.println("이메일 전송: " + message);
}
}
class SMSService {
public void sendSMS(String message) {
System.out.println("SMS 전송: " + message);
}
}
class Notification {
private EmailService emailService;
private SMSService smsService;
public Notification() {
this.emailService = new EmailService();
this.smsService = new SMSService();
}
public void sendEmailNotification(String message) {
emailService.sendEmail(message);
}
public void sendSMSNotification(String message) {
smsService.sendSMS(message);
}
}
해당 코드는 아래와 같은 문제점이 있습니다.
sendEmail 과 sendSMS 메서드를 호출할 때 알림 모듈이 각 서비스의 구체적인 구현에 종속되어 있어, 서비스가 변경되거나 새로운 알림 방식이 추가될 경우 알림 모듈을 수정해야 합니다.
이로 인해 확장성이 떨어지고, 유연하게 새로운 기능을 추가하거나 유지 보수하는 데 어려움이 있습니다.
DIP 적용된 예시를 위해 위 이미지처럼 설계를 하였고 아래와 같이 코드를 작성했습니다.
// 알림 서비스 인터페이스
interface NotificationService {
void send(String message);
}
// 이메일 서비스 클래스
class EmailService implements NotificationService {
public void send(String message) {
System.out.println("이메일 전송: " + message);
}
}
// SMS 서비스 클래스
class SMSService implements NotificationService {
public void send(String message) {
System.out.println("SMS 전송: " + message);
}
}
// 알림 클래스
class Notification {
private NotificationService service;
public Notification(NotificationService service) {
this.service = service;
}
public void sendNotification(String message) {
service.send(message);
}
}
위 내용은 DIP(Dependency Inversion Principle)가 적용된 예시로, 상위 모듈인 Notification 인터페이스 또는 추상클래스가 구체적인 EmailService와 SMSService 구현체에 의존하지 않고, NotificationService라는 추상화된 인터페이스를 통해 상호작용하도록 설계되었습니다. 이를 통해 시스템이 유연하게 확장 가능하며, 각 서비스 구현체의 변경이 상위 모듈에 영향을 미치지 않게 됩니다.
DIP 를 공부했을 때는 추상화 계층을 참조하기 떄문에 구현클래스 확장이 가능한건 이해가 되었는데 추상 레이어가 깨질경우에는 답이 없는건가? 라는 생각도 해보았다.
ISP 는 Interface Segregation Principle (인터페이스 분리 원칙) 준말로 아래와 같은 원칙을 가지고 있습니다.
클라이언트가 자신이 이용하지 않는 메서드에 의존하면 안된다.
클라이언트가 목적과 용도에 맞게 인터페이스를 제공하여 사용하지 않는 메소드를 제거해야 한다는 것입니다. 즉 사용하지 않는 메소드는 상속 받지도 말고 구현 하지도 말아라 입니다.
이는 인터페이스를 더 작고 특화된 단위로 분리함으로써 클라이언트의 의존성을 최소화하고 유연성을 높이는 것을 목표로 합니다.
하나의 큰 인터페이스 대신 여러 개의 작은 인터페이스로 나누어 각 클라이언트가 필요한 기능 만을 구현할 수 있도록 하는 것입니다. 이렇게 함으로써 시스템의 결합도를 낮추고 유지보수성을 향상시킬 수 있습니다.
차의 옵션 기능 예를 들어 설명해보겠습니다. 아래 사진은 K5 의 패키지 옵션입니다.
차량의 등급은 별로 기본으로 제공되는 패키지 옵션이 다릅니다. 다만 위 옵션은 너무 많으니 아래와 같이 추서 정리하겠습니다.
프레티지
노블레스
시그니처
LED 헤드렘프
O
O
O
컴포트
O
O
O
빌트인캠
X
O
O
클러스터 팩
X
O
O
프리미엄사운드
X
X
O
이제 위의 예시를 바탕으로 ISP 원칙을 위반하는 코드와 이를 개선한 코드를 살펴보겠습니다. 먼저, ISP 원칙을 위반하는 코드는 다음과 같습니다:
public interface SmartCar {
// LED 헤드램프
void LEDHeadLamp();
// 컴포트
void comfort();
// 빌트인캠
void builtInCam();
// 클러스터팩
void clusterPack();
// 프리미엄 사운드
void premiumSound();
}
public class PretagePack implements SmartCar {
@Override
public void LEDHeadLamp() { System.out.println("LED헤드렘프 옵션 적용(0)"); }
@Override
public void comfort() { System.out.println("컴포트 옵션 적용(0)"); }
@Override
public void builtInCam() { System.out.println("빌트인탬을 적용할수가 없습니다.(X)"); }
@Override
public void clusterPack() {System.out.println("클러스터팩을 적용할수가 없습니다.(X)");}
@Override
public void driveWise() {System.out.println("드라이브와이즈를 적용할수가 없습니다.(X)");}
@Override
public void premiumSound() {System.out.println("프리미엄사운드를 적용할수가 없습니다.(X)");}
}
public class NoblessePack implements SmartCar{
@Override
public void LEDHeadLamp() { System.out.println("LED헤드렘프 옵션 적용(0)"); }
@Override
public void comfort() { System.out.println("컴포트 옵션 적용(0)"); }
@Override
public void builtInCam() { System.out.println("빌트인탬을 적용(O)"); }
@Override
public void clusterPack() {System.out.println("클러스터팩을 적용(O)");}
@Override
public void driveWise() {System.out.println("드라이브와이즈를 적용할수가 없습니다.(X)");}
@Override
public void premiumSound() {System.out.println("프리미엄사운드를 적용할수가 없습니다.(X)");}
}
public class SignaturePack implements SmartCar {
@Override
public void LEDHeadLamp() { System.out.println("LED헤드렘프 옵션 적용(0)"); }
@Override
public void comfort() { System.out.println("컴포트 옵션 적용(0)"); }
@Override
public void builtInCam() { System.out.println("빌트인탬을 적용(O)"); }
@Override
public void clusterPack() {System.out.println("클러스터팩을 적용(O)");}
@Override
public void driveWise() {System.out.println("드라이브와이즈를 적용할수가 없습니다.(O)");}
@Override
public void premiumSound() {System.out.println("프리미엄사운드를 적용할수가 없습니다.(O)");}
}
위의 코드에서 볼 수 있듯이, 각 패키지 클래스는 SmartCar 인터페이스의 모든 메서드를 구현해야 합니다. 그러나 이는 ISP 원칙을 위반하고 있습니다. 예를 들어, PretagePack 클래스는 실제로 사용하지 않는 builtInCam(), clusterPack() 등의 메서드를 구현해야 하는 상황입니다.
이러한 문제를 해결하기 위해 ISP 원칙을 적용하여 인터페이스를 더 작고 특화된 단위로 분리해 보겠습니다.
위 그림을 참고했을 때 각 기능 별로 인터페이스를 분리하고, 각 패키지 클래스가 필요한 인터페이스만 구현을 했습니다. 이렇게 함으로써 각 클래스는 자신이 실제로 사용하는 기능만을 구현하게 되어 불필요한 의존성을 제거할 수 있습니다. 아래는 ISP 원칙을 적용한 개선된 코드 예시입니다:
public interface LEDHeadLamp { void settingLEDHeadUpLamp(); }
public interface BuiltInCamOption { void builtInCamCharge(); }
public interface ComfortPackage { void settingComfort(); }
public interface ClusterPack { void clusterPackCharge(); }
public interface SoundOptions { void premiumSound(); }
public class PretagePack implements LEDHeadLamp,ComfortPackage {
@Override
public void settingComfort() {System.out.println("컴포트 옵션 적용(0)");}
@Override
public void settingLEDHeadUpLamp() {System.out.println("LEDHeadUpLamp 옵션 석용");}
}
public class NoblessePack implements LEDHeadLamp,ComfortPackage,BuiltInCamOption,ClusterPack {
@Override
public void settingComfort() {System.out.println("컴포트 옵션 적용(0)");}
@Override
public void settingLEDHeadUpLamp() {System.out.println("LEDHeadUpLamp 옵션 석용");}
@Override
public void builtInCamCharge() {System.out.println("builtInCamCharge 옵션 석용");}
@Override
public void clusterPackCharge() {System.out.println("clusterPackCharge 옵션 석용");}
}
public class SignaturePack implements LEDHeadLamp,ComfortPackage,BuiltInCamOption,ClusterPack,SoundOptions{
@Override
public void settingComfort() {System.out.println("컴포트 옵션 적용(0)");}
@Override
public void settingLEDHeadUpLamp() {System.out.println("LEDHeadUpLamp 옵션 석용");}
@Override
public void builtInCamCharge() {System.out.println("builtInCamCharge 옵션 석용");}
@Override
public void clusterPackCharge() {System.out.println("clusterPackCharge 옵션 석용");}
@Override
public void premiumSound() {System.out.println("premiumSound 옵션 석용");}
}
인터페이스를 분리함으로써, 각 패키지 클래스는 자신이 실제로 제공하는 기능만을 구현하게 됩니다. 이는 ISP 원칙을 준수하며, 코드의 유연성과 재사용성을 높이고 유지보수를 용이하게 합니다. 또한, 새로운 패키지나 기능을 추가할 때도 기존 코드의 변경 없이 쉽게 확장할 수 있게 됩니다.
이러한 ISP 원칙의 적용은 단순히 코드 구조를 개선하는 것을 넘어서, 시스템의 전반적인 설계 철학에도 영향을 미칩니다. 인터페이스를 더 작고 특화된 단위로 분리함으로써, 각 컴포넌트의 책임이 명확해지고 시스템의 모듈성이 향상됩니다. 이는 결과적으로 코드의 가독성을 높이고, 테스트와 디버깅을 용이하게 만들어 개발 프로세스 전반의 효율성을 증대시킵니다.
리스코프 치환 원칙(LSP)은 SOLID 원칙중에서 가장 이해하기가 어려웠습니다. 우선 리스코프라는 이름을 가진 분이 연구를 했다고 하는데 컴퓨터 과학 분야에 유명한 분인 것 같습니다. 튜링상을 받았다고 하니 대단하신 분이죠.
바바라 리스코프
LSP 를 한 줄로 정리해서 말하면
서브 타입은 언제나 기반 타입으로 교체를 할 수 있어야 한다.
내용이 너무 어려워서 이걸 풀어서 쉽게 설명 드리면 부모 클래스의 인스턴스를 사용하는 위치에 자식 클래스의 인스턴스를 사용 했을 때 코드가 원래의 의도대로 동작을 해야 한다는 의미입니다. 추상층에서 정의된 부모가 제공해준 메소드들을 재 정의를 하지 말고 사용을 하라는 의미 입니다.(부모가 준 정보를 훼손하지 말고 사용하라는 뜻 같습니다)
다형성의 원리도 클래스를 상속 및 합성하여 타입을 통합하고 업 캐스팅을 해도 메소드 동작에 문제 없이 설계를 잘 해야한다는걸 OOP 공부를 해보셨다면 다들 잘 아실겁니다.
예를 들어서 위 그림과 추상층에서 생물의 특성을 '숨을 쉰다'와 '다리를 움직인다' 두 가지로 정의했을 때, 사람, 고릴라, 고래, 앵무새가 이 추상화된 특성에 부합하는지를 표로 나타낸 것이다.
생물
숨을 쉰다, 두 다리로 걷는다
사람
O
고릴라
O
고래
X
앵무새
X
이 표에서 볼 수 있듯이, '숨을 쉰다'는 모든 생물에 적용되지만 '다리를 움직인다'는 일부 생물에게는 적용되지 않는다. 사실 생물 모두 다리가 달려있지는 않는다. 이는 추상층의 정의가 너무 구체적일 경우 발생할 수 있는 문제점을 잘 보여준다. 따라서 리스코프 치환 원칙을 적용하기 위해서는 추상층의 정의를 더 일반화하거나, 구체적인 특성은 하위 클래스에서 정의하는 것이 바람직하다는 원칙을 가지고 있습니다. 아래 표로 다시 분류를 해보겠습니다.
생물 -> 숨을 쉰다
이족보행 -> 두 다리로 걷는다
사람
O
O
고릴라
O
O
고래
O
X
앵무새
O
X
표로 분리를 해놓은 것처럼 별도로 다리로 걷는다를 추상화 계층을 만들어서 최소한의 특징을 가지고 있을떄 사용되지않는 내용을 제거할수가 있습니다.여기서는고래와 앵무새가 이족 보행에 대한 특징이 없으니 별도로 구현이 하지 않습니다.
다른 예시를 가정해 보겠습니다. 파일을 생성하는 기능이 있고 Excel 과 PDF, 한글 파일을 생성하는 기능이 구현이 되어있고 생성된 문서 파일에 AI 요약 글 생성 기능 추가 요청이 온 상황이라고 가정을 해봅시다.
요구사항에 맞게 UML 을 요구사항 처럼 설계를 했습니다. 이렇게 설계를 하고 구현을 하다 보니 한글 파일에서는 AI 기능이 동작이 안된다는 걸 알고 예외 처리를 진행했습니다. (어디까지 예시를 가정 한것입니다. 한글에서도 AI 기능이 지원 될 수 있습니다.)
public abstract class FileGenerator {
// AI 요약
abstract void summaryAI(String token);
// 파일 생성
abstract void generatorFile();
}
public class ExcelFileGenerator extends FileGenerator {
@Override
public void summaryAI(String token) {
System.out.println(token+"토큰 인증 시도");
System.out.println("AI 요약 생성중 입니다.");
}
@Override
public void generatorFile() {
System.out.println("Excel 파일 생성 중입니다.");
}
}
public class PdfFileGenerator extends FileGenerator {
@Override
public void summaryAI(String token) {
System.out.println(token+"토큰 인증 시도");
System.out.println("AI 요약 생성중 입니다.");
}
@Override
public void generatorFile() {
System.out.println("Excel 파일 생성 중입니다.");
}
}
public class HangulFileGenerator extends FileGenerator {
@Override
public void summaryAI(String token) {
throw new Exception("한글파일은 AI 요약기능을 사용할수 없습니다.");
}
@Override
public void generatorFile() {
System.out.println("Excel 파일 생성 중입니다.");
}
}
한글 파일은 AI 요약이 지원 되지 않는 상황이다. 그렇다면 위에서 언급했던 부모 클래스의 인스턴스를 사용하는 위치에 자식 클래스의 인스턴스를 사용 했을 때 동작이 문제 없이 될까 ? 라는 생각을 했을 때 한글 파일은 동작이 제대로 안 될 거고 이는 당연히 LSP 를 위반한다고 볼 수 있다. 클래스가 자신이 사용하지 않는 기능을 구현하려고 하여 위반된 예제인 것이다.
그렇다면 이럴 경우는 어떻게 해야 할까 ? 대안은 여러가지가 있지만 필자는 어떠한 클래스가 다른 클래스에 종속이 될 떄는 최소한의 인터페이스만 사용하도록 권장하는 것이다. 즉 최소 단위로 인터페이스를 만들어 사용되는 곳에만 구현을 진행을 해야 합니다.
개선한 UML 을 아래와 같이 그려보았습니다.
그리고 설계된 UML 을 보고 아래와 같이 구현하였습니다.
public interface AIAssistant {
//AI 요약
void summeryAI(String token);
}
public abstract class FileGenerator {
// 파일 생성
abstract void generatorFile();
}
public class ExcelFileGenerator extends FileGenerator implements AIAssistant {
@Override
public void generatorFile() {
System.out.println("Excel 파일 생성 중입니다.");
}
@Override
public void summeryAI(String token) {
System.out.println(token+"토큰 인증 시도");
System.out.println("AI 요약 생성중 입니다.");
}
}
public class PdfFileGenerator extends FileGenerator implements AIAssistant {
@Override
public void generatorFile() {
System.out.println("Excel 파일 생성 중입니다.");
}
@Override
public void summeryAI(String token) {
System.out.println(token+"토큰 인증 시도");
System.out.println("AI 요약 생성중 입니다.");
}
}
public class HangulFileGenerator extends FileGenerator {
@Override
public void generatorFile() {
System.out.println("Excel 파일 생성 중입니다.");
}
}
Client 클래스는 아래와 같이 구현을 하였습니다.
public class Client {
private FileGenerator fileGenerator;
public Client(FileGenerator fileGenerator) {
this.fileGenerator = fileGenerator;
}
void generatorFile() {
fileGenerator.generatorFile();
}
void useAISummary(String token) {
if (fileGenerator instanceof AIAssistant) {
((AIAssistant) fileGenerator).summeryAI(token);
} else {
System.out.println("AI 기능을 지원하지 않는 파일 생성기입니다.");
}
}
public static void main(String[] args) throws Exception {
Client excelClient = new Client(new ExcelFileGenerator());
excelClient.generatorFile(); // Excel 파일 생성중 입니다.
excelClient.useAISummary("AI_EXCEL"); //AI 요약 생성중 입니다."
Client pdfClient = new Client(new PdfFileGenerator());
pdfClient.generatorFile(); // PDF 파일 생성중 입니다.
excelClient.useAISummary("AI_EXCEL"); // AI 요약 생성중 입니다.
Client hangulClient = new Client(new HangulFileGenerator());
hangulClient.generatorFile(); // 한글 파일을 생성중 입니다.
hangulClient.useAISummary("AI_HANGUL"); //AI 기능을 지원하지 않는 파일 생성기입니다.
}
}
main 함수에 각 클라이언트가 사용할 FileGenerator 구현 클래스를 주입했을 때 이 클래스가 AI 요약 기능을 사용하는지를 확인하기 위해서 useAISummary 메소드 안에 instanceof 로 AIAssistant 사용 유무를 분기처리 하였습니다.
LSP 에서 말하고자 하는건 최소한의 추상층을 구성하여 필요한 내용을 구현하는것 같습니다. 사실 부모 타입으로 의도된 동작을 해야하는거고 이 부분이 충족 되면 OCP 에서 말했던것 처럼 변경에는 닫혀있고 확장에는 열려있는 구조가 성럽이 되는것 같습니다.
