[프로그래머스] 수 조작하기1

수 조작하기 1 - 알고리즘 문제 풀이 (Java와 Python 코드)

문제 설명

이 문제에서는 주어진 정수 n과 문자열 control에 따라 n의 값을 변경하는 간단한 알고리즘을 작성하는 문제입니다. control은 "w", "a", "s", "d"로 구성된 문자열로, 각 문자는 다음과 같은 방식으로 n을 변경합니다:

• "w": n이 1 커집니다.
• "s": n이 1 작아집니다.
• "d": n이 10 커집니다.
• "a": n이 10 작아집니다.

문자열 control의 문자를 앞에서부터 하나씩 처리하여, 해당 문자에 맞는 연산을 적용한 후 마지막 n의 값을 반환하는 것이 목표입니다.

제한사항

• -100,000 ≤ n ≤ 100,000
• 1 ≤ control의 길이 ≤ 100,000
• control은 "w", "a", "s", "d"로만 구성된 문자열입니다.

입출력 예시

n	control	result
0	"wsdawsdassw"	-1

입출력 예 설명:

• 초기값 n = 0입니다.
• "wsdawsdassw"의 각 문자를 순서대로 처리하면:
  1. 'w' → 1 증가 → n = 1
  2. 's' → 1 감소 → n = 0
  3. 'd' → 10 증가 → n = 10
  4. 'a' → 10 감소 → n = 0
  5. 'w' → 1 증가 → n = 1
  6. 's' → 1 감소 → n = 0
  7. 'd' → 10 증가 → n = 10
  8. 'a' → 10 감소 → n = 0
  9. 's' → 1 감소 → n = -1
  10. 's' → 1 감소 → n = -2
  11. 'w' → 1 증가 → n = -1

따라서 결과는 -1입니다.

---

해결 방법

문자열을 하나씩 순회하면서 해당 문자에 따라 n의 값을 업데이트하는 방식으로 문제를 해결할 수 있습니다. 각 문자는 고정된 값을 n에 더하거나 빼기 때문에, 이 문제는 매우 간단한 시뮬레이션 문제로 볼 수 있습니다.

Java 코드

class Solution {
    static int solution(int n, String control){
        for(char chr: control.toCharArray()){
            switch(chr){
                case 'w':
                    n++;
                    break;
                case 's':
                    n--;
                    break;
                case 'd':
                    n += 10;
                    break;
                case 'a':
                    n -= 10;
                    break;
                default:
            }
        }
        return n;
    }

    public static void main(String[] args) {
        System.out.println(solution(0, "wsdawsdassw"));  // 출력: -1
    }
}

Python 코드

def solution(n, control):
    for chr in control:
        if chr == 'w':
            n += 1
        elif chr == 's':
            n -= 1
        elif chr == 'd':
            n += 10
        elif chr == 'a':
            n -= 10
    return n

---

시간 복잡도 및 공간 복잡도 분석

시간 복잡도 (Time Complexity)

control 문자열을 순차적으로 탐색하면서 각 문자를 처리하는 방식입니다. 문자열의 길이를 m이라고 하면, 각 문자에 대해 상수 시간(O(1)) 연산을 수행합니다.

• 문자열 탐색: for 루프에서 control의 각 문자를 순회합니다. 이 작업은 O(m)의 시간이 걸립니다.
• 연산 처리: 각 문자에 대해 상수 시간의 연산(n을 더하거나 빼는 작업)을 수행합니다. 따라서, 이 부분 역시 O(1)입니다.

따라서 전체 시간 복잡도는 O(m)이 됩니다. 여기서 m은 control 문자열의 길이입니다.

공간 복잡도 (Space Complexity)

공간 복잡도는 추가적으로 사용하는 메모리를 의미합니다.

• 입력 공간: 입력으로 주어지는 문자열 control 자체는 이미 주어진 공간이므로, 이는 추가 공간에 포함되지 않습니다.
• 추가 메모리: Java에서는 control.toCharArray()로 문자 배열을 생성하지만, Python에서는 직접 문자열을 순회하므로 추가적인 배열을 생성하지 않습니다.
• 상수 공간 사용: 문제 해결을 위한 추가 변수는 n과 몇 개의 임시 변수들 뿐이므로, 공간 복잡도는 O(1) (상수 공간)입니다.

따라서 전체 공간 복잡도는 O(1)로 상수 공간을 사용합니다.

---

최종 정리

이 문제는 간단한 문자열 탐색과 시뮬레이션 문제로, 각 문자를 순차적으로 처리하여 값을 변경하는 방식입니다. 시간 복잡도는 문자열의 길이에 비례하여 O(m)이고, 추가적인 공간을 거의 사용하지 않으므로 공간 복잡도는 상수 공간인 O(1)입니다.

핵심 포인트

1. 문자열을 순차적으로 탐색하며 switch 또는 if-else문으로 각 문자를 처리한다.
2. 시간 복잡도는 O(m), 공간 복잡도는 O(1)로 매우 효율적이다.
3. 파이썬과 자바에서 각각 간단한 코드로 구현 가능하다.

결론

이 문제는 시간, 공간 복잡도 모두 효율적인 방식으로 해결할 수 있는 문제입니다. 입력 크기 제한도 비교적 크지 않으므로 주어진 방법으로 충분히 처리할 수 있습니다.