Roma Rakamlarını Tam Sayıya Çevirme: LeetCode #13 Detaylı Analiz
LeetCode’un “Top Interview 150” listesinde yer alan ve mülakatlarda sıkça karşılaşılan “13. Roman to Integer” problemi, Roma rakamlarını modern tam sayılara dönüştürmeyi amaçlayan klasik bir algoritma sorusudur. Bu problem, temel string işleme, koşullu mantık ve veri yapıları bilgisini test ederken, aynı zamanda karmaşık görünen bir sistemin nasıl basit kurallarla çözülebileceğini gösterir. Bu makalede, Roma rakamları sistemini, problem tanımını, etkili bir çözüm algoritmasını ve Python dilinde örnek bir uygulamayı detaylı bir şekilde inceleyeceğiz.
Roma Rakamları Sistemine Giriş
Roma rakamları, Antik Roma’da sayıları temsil etmek için kullanılan bir sistemdir. Günümüzde saat kadranları, kitap bölümleri ve kraliyet isimleri gibi belirli bağlamlarda hala karşımıza çıkabilmektedir. Bu sistemin kendine özgü kuralları ve sembolleri vardır.
Temel Semboller ve Değerleri
Roma rakamları yedi temel sembol kullanır ve her birinin belirli bir tam sayı değeri vardır:
I: 1V: 5X: 10L: 50C: 100D: 500M: 1000
Toplama ve Çıkarma Kuralları
Roma rakamları genellikle soldan sağa doğru okunur ve sembollerin değerleri toplanır. Örneğin, II iki (1+1), VI altı (5+1) ve LX altmış (50+10) anlamına gelir. Ancak sistemin en önemli özelliği, bazı durumlarda çıkarma kuralının uygulanmasıdır. Eğer küçük değerli bir sembol, kendisinden daha büyük değerli bir sembolün solunda yer alıyorsa, küçük değerli sembol büyükten çıkarılır.
Özel Durumlar: Çıkarma Kuralı
Çıkarma kuralı sadece belirli sembol çiftleri için geçerlidir:
I,V(IV=4) veX(IX=9) öncesinde yer alabilir.X,L(XL=40) veC(XC=90) öncesinde yer alabilir.C,D(CD=400) veM(CM=900) öncesinde yer alabilir.
Diğer durumlarda, örneğin IL gibi bir kombinasyon geçerli değildir. Bu kurallar, Roma rakamlarını tam sayılara çevirirken dikkat etmemiz gereken kritik noktalardır.
Problem Tanımı ve LeetCode #13
LeetCode’daki “13. Roman to Integer” problemi, verilen bir Roma rakamı stringini karşılık gelen tam sayıya çevirmemizi ister. Problem, girişin her zaman geçerli bir Roma rakamı olacağını garanti eder.
Girdi Formatı ve Beklenen Çıktı
Girdi, bir string (örneğin, "MCMXCIV") formatındadır. Çıktı ise bu Roma rakamının temsil ettiği tam sayı olmalıdır (örneğin, 1994).
Kısıtlamalar ve Edge Durumlar
Problemin kısıtlamaları genellikle şunları içerir:
- Girdi stringinin uzunluğu 1 ile 15 arasında olabilir.
- Girdi sadece
('I', 'V', 'X', 'L', 'C', 'D', 'M')sembollerini içerir. - Girdinin geçerli bir Roma rakamı olduğu garantidir.
- Çıktının 1 ile 3999 arasında olması beklenir (çünkü 3999, Roma rakamlarıyla temsil edilebilen en büyük sayıdır:
MMMCMXCIX).
Bu kısıtlamalar, çözümümüzün belirli sınırlar içinde çalışacağını ve aşırı büyük sayılar veya geçersiz karakterlerle uğraşmamıza gerek kalmayacağını gösterir.
Neden Önemli Bir Problem?
Bu problem, string işleme, koşullu mantık yürütme ve veri yapılarını (harita/sözlük) etkin bir şekilde kullanma becerilerini test ettiği için önemlidir. Mülakatlarda, adayların problem çözme yaklaşımını, kenar durumları ele alma yeteneğini ve temiz kod yazma alışkanlıklarını değerlendirmek için idealdir.
Temel Çözüm Yaklaşımı: Soldan Sağa Tarama
Roma rakamlarını tam sayıya çevirmenin birden fazla yolu olsa da, en sezgisel ve etkili yaklaşımlardan biri stringi soldan sağa doğru taramaktır. Bu yöntem, çıkarma kuralını akıllıca ele alarak doğru sonucu verir.
Sembol Değerlerini Eşleme
İlk adım, her Roma rakamı sembolünün karşılık gelen tam sayı değerini hızlıca alabileceğimiz bir eşleme (sözlük veya harita) oluşturmaktır. Bu, her sembolü işlerken sürekli if-else blokları yazmaktan daha verimlidir.
roman_map = {
'I': 1, 'V': 5, 'X': 10, 'L': 50,
'C': 100, 'D': 500, 'M': 1000
}
Soldan Sağa Tarama Mantığı
Stringi soldan sağa tararken, her bir sembolün değerini bir sonraki sembolün değeriyle karşılaştırırız. Eğer mevcut sembolün değeri bir sonraki sembolün değerinden küçükse, bu bir çıkarma durumudur. Bu durumda, mevcut sembolün değerini toplamdan çıkarmamız gerekir. Aksi takdirde, mevcut sembolün değerini toplama ekleriz.
Karşılaştırmalı Analiz
Örneğin, "IV" için:
I(1) veV(5) karşılaştırılır. 1 < 5 olduğu için, 1'i toplamdan çıkarırız.V(5) işlenir. Bu son sembol olduğu için 5'i toplama ekleriz.
Başlangıçta toplam 0 ise: 0 - 1 + 5 = 4. Bu yaklaşım, çıkarma kuralını otomatik olarak doğru bir şekilde ele alır.
Algoritma Tasarımı ve Adımlar
Şimdi, soldan sağa tarama yaklaşımını kullanarak Roma rakamını tam sayıya çevirecek algoritmanın adımlarını detaylandıralım.
1. Sembol-Değer Eşlemesi Oluşturma
Yukarıda bahsedildiği gibi, her Roma rakamı sembolünü karşılık gelen tam sayı değerine eşleyen bir sözlük (Python'da dict, diğer dillerde HashMap veya Map) tanımlayın. Bu, sembol değerlerine hızlı erişim sağlar.
2. Toplam Değişkenini Başlatma
Roma rakamının tam sayı karşılığını tutacak bir total veya result değişkeni tanımlayın ve başlangıç değerini 0 olarak ayarlayın.
3. Diziyi Tarama Stratejisi
Verilen Roma rakamı stringini soldan sağa, yani ilk karakterden son karaktere kadar döngü ile tarayın. Döngü, son karakterden bir önceki karaktere kadar gitmeli, çünkü her adımda mevcut karakteri bir sonraki karakterle karşılaştıracağız.
4. Koşullu Toplama/Çıkarma Mantığı
Döngünün her adımında, mevcut karakterin (s[i]) değerini bir sonraki karakterin (s[i+1]) değeriyle karşılaştırın:
- Eğer
roman_map[s[i]] < roman_map[s[i+1]]ise (çıkarma durumu),total -= roman_map[s[i]]yapın. - Aksi takdirde (toplama durumu),
total += roman_map[s[i]]yapın.
Döngü bittikten sonra, son karakterin değeri henüz toplama eklenmemiş olacaktır. Son karakter her zaman toplama eklenmelidir, çünkü onun sağında karşılaştırılacak başka bir karakter yoktur ve asla bir çıkarma durumunun parçası olamaz.
total += roman_map[s[len(s)-1]]
Python ile Kodlama ve Uygulama
Şimdi bu algoritmayı Python dilinde nasıl uygulayacağımıza bakalım.
Yardımcı Fonksiyonlar ve Veri Yapıları
Bu problem için özel bir yardımcı fonksiyona gerek yoktur, ancak roman_map sözlüğü temel veri yapımız olacaktır.
Örnek Kodlama (Python)
class Solution:
def romanToInt(self, s: str) -> int:
roman_map = {
'I': 1, 'V': 5, 'X': 10, 'L': 50,
'C': 100, 'D': 500, 'M': 1000
}
total = 0
n = len(s)
# Son karakterden bir önceki karaktere kadar döngü
for i in range(n - 1):
current_val = roman_map[s[i]]
next_val = roman_map[s[i+1]]
if current_val < next_val:
total -= current_val
else:
total += current_val
# Son karakterin değerini ekle
total += roman_map[s[n-1]]
return total
# Test Durumları
solution = Solution()
print(f"'III' -> {solution.romanToInt('III')}") # Beklenen: 3
print(f"'LVIII' -> {solution.romanToInt('LVIII')}") # Beklenen: 58
print(f"'MCMXCIV' -> {solution.romanToInt('MCMXCIV')}") # Beklenen: 1994
print(f"'IV' -> {solution.romanToInt('IV')}") # Beklenen: 4
print(f"'IX' -> {solution.romanToInt('IX')}") # Beklenen: 9
Test Durumları ve Doğrulama
Yukarıdaki kod bloğunda verilen test durumları, algoritmanın farklı senaryolarda (sadece toplama, çıkarma içeren, karışık) doğru çalıştığını doğrulamak için yeterlidir. LeetCode'da gönderdiğinizde, platform kendi kapsamlı test setlerini kullanarak çözümünüzü değerlendirecektir.
Performans Analizi: Zaman ve Alan Karmaşıklığı
Bir algoritmanın etkinliğini değerlendirmenin iki ana yolu, zaman karmaşıklığı (ne kadar hızlı çalıştığı) ve alan karmaşıklığıdır (ne kadar bellek kullandığı).
Zaman Karmaşıklığı (Time Complexity)
Algoritmamız, Roma rakamı stringini baştan sona tek bir döngü ile tarar. Stringin uzunluğu n ise, döngü n-1 kez çalışır. Her döngü iterasyonunda sözlükten değer okuma ve basit aritmetik işlemler yapılır ki bunlar sabit zamanlı (O(1)) işlemlerdir. Dolayısıyla, algoritmanın zaman karmaşıklığı O(n) veya doğrusal zamandır. Bu, mümkün olan en iyi zaman karmaşıklıklarından biridir, çünkü tüm stringi en az bir kez okumak zorundayız.
Alan Karmaşıklığı (Space Complexity)
Algoritmamız, Roma rakamı sembollerini ve değerlerini depolamak için bir sözlük (roman_map) kullanır. Bu sözlük, yedi sabit sayıda eleman içerir. Giriş stringinin uzunluğundan bağımsız olarak boyutu değişmez. Bu nedenle, algoritmanın alan karmaşıklığı O(1) veya sabit alandır. Bu da oldukça verimli bir bellek kullanımı anlamına gelir.
Sonuç
"13. Roman to Integer" problemi, basit ancak incelikli bir string işleme ve koşullu mantık örneğidir. Roma rakamlarının kendine özgü çıkarma kurallarını, soldan sağa tarama ve bir sonraki karakterle karşılaştırma stratejisiyle zarifçe çözebiliriz. Python'daki sözlükler gibi veri yapılarını kullanarak bu eşlemeyi verimli bir şekilde yönetmek, kodun hem okunabilirliğini hem de performansını artırır. O(n) zaman ve O(1) alan karmaşıklığı ile bu çözüm, hem teorik hem de pratik açıdan oldukça verimlidir. Bu problemi başarıyla çözmek, mülakatlarda temel algoritma becerilerinizi sergilemek için harika bir fırsattır.
Sıkça Sorulan Sorular (SSS)
Neden sağdan sola tarama yerine soldan sağa tarama daha kolay?
Soldan sağa tarama, mevcut sembolün bir sonraki sembolden küçük olup olmadığını kontrol ederek çıkarma kuralını doğrudan uygular. Sağdan sola taramada ise her zaman toplama yapılır, ancak mevcut sembolün değeri bir önceki sembolün değerinden küçükse, mevcut sembolün değeri negatif olarak eklenir. Her iki yaklaşım da çalışır, ancak soldan sağa yaklaşım genellikle daha sezgisel bulunur.
Bu problemde farklı veri yapıları kullanılabilir mi?
roman_map için sözlük (dictionary/hash map) en uygun veri yapısıdır çünkü O(1) ortalama zamanda arama imkanı sunar. Alternatif olarak, uzun bir if-elif-else zinciri veya sabit boyutlu bir dizi de kullanılabilir, ancak sözlük daha temiz ve genişletilebilir bir çözümdür.
Roma rakamları neden bu kadar kısıtlı bir aralıkta (1-3999)?
Antik Roma sisteminde, 3999'dan daha büyük sayılar için yeni semboller veya farklı gösterimler (örneğin, bir sembolün üzerine çizgi çekmek gibi) kullanılırdı. Ancak modern bilgisayar bilimlerinde ve bu LeetCode probleminde, genellikle 1'den 3999'a kadar olan standart Roma rakamları kuralları uygulanır.
Bu problemin gerçek dünya uygulamaları var mı?
Doğrudan Roma rakamlarını çevirme ihtiyacı nadir olsa da, bu problemde kullanılan temel prensipler (string ayrıştırma, sembol tabanlı kuralları yorumlama, koşullu mantık) birçok gerçek dünya uygulamasında karşımıza çıkar. Örneğin, dosya formatlarını ayrıştırma, programlama dillerini yorumlama veya özel metin formatlarını işleme gibi durumlarda benzer mantıklar kullanılır.