[백준] 1253번: 좋다 (골드4, JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/1253

 

[백준] 1253번: 좋다 (골드4, JAVA)

우선 아래의 코드를 사용하여 사용자로부터 입력을 받고 배열로 변환 합니다. 단, 문제를 풀 때 수월하게 풀기 위해서 따로 원본 배열과 사본 배열을 생성하고 사본 배열을 오름차순 정렬하였습니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();

int N = Integer.parseInt(br.readLine());

String input = br.readLine();
sb.append(input);

// 스트링 배열로 변환
String[] strArr = sb.toString().split(" ");

// 원본 배열 생성
int[] originA = new int[strArr.length];

// 사본 배열 생성
int[] A = new int[strArr.length];

// 스트링 배열 -> int 배열 변환
for(int i=0; i<A.length; i++) {
    originA[i] = Integer.parseInt(strArr[i]);
    A[i] = Integer.parseInt(strArr[i]);
}

// 사본 배열 오름차순 정렬
Arrays.sort(A);

 

우선 for 안에 while을 사용하여 볼건데, 로직을 작성하기 전의 코드를 보면 아래와 같습니다. 원본 배열은 어떤 수(현재 인덱스)를 가지고 있어야 하고, 투포인터를 사용해야하기 때문에 오름차순으로 정렬한 배열은 시작 인덱스와 끝 인덱스를 만들어 줍니다.

int answer = 0; // 반환 값
for(int i=0; i<A.length; i++) {
    int number = i; // 어떤 수의 인덱스 (원본 배열) 
    int start = 0;  // 시작 인덱스 (사본 배열)
    int end = A.length-1; // 끝 인덱스 (사본 배열)
    int count = 0; // 중복값 카운트
    
    // 로직 작성
}

 

문제를 보면 아래와 같은 조건이 있는데, 즉 같은 값을 가지고 있더라도 위치(인덱스)가 다르면 다른 수라고 합니다. 위 코드의 count 배열은 어떤 수(원본 배열)와 시작 또는 끝 인덱스에 위치한 값(사본 배열)이 일치하는게 있다면 1, 없다면 0으로 사용할 예정입니다.

• 애초에  사본 배열에 있는 값을 가지고 비교할 예정이기 때문에 중복되는 값이 있더라도 인덱스의 위치 상관 없이 단 한번만 무시하면 됩니다.
• ex) 원본 배열 : 0 1 4 5 3 4 의 경우 사본 배열로 만들어 오름차순하게 되면 0 1 3 4 4 5 로 됩니다. 이러한 경우일 때 원본 배열의 어느 인덱스에 있던간에 사본 배열의 3번 또는 4번 인덱스에 위치한 값 한번만 무시하면 됩니다. 

 

위의 코드에서 로직이 한번 더 추가된 코드입니다. 조건식은 다음과 같습니다.

1. 사본 배열의 시작 인덱스 값 = 어떤 수(원본 배열)이 같거나 count가 0이면 true
   → count가 1이라면 이미 중복된 코드를 처리했기 때문에 pass
   → 다음 인덱스의 값을 비교하기 위해 start 값 증가
2. 사본 배열의 끝 인덱스 값 = 어떤 수(원본 배열)이 같거나 count가 0이면 true
   → 다음 인덱스의 값을 비교하기 위해 end 값 감소
3. 그 외의 경우(값이 같지 않고, 중복된 로직이 없었다면) true 

int answer = 0; // 반환 값
for(int i=0; i<A.length; i++) {
    int number = i; // 어떤 수의 인덱스 (원본 배열) 
    int start = 0;  // 시작 인덱스 (사본 배열)
    int end = A.length-1; // 끝 인덱스 (사본 배열)
    int count = 0; // 중복값 카운트
    
    // 추가된 로직
    while(start < end) { // 시작이 종료보다 작을 때
        if(A[start] == originA[number] && count == 0) {
            count++;
            start++;
        } else if(A[end] == originA[number] && count == 0) {
            count++;
            end--;
        } else {
            // 투포인터 로직 작성
            
        }
    }
}

 

 

투포인터 로직까지 작성하면 아래와 같습니다. 사본 배열의 시작 인덱스 + 끝 인덱스가 어떤 수(원본 배열)보다 크다면 끝 인덱스를 줄이고, 반대의 경우라면 시작 인덱스를 줄여가며 비교합니다. 만약 시작 인덱스 + 끝 인덱스의 합이 어떤 수(원본 배열)와 같다면 반환값을 증가하고 이미 좋은 수로 판단이 되었기 때문에 추가적인 검사 없이 break로 while을 탈출합니다.

while문이 종료되며 for문이 다시 반복되고, 원본 배열의 다음 인덱스를 비교해가며 좋은 수를 찾아가게 됩니다.

int answer = 0; // 반환 값
for(int i=0; i<A.length; i++) {
    int number = i; // 어떤 수의 인덱스 (원본 배열) 
    int start = 0;  // 시작 인덱스 (사본 배열)
    int end = A.length-1; // 끝 인덱스 (사본 배열)
    int count = 0; // 중복값 카운트
    
    // 추가된 로직
    while(start < end) { // 시작이 종료보다 작을 때
        if(A[start] == originA[number] && count == 0) {
            count++;
            start++;
        } else if(A[end] == originA[number] && count == 0) {
            count++;
            end--;
        } else {
            // 투포인터 로직 작성
            if(A[start]+A[end] > originA[number]) { // 어떤수가 합보다 작을 때
                end--;
            } else if(A[start]+A[end] < originA[number]) { // 어떤수가 합보다 클 때
                start++;
            } else if(A[start]+A[end] == originA[number]) { // 어떤수가 합과 같을 때
                answer++;
                break;
            }
        }
        System.out.println(answer);
    }
}