이전 20922번과는 달리 k라는 일정한 간격이 정해져 있어서, 상대적으로 투포인터의 느낌이 옅은 것 같은 문제였다. 입력값 저장은 일차원 배열에 하지만 회전 초밥은 시작과 끝이 연결되어 있으므로 left (시작 지점)이 n-1번째까지 오도록 반복하고, right는 n과 같아질 경우 다시 0번째 인덱스로 돌려줬다. 나는 코드에서 d값을 쓰지는 않았다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 초기값 저장
int n = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int[] arr = new int[n];
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++)
arr[i] = Integer.parseInt(br.readLine());
// 처음 k개 초밥 계산
int cnt = 0;
for (int i = 0; i < k; i++) {
map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
if (map.get(arr[i]) == 1) cnt++;
}
int answer = cnt;
// 투포인터 적용
int right = k;
for (int left = 0; left < n; left++) {
if(right == n) right = 0;
map.put(arr[left], map.get(arr[left]) - 1);
if(map.get(arr[left]) == 0) cnt--;
map.put(arr[right], map.getOrDefault(arr[right], 0) + 1);
if(map.get(arr[right]) == 1) cnt++;
// 쿠폰 번호 확인
if(map.getOrDefault(c, 0) == 0) answer = Math.max(answer, cnt+1);
else answer = Math.max(answer, cnt);
// 포인터 이동
right++;
}
System.out.println(answer);
}
}
C언어나 C++을 써본 사람이라면 투포인터를 이해하기가 더 쉬울 것이라고 생각한다. 포인터는 말 그대로 어떤 배열을 '가리키는' 화살표를 사용하는 것이다. 그런데 자바에는 포인터가 없으므로, 배열의 특정 위치를 가리키는 값, 즉 인덱스로 보면 된다. (자바에 포인터가 없는 이유도 나중에 정리해보면 좋을 것 같다.)
이 문제에서는 조건을 만족하는 가장 긴 수열의 길이를 찾는 것이 목적이기 때문에, 해당 수열을 찾기 위해 수열의 양 옆을 가리키는 left와 right라는 두 포인터(인덱스값)를 이용하게 된다. 포인터를 한칸씩 이동하며 left ~ right에 해당하는 부분 수열이 문제에서 제시하는 조건에 부합한다면 결과(answer) 값을 갱신하면 된다. 각 숫자의 개수를 카운팅하는 방법은 여러 방법이 있을 것이다. 20만 크기의 배열을 선언하여 바로바로 참조하는 방법도 있겠지만, 나는 굳이 빈 공간을 두기 싫어서 숫자 N을 키로 갖는 Map을 사용했다.
첫 번째 예제에서는 k값이 2이기 때문에, 어떤 숫자의 개수가 2가 되기 전까지는 계속해서 right를 증가시켜 준다. 그래야 left~right 수열의 길이가 최대가 되기 때문이다. 그렇게 한 칸씩 이동하다가 (3, 2, 5, 5, 6, 4, 4, 5) 에서 조건에 위배되는 경우를 마주치게 되었다. 그러면 앞에 나온 동일한 숫자 5가 없을 때까지 left를 이동시켜줘야 하므로, 앞부분의 (3, 2, 5) 를 제외하고(카운팅한 개수에서도 하나씩 없앰) left는 4번째 자리의 5를 가리키게 된다. 이제 K값보다 큰 개수의 숫자가 없기 때문에 다시 조건에 맞는 가장 긴 순열을 찾기 위해 right를 증가시키는 과정을 입력 순열의 마지막 인덱스가 될 때까지 반복하면 된다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int answer = 1; // k의 최솟값은 1임
// 기본 입력값 받기
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
// 입력 수열 저장
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++)
arr[i] = Integer.parseInt(st.nextToken());
// 투 포인터 적용
Map<Integer, Integer> m = new HashMap();
int left = 0, right = 0; // left~right의 연속된 수열을 위한 인덱스
while(right < n) { // 입력수열의 마지막까지 확인
m.put(arr[right], m.getOrDefault(arr[right], 0) + 1);
while (m.get(arr[right]) > k) {
m.put(arr[left], m.get(arr[left]) - 1);
left++;
}
answer = Math.max(answer, right - left + 1);
right++;
}
System.out.println(answer);
}
}
오늘 오후 2~5시에 진행됐던 쇼미더코드가 끝났다. 결론은 세 문제 다 풀긴 풀었다! 와아아 👏 A는 부분합 문제, B는 BFS 문제, C는 dp 문제였다. 공개된 문제를 보니 난이도는 골드5, 5, 3이었다. 직접 풀어보고 싶으신 분들은 이쪽 → https://www.acmicpc.net/category/detail/3451
사실 A번부터 풀기 시작했는데 처음에 잘 안풀리길래 그냥 관둘까 하다가 B번이 너무 쉬워보여서 조금만 더 해보자 했다. 다행히 B번은 1트만에 풀었는데 그게 이미 대회가 시작된지 1시간 30분이 지난 뒤여서 좀 아쉬웠다. C번은 처음에 문제를 이해하는 데 시간이 좀 걸렸고, 전체 틀을 금방 잡았는데 사소하게 놓친 부분들이 있어 이것저것 고치다보니 제출횟수가 좀 많아졌다. C번까지 풀고 나니 20분정도가 남았고, A번을 다시 보는데 갑자기 그제서야 방법이 확 생각나서.. 후다닥 풀고 종료 5분 전에 다 제출했다. 아래 코드는 급하게 푼 만큼, 가독성이나 효율성이 안좋을 수 있는 점 참고 바란다.
+
1월 30일에 테스트 결과가 이메일로 발송됐다. 제출 횟수나 시간 등을 봤을 때 금손은 절대 아닐거라 생각하고 있었고, 예상대로 은손을 받았다.
A번: 신을 모시는 사당
입력된 1의 개수, 2의 개수를 카운팅해서 배열에 넣도록 했다. 1은 음수, 2는 양수로 해서 가장 큰/작은 연속된 수열의 합을 구하는 로직을 적용했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ArrayList<Integer> arr = new ArrayList<>();
int sum = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
int val = Integer.parseInt(st.nextToken());
if(val == 1){
if(sum < 0) sum--;
else{
arr.add(sum);
sum = -1;
}
}
else{
if(sum > 0) sum++;
else{
arr.add(sum);
sum = 1;
}
}
}
arr.add(sum);
int arrSize = arr.size();
int largeSum = 0, smallSum = 0;
int largest = 0, smallest = 0;
for (int i = 0; i < arrSize; i++) {
for (int j = i; j < arrSize; j++) {
largeSum += arr.get(j);
smallSum += arr.get(j);
largest = Math.max(largest, largeSum);
smallest = Math.min(smallest, smallSum);
}
largeSum = smallSum = 0;
}
int answer = Math.max(largest, -smallest);
System.out.println(answer);
}
}
B번: 도넛 행성
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static class Pos{
int x, y;
Pos(int x, int y){
this.x = x;
this.y = y;
}
}
static int N, M;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[][] star = new int[N][M];
boolean[][] visited = new boolean[N][M];
for(int i = 0;i < N;i++){
st = new StringTokenizer(br.readLine());
for(int j = 0;j < M;j++){
star[i][j] = Integer.parseInt(st.nextToken());
if(star[i][j] == 1) visited[i][j] = true;
}
}
int answer = 0;
for(int i = 0;i < N;i++) {
for (int j = 0; j < M; j++) {
if(visited[i][j]) continue;
bfs(i, j, visited);
answer++;
}
}
System.out.println(answer);
}
private static void bfs(int i, int j, boolean[][] visited) {
Queue<Pos> q = new LinkedList();
q.add(new Pos(i, j));
while(!q.isEmpty()){
Pos cur = q.poll();
if(visited[cur.x][cur.y]) continue;
visited[cur.x][cur.y] = true;
for(int d = 0;d < 4;d++){
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
// set bound
if(nx >= N) nx -= N;
else if(nx < 0) nx += N;
if(ny >= M) ny -= M;
else if(ny < 0) ny += M;
if(!visited[nx][ny])
q.add(new Pos(nx, ny));
}
}
}
}
C번: 미팅
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
int[][] W = new int[C+1][C+1];
int[] aChar = new int[N];
int[] bChar = new int[M];
// 성격 간의 만족도 저장
for (int i = 1; i <= C; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= C; j++) {
W[i][j] = Integer.parseInt(st.nextToken());
}
}
// A와 B 학생들의 성격 저장
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
aChar[i] = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++)
bChar[i] = Integer.parseInt(st.nextToken());
// dp 초기값 설정
long[][] dp = new long[N][M];
long answer = 0;
dp[0][0] = W[aChar[0]][bChar[0]];
for (int i = 1; i < N; i++)
dp[i][0] = Math.max(dp[i-1][0], W[aChar[i]][bChar[0]]);
for (int i = 1; i < M; i++)
dp[0][i] = Math.max(dp[0][i-1], W[aChar[0]][bChar[i]]);
// 최대 만족도 계산
for (int i = 1; i < N; i++) {
for (int j = 1; j < M; j++) {
// 악수를 하는 경우와 안하는 경우 고려
long val = Math.max(dp[i-1][j], dp[i][j-1]);
dp[i][j] = Math.max(val, dp[i-1][j-1] + W[aChar[i]][bChar[j]]);
}
}
System.out.println(dp[N-1][M-1]);
}
}
사용자가 편집하기를 원하는 모든 데이터를 가지고 있어야 함 - 화면 안에 글자가 표현된다면 박스의 위치, 크기, 글자 포맷 정보 등을 가지고 있어야 함
뷰나 컨트롤러에 대해서 어떤 정보도 알지 말아야 함 - 데이터 변경이 일어났을 때 모델에서 직접 UI를 수정할 수 있도록 뷰를 참조하는 내부 속성값을 가지면 안됨
변경이 일어나면, 변경 통지에 대한 처리방법을 구현해야만 함 - 모델의 정보가 변경된다면 이벤트를 발생시켜 누군가에게 전달해야 함 - 누군가가 모델을 변경하도록 요청하는 이벤트를 보냈을 때 이를 수신할 수 있는 처리 방법을 구현해야 함 - 모델은 재사용가능해야 하며 다른 인터페이스에서도 변하지 않아야 함
뷰
화면에 무엇인가를 보여주기 위한 역할
사용자에게 보여주는 화면(UI)에 해당하며, 텍스트, 체크박스 항목과 같은 사용자 인터페이스 요소를 나타냄
지연 초기화를 위한 코드 작성이 필요하는데, 이를 모든 클래스마다 직접 넣을 경우 엄청 많은 코드 중복이 발생함
2. 프록시 객체를 사용하는 경우
프록시 객체가 요청을 먼저 받은 뒤 흐름을 제어하여 DB에 쿼리를 날릴 수 있음
서비스를 유연하게 제공 가능
장점
참조를 통한 메모리 공간 확보
해당 객체가 메모리에 존재하지 않아도 기본적인 정보를 참조하거나 설정할 수 있음
사이즈가 큰 객체가 로딩되기 전에도 프록시를 통해서 참조할 수 있음
객체의 기능이 필요한 시점까지 객체의 생성을 미룰 수 있음
클라이언트들의 활성 상태 여부를 확인하여, 비어있을 경우 해당 서비스 객체를 닫고 그에 해당하는 시스템 자원을 확보할 수 있음
흐름 제어
클라이언트의 모든 요청을 받음 → 서비스를 유연하게 제공
실제 메소드가 호출되기 이전에 전처리 등을 구현 객체의 변경 없이 추가할 수 있음
캐시 사용 가능
프록시가 내부 캐시를 통해 데이터가 캐시에 존재하지 않는 경우에만 주체 클래스에서 작업이 실행되도록 할 수 있음
인터페이스를 두기 때문에 개발 코드에서 구현체에 영향을 받지 않아 코드 변경이 최소화됨
실제 객체의 메소드를 숨기고 인터페이스를 통해 노출시킬 수 있어 방패(보안) 역할
사용자 입장에서는 프록시 객체나 실제 객체나 사용법은 유사하므로 사용성이 좋음
활용
기존의 작업 수행하며 부가적인 작업(초기화 지연, 로깅, 액세스 제어, 캐싱 등)을 수행하기 좋음
비용이 많이 드는 연산(DB 쿼리, 대용량 텍스트 파일 등)을 실제로 필요한 시점에 수행할 수 있음
페이지를 로드할 때 이미지는 텍스트보다 용량이 커서 로딩 시간이 오래 걸릴 수 있기 때문에, 프록시의 흐름 제어를 통해 현재까지 완료된 내용들을 우선적으로 보여주도록 함
단점
객체를 생성할 때 한 단계를 거치게 되므로 빈번한 객체 생성은 성능을 저하시킬 수 있음
객체 생성을 위해 스레드가 생성, 동기화가 구현되어야 하는 경우 성능을 저하시킬 수 있음
로직이 난해해져 가독성이 떨어짐
프록시 패턴의 종류
가상 프록시와 보호 프록시의 사용 예시는 아래 예제 코드의 시나리오를 참고하면 도움이 됩니다. 해당 예제는 이 블로그를 참고했습니다.
가상 프록시(Virtual Proxy)
생성하기 힘든 자원에 대한 접근을 제어
꼭 필요로 하는 시점까지 객체의 생성을 연기하고, 해당 객체가 생성된 것처럼 동작하도록 만들고 싶을 때 사용
프록시 클래스에서 작은 단위의 작업을 처리하고 리소스가 많이 요구되는 작업들이 필요할 경우만 주체 클래스를 사용하도록 구현
무거운 서비스 객체가 항상 가동되며 시스템 자원을 낭비하는 초기화 지연 경우에 사용
보호 프록시(Protection Proxy)
접근 권한이 필요한 자원에 대한 접근을 제어
특정 클라이언트에게만 서비스 객체를 사용할 수 있도록 하는 경우에 사용
프록시 클래스에서 클라이언트가 주체 클래스에 대한 접근을 허용할지 말지 결정하도록 함
예를 들어 운영 체제의 중요한 부분에 악의적인 응용 프로그램들이 접근하지 못하도록 할 수 있음
원격 프록시(Remote Proxy)
원격 객체에 대한 접근을 제어
서비스 객체가 원격 서버에 존재하는 경우, 네트워크를 통해 클라이언트의 요청을 전달하여, 네트워크와의 작업의 모든 복잡한 세부 사항을 처리함
서로 다른 주소 공간에 있는 객체에 대해 마치 같은 주소 공간에 있는 것처럼 동작하게 하는 패턴
Ex: Google Docs
기타
로깅 프록시(요청들의 로깅)
서비스 객체에 대한 요청들의 기록을 유지하고 싶은 경우
프록시는 각 요청을 서비스에 전달하기 전에 로깅할 수 있음
캐싱 프록시(요청 결과들의 캐싱)
요청 결과들을 캐싱하고, 이 캐시들의 수명 주기를 관리할 때(특히 결과들이 상당히 큰 경우)에 사용
항상 같은 결과를 생성하는 반복 요청들에 대해 캐싱을 구현
요청들의 매개변수들을 캐시 키로 사용할 수 있음
예제 코드
일반
public interface Subject {
void request();
}
public class RealSubject implements Subject {
@Override
public void request() {
System.out.println("Hello World!");
}
}
public class Proxy implements Subject {
private Subject subject;
@Override
public void request() {
// 객체의 초기화를 지연시켜 실제로 사용될 때 생성함으로써 메모리 절약 가능
if (this.subject == null) {
this.subject = new RealSubject();
}
subject.request(); // 프록시가 RealSubject()의 메소드를 호출
}
}
public class Main {
public static void main(String[] args) {
// RealSubject 클래스의 메소드를 호출하는것이 아닌 Proxy 클래스의 메소드를 호출
Subject subject = new Proxy();
subject.request(); // 내부적으로 RealSubject의 메소드를 호출
}
}
가상 프록시
콘솔 프로그램으로 20개씩 난독화된 전자 서류의 본문을 복호화해서 보여주는 프로그램 작성한다고 해보자. 아래처럼 텍스트 파일을 읽는 인터페이스가 있다. 메서드가 하나밖에 없는 아주 간단한 인터페이스로, 앞으로 이 인터페이스를 구현하는 클래스는 반드시 fetch() 메서드를 구현해야 한다.
interface TextFile {
String fetch();
}
실제 업무를 수행하기에 앞서 협업 조직에 SecretTextFile 이라는 클래스를 인수 받았다. 이 클래스는 난독화되어 있는 텍스트 파일을 복호화해서 평문으로 바꿔주는 클래스로, 협업 조직에서 라이브러리로 제공한 클래스라고 가정하자. 즉, 나는 이 클래스를 수정할 권한이 없다.
class SecretTextFile implements TextFile {
private String plainText;
public SecretTextFile(String fileName) {
// 특별한 복호화 기법을 이용해 데이터를 복원해서 내용을 반환
this.plainText = SecretFileHolder.decodeByFileName(fileName);
}
@Override
public String fetch() {
return plainText;
}
}
이 클래스로 콘솔 프로그램을 구성했으나, 실행 후 첫 결과가 나오기까지 6초라는 시간이 걸렸다. 이유를 확인해보니 SecretTextFile 클래스에서 사용 중인 SecretFileHolder.decodeByFileName() 메서드의 수행 속도가 0.3초였던 것이다. 그리고 목록에 20개의 파일 내용을 노출해야 하는 상태였기 때문에 문제가 된 것이다. 화면을 구성할 때 이 파일들을 전부 객체로 만들다 보니 6초 정도의 로딩 시간을 갖게 된 것이다. 이제 프록시 클래스를 구현하자.
class ProxyTextFile implements TextFile {
private String fileName;
private TextFile textFile;
public ProxyTextFile(String fileName) {
this.fileName = fileName;
}
@Override
public String fetch() {
if (textFile == null) {
textFile = new SecretTextFile(fileName);
}
// 프록시 객체를 사용하는 경우를 확인하기 위해 [proxy] 문구를 넣음
return "[proxy] " + textFile.fetch();
}
}
프록시 패턴을 적용해 필요할 때만 파일 복호화를 하도록 수정하기로 했다. ProxyTextFile 클래스는 객체를 생성할 때에는 별다른 동작을 하지 않지만, 실제로 데이터를 가져와야 할 때는 실제 객체인 SecretTextFile 객체를 만들어내고 기능을 위임한다. 이제 프로그램 코드를 수정하자.
다음의 코드는 처음 3개의 파일만 실제 객체를 사용하고 나머지는 프록시 객체를 사용해 프로그램에서 첫 결과가 나오는 것을 1초 내로 만들도록 한다. textFileList를 사용하는 입장에서는 별다른 조치없이 그대로 사용하면 된다. 콘솔에서 textFileList를 순회하면서 노출한다고 하면 처음 세개는 이미 로딩이 되어 있는 상태이므로 바로 노출하고 그다음 아이템부터는 차근차근 노출할 것이다.
따라서 ProxyTextFile 같은 프록시 클래스를 만들고 기존 SecretTextFile 클래스 대신 사용한것만으로도 초기 객체 생성 시간이 대폭 감소했다. 정말 필요한 시점에만 텍스트 복호화를 하게 된 것이다. 이렇게 초기 비용이 많이 드는 연산이 포함된 객체의 경우 가상 프록시를 사용했을 때 효과를 볼 수 있다.
보호 프록시
인사팀에서 인사정보에 대한 데이터 접근을 직책 단위로 세분화 하려고 한다. 기존에는 오로지 인사팀에서만 사용했던 부분이었으나 최근 인사정보를 직책별로 공개해줘야 하는 경우가 생겼다. 따라서 직책에 따라서 조직원의 인사정보 접근을 제어하는 업무를 수행해야 한다. 기존에 인사팀만 사용하던 코드는 아래와 같다.
// 직책 등급(차례대로 조직원, 조직장, 부사장)
enum GRADE {
Staff, Manager, VicePresident
}
// 구성원
interface Employee {
String getName(); // 구성원의 이름
GRADE getGrade(); // 구성원의 직책
String getInformation(Employee viewer); // 구성원의 인사정보(매개변수는 조회자)
}
// 일반 구성원
class NormalEmployee implements Employee {
private String name;
private GRADE grade;
public NormalEmployee(String name, GRADE grade) {
this.name = name;
this.grade = grade;
}
@Override
public String getName() {
return name;
}
@Override
public GRADE getGrade() {
return grade;
}
// 기본적으로 자신의 인사정보는 누구나 열람할 수 있도록 되어있습니다.
@Override
public String getInformation(Employee viewer) {
return "Display " + getGrade().name() + " '" + getName() + "' personnel information.";
}
}
NormalEmployee 클래스는 단순히 Employee 인터페이스를 구현하기만 한 것으로, getInformation() 메서드는 조직원이 누구든 자신의 인사정보를 열람할 수 있도록 작성이 되어있다. 지금 이 상태로만 놔둔다면 누구든지 Employee 객체에서 getInformation() 메서드를 호출하면 누가 조회하든 정보를 보여줄 것이다. 이제부터 보호 프록시 클래스를 구성해보자. 이 클래스는 조회자의 직책을 확인하고 예외를 던지거나 인사 정보를 노출할 수 있도록 실제 객체에게 위임한다. 보호 프록시에서 메서드 호출시 조회자에게 권한이 없으면 NotAuthorizedException 예외를 던지도록 한다.
// 인사정보가 보호된 구성원(인사 정보 열람 권한 없으면 예외 발생)
class ProtectedEmployee implements Employee {
private Employee employee;
public ProtectedEmployee(Employee employee) {
this.employee = employee;
}
@Override
public String getInformation(Employee viewer) {
// 본인 인사정보 조회
if (this.employee.getGrade() == viewer.getGrade() && this.employee.getName().equals(viewer.getName())) {
return this.employee.getInformation(viewer);
}
switch (viewer.getGrade()) {
case VicePresident:
// 부사장은 조직장, 조직원들을 볼 수 있다.
if (this.employee.getGrade() == GRADE.Manager || this.employee.getGrade() == GRADE.Staff) {
return this.employee.getInformation(viewer);
}
case Manager:
if (this.employee.getGrade() == GRADE.Staff) { // 조직장은 조직원들을 볼 수 있다.
return this.employee.getInformation(viewer);
}
case Staff:
default:
throw new NotAuthorizedException(); // 조직원들은 다른 사람의 인사정보를 볼 수 없다.
}
}
@Override
public String getName() {
return employee.getName();
}
@Override
public GRADE getGrade() {
return employee.getGrade();
}
}
class NotAuthorizedException extends RuntimeException {
private static final long serialVersionUID = -1714144282967712658L;
}
우선 예제를 보고 문제에서 구하고자 하는 바이토닉 수열은 연속되지 않아도 된다는 점을 알았다. 바이토닉 수열은 계속해서 증가하다가 어느 시점을 기점으로 계속해서 감소하는 수열인데, 그러면 배열 하나로 구하기보다는 증가하는 수열의 길이를 담는 배열과 감소하는 수열의 길이를 담는 배열 2개를 계산해서 그 합을 비교하면 될 것 같다. 감소하는 수열은 결국 증가하는 수열을 반대 방향에서 계산한 것과 동일하므로, 부호만 수정해주면 된다. 즉 11053번의 응용 문제이다.
그치만 여기까지 생각해놓고 LIS 알고리즘이 생각 안나는 나는,,, 처음에는 스택 두개로 어떻게 해보려고 삽질하다가 이게 맞나 싶어서 결국 솔루션을 찾아봤다. 해보지는 않았는데 스택 방법도 논리적으로는 문제가 없다고 생각한다.. 아마도? 간략하게만 적어보면 스택 2개를 두고, 하나에는 (현재) 가장 긴 증가하는 수열을 저장 / 나머지 하나는 (앞으로) 가장 길 수도 있는 수열을 저장하는 것이었다. 그래서 만약 {7, 8, 9, 1, 2, 3, 4, 5} 가 있다면 뒤쪽의 5숫자가 가장 길기 때문에, 작은 수가 나온다면 임시 후보로 스택에 저장해두다가 그 길이가 더 길어지면 스위치하는 방식을 생각해봤다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int answer = 0;
int[] arr = new int[n];
int[] increase = new int[n];
int[] decrease = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0;i < n;i++)
arr[i] = Integer.parseInt(st.nextToken());
// 최장 증가 수열(LIS) 구하기
for(int i = 0;i < n;i++){
increase[i] = 1;
for(int j = 0;j < i;j++){
if(arr[i] > arr[j])
increase[i] = Math.max(increase[i], increase[j] + 1);
}
}
// 최장 감소 수열(LDS) 구하기
for(int i = n-1;i >= 0;i--){
decrease[i] = 1;
for(int j = n-1;j >= i;j--){
if(arr[i] > arr[j])
decrease[i] = Math.max(decrease[i], decrease[j]+1);
}
}
for(int i = 0;i < n;i++)
answer = Math.max(answer, increase[i] + decrease[i]);
System.out.println(answer - 1); // 가운데 중복되는 숫자 제외
}
}
